Finite-dimensional algebras in Sage?

[Jeroen Demeyer]

Hello all,

Have finite-dimensional algebras (over QQ, say) been implemented in
Sage? I mean an implementation where you can give any multiplication
table and compute with the algebra. Or to give such an algebra as a
sub-algebra of a matrix algebra (first computing the sub-algebra
generated by given matrices...).

I only found sage/categories/finite_dimensional_algebras_with_basis.py
which is just a category with essentially no code.

I am considering to give "implement [1] in Sage" as a master thesis
project (there exists a Magma implementation). This would require such
functionality (or such functionality would be part of the project).

[1] Gabrielle Nebe, Allan Steel, Recognition of division algebras, J.
Algebra 322 (2009), 903--909.

[Dima Pasechnik]

There is such functionality in GAP, so potentially one can just provide an interface.

[Jeroen Demeyer]

On 2011-09-19 13:23, Dima Pasechnik wrote:
> There is such functionality in GAP, so potentially one can just provide
> an interface.

I guess providing an interface would be as much work (maybe even more)
as doing it directly in Sage. There is a lot of "basic" functionality
in GAP but not many non-trivial algorithms it seems.

[Simon King]

Hi Jeroen,

On 19 Sep., 12:23, Jeroen Demeyer <jdeme...@cage.ugent.be> wrote:
> I only found sage/categories/finite_dimensional_algebras_with_basis.py
> which is just a category with essentially no code.

Well, that's for the *category* of such algebras. Hence, it does of
course not contain an implementation of the algebras themselves.

Perhaps sage.algebras.free_algebra_quotient contains what you are
looking for. I never worked with it, but if I remember correctly, it
essentially boils down to providing multiplication matrices.

Best regards,
Simon

[William Stein]

Technically it should. That code was written by David Kohel in 2005
-- one of the first contributions to Sage -- so don't be surprised if
it is crufty.

Writing a fast general finite-dimensional algebras arithmetic class
sounds like a good project to me. Doing it in Sage (over wrapping
GAP) has the advantage that it would work over any base ring.

What functionality does the Magma version provide?

William

>
> Best regards,
> Simon
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

[Maarten Derickx]

I remember that at least at some point I wanted this functionality. And this would probably also allow us to turn the hecke algebras in sage really into algebras. So a big plus 1 from me.

[Maarten Derickx]

[Dima Pasechnik]

actually, I won't mind having the functionality directly in Sage, at all :)

To be uselful fo rme, it certainly will need to support algebras of dimension more than, say, 10,000, which

is not so uncommon in my applications (one often get these as centralisers of permutation

groups, say). This mandates the structure for 

multiplication coefficients being clever.

Dima

 

[Jeroen Demeyer]

On 2011-09-20 12:27, Dima Pasechnik wrote:
> This mandates the structure for
> multiplication coefficients being clever.

You mean they should be sparse?

[Nicolas M. Thiery]

On Mon, Sep 19, 2011 at 12:23:06PM +0200, Jeroen Demeyer wrote:
> I only found sage/categories/finite_dimensional_algebras_with_basis.py
> which is just a category with essentially no code.

I noticed you found #11111 in the mean time. Help on finalizing this
patch is most welcome :-)

> Have finite-dimensional algebras (over QQ, say) been implemented in
> Sage? I mean an implementation where you can give any
> multiplication table and compute with the algebra.

This should only take a few lines to implement. That being said, it is
an often requested feature, so it would be worthwhile to have a nice
and easy front end like:

sage: A = AlgebraFromStructureCoefficients(QQ, [1,2,3], ... multiplication_table)

Basically, the only thing to do is to decide on the exact format for
inputing the multiplication table.

You may want to look at #11111, e.g. by installing the sage-combinat
queue:

> sage -combinat install

The example of finite dimensional algebra with basis does just this,
with an hard coded multiplication table:

sage: C = AlgebrasWithBasis(QQ).FiniteDimensional().example()
sage: C??

> Or to give such an algebra as a sub-algebra of a matrix algebra
> (first computing the sub-algebra generated by given matrices...).

> I am considering to give "implement [1] in Sage" as a master thesis
> project (there exists a Magma implementation). This would require such
> functionality (or such functionality would be part of the project).

+1!

Having a fast implementation of this feature has been on our
dream/todo list ever since we switched from MuPAD.

So far we have been using GAP:

sage: C = AlgebrasWithBasis(QQ).FiniteDimensional().example()
sage: M = MatrixSpace(QQ,2)
sage: s = M([[0,1],[1,0]])
sage: pi = M([[0,1],[0,1]])
sage: A = gap.Subalgebra(gap.MatrixAlgebra(QQ,2), [s,pi]); A
Algebra( Rationals, [ [ [ 0, 1 ], [ 1, 0 ] ], [ [ 0, 1 ], [ 0, 1 ] ] ] )
sage: A.Dimension()
3

I have attached a quick implementation which calls GAP to compute the
algebra closure, and then allows for computing with elements within
Sage (joint with Nicolas Borie; no sage-combinat patch needed). We
basically wanted to see how the category infrastructure for
subquotients would deal with that. Feel free to ask further questions
/ recycle / ...

As William said, a native Sage implementation would be useful in order
to work with any coefficient ring, but also any ambient algebra.
Besides, the underlying tools required to get this specific feature
would be of general use.

Here is a suggestion of implementation plan:

- Low level kernel: implement efficient "mutable" subspaces. That is
we want the usual subspaces:

sage: V = QQ^20
sage: v1 = ...
sage: v2 = ...
sage: S = V.subspace([v1,v2])

with the ability to progressively enlarge *in place* the subspace
by throwing in new vectors:

sage: S.add(v3)
True

(the return value tells whether v3 was actually added or whether it
already belonged to that subspace)

Nicolas B. (in CC) has been using the usual subspaces of FreeModule
for this, and ran into memory issues. This essentially because the
addition of each single vector required the creation of a new
subspace (he could reproduce the exact issue if asked for). At the
end, he implemented his own progressive Gauss elimination ...

Besides, one would want this feature to be available for all vector
spaces in Sage: FreeModule, MatrixSpace, CombinatorialFreeModule,
but also all polynomial rings and such.

- Implement generically (in ModulesWithBasis) a method:

sage: S = V.module_closure([v1,...], operators)

which returns the smallest subspace S of V containing the vectors
[v1,...], and closed upon the action of the linear operators in
``operators``.

- Use it to implement (in AlgebrasWithBasis) a method:

sage: V.algebra_closure([v1,...])

by using the `x -> x*v1` as linear operators.

- Make sure that all sage vector spaces and algebras are in the
appropriate categories!

We had module_closure and algebra_closure in MuPAD. For examples of
use, you may want to browse through the Sage demo at the end of [1]
(don't worry about the maths there; all you need to know to get a
feeling of what's going on is that a Kac algebra is an algebra with
some extra operations).

Cheers,
Nicolas

[1] http://fr.arxiv.org/abs/0812.3044v3

PS: Nicolas is finishing his PhD dissertation right now; he might be
slow answering!

--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[Dima Pasechnik]

In my case, sometimes keeping multiplication coefficients, even in a  sparse form, is less efficient than recomputing them over and over again, from a set of sparse matrix generators. 

[Felix Salfelder]

On Tue, Sep 20, 2011 at 12:40:30PM +0200, Nicolas M. Thiery wrote:
> Here is a suggestion of implementation plan:
>
> - Low level kernel: implement efficient "mutable" subspaces. That is
> we want the usual subspaces:

> [..]

> - Implement generically (in ModulesWithBasis) a method:

> [..]

> - Use it to implement (in AlgebrasWithBasis) a method:

> [..]

> - Make sure that all sage vector spaces and algebras are in the
> appropriate categories!

Hi there.

this looks familiar (in a way).

some time ago i've started implementing path (or 'quiver') algebras in a
similar way. a path algebra is the algebra generated by the paths in a
directed graph -- think of it as a generalization of a free algebra
(where the graph has only one vertex).

i haven't come beyond elements, multiplication and (graded) quotients,
which are currently brute force and quite slow.
nevertheless these basic things work:

(from memory, see doctests for more examples/details):
sage: G = DiGraph({'e':['s'], 's':['e']}, name="some graph");
sage: A = PathAlgebra(GF(3),G);
sage: X=A.gens();X
(e,s,es,se)
sage: e,s,es,se=X
sage: es*e
0
sage: es*s
es
sage: es*se
es_se
sage: A(1)
e + s
sage: I = A.ideal([es*se])
sage: Q = A.quotient(I)
sage: Y=Q.gens();Y
[[e], [s], [es], [se]]
sage: e,s,es,se=Y
sage: Q.gens(2)
[[se_es]]
sage: Q.graded_comp(2).dimension()
1
sage: es+se
[es+se]
sage: e*es
[es]
sage: a=es*se;a
[es_se]
sage: a==0
True
sage: (es*se).simplify()
0

you can find the code here:
http://tool.em.cs.uni-frankfurt.de/~felix/misc/path_algebra-0.0.0.tbz2

regards
felix

[Nicolas M. Thiery]

I am confused. When you say "set of sparse matrix generators" do you
mean "algebra generators" or "basis of the algebra"?

Cheers,
Nicolas

[Dima Pasechnik]

On Wednesday, 21 September 2011 15:21:00 UTC+8, Nicolas M. Thiéry wrote:

On Tue, Sep 20, 2011 at 08:11:39AM -0700, Dima Pasechnik wrote:
>    In my case, sometimes keeping multiplication coefficients, even in a
>     sparse form, is less efficient than recomputing them over and over again,
>    from a set of sparse matrix generators.

I am confused. When you say "set of sparse matrix generators" do you
mean "algebra generators" or "basis of the algebra"?

I mean the basis of the algebra; specifically, orbitals (a.k.a. 2-orbits) of a permutation group, considered as 0-1 matrices.

Say, consider the problem of finding the eigenvalues of a particular element of the algebra, given

as a linear combination of the basis elements.

When the dimension of the algebra is small compared to the size of the domain on which the permutation group acts, even

the regular representation of the algebra is must faster to deal with than the original basis matrices. 

When this is the other way around, it's better to deal with the original basis matrices directly.

Dima

   

 

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/