Improve radical_basis and cartan_invariants_matrix for a finite dimensional algebra

[nthiery]

This ticket improves the algorithmic complexity (n^4 to n^3 for radical_basis) and further optimizes the code for computing the radical and the Cartan invariants matrix.

Without:

sage: A = HeckeMonoid(SymmetricGroup(5)).algebra(QQ)
sage: %time len(A.radical_basis())
CPU times: user 4.25 s, sys: 45.1 ms, total: 4.3 s
Wall time: 4.26 s
104
sage: %time A.cartan_invariants_matrix()
CPU times: user 45.2 s, sys: 267 ms, total: 45.4 s
Wall time: 45.5 s

With:

sage: A = HeckeMonoid(SymmetricGroup(5)).algebra(QQ)
sage: %time len(A.radical_basis())
CPU times: user 418 ms, sys: 29.5 ms, total: 447 ms
Wall time: 422 ms
104
sage: %time A.cartan_invariants_matrix_by_characters()
CPU times: user 9.39 s, sys: 208 ms, total: 9.6 s
Wall time: 9.53 s

(the above examples do not use that this is a monoid algebra, though of course the sparsity helps).

The dependency on #6484 is only for speed.

[nthiery]

Last 10 new commits:

​cba7c8d	17696: factored out of the examples a basic implementation of the 0-Hecke monoid
​6e81e4b	16659: proofreading and little additions to the doc; small refactoring of the code
​19756de	16659: minor line-split in the doc
​fd8e1ad	16659: refactored _orthogonal_decomposition and updated doctests accordingly
​cc327ef	16659: improved documentation for _orthogonal_decomposition
​e00dfdb	16659: improved documentation for _orthogonal_decomposition
​cce7d3d	17696: added crosslinks
​faf83a1	16659: added missing hecke_monoid.py file
​223e558	18310: Finite dimensional modules with basis: improved conversions to vectors and matrices
​50867d8	18311: O(n^3) algorithm for radical_basis in char 0 and faster Cartan invariants matrix by characters

[tscrim]

Mainly to cc myself.

[virmaux]

Hello,

I just took some time to read the patch.

FiniteDimensionalAlgebrasWithBasis.multiplication_matrix the name is not very explicit, what about basis_action_matrices ? As well, wether we want sparse matrices or not may be given as an argument?

Should we overwrite the previous method for Cartan invariant matrix from #16659 with this new one ? Indeed the return should be the same and it's much faster! In this case maybe we may want to wait that #16659 is positive_reviewed to avoid merging issues.

Everything else looks good to me (modulo the remaining documentation) I can do the aforementioned modifications.

[nthiery]

Replying to virmaux:

I just took some time to read the patch.

Thanks!

FiniteDimensionalAlgebrasWithBasis.multiplication_matrix the name is not very explicit, what about basis_action_matrices ?

Agreed; maybe multiplication_matrix_on_basis. Suggestions anyone?

As well, wether we want sparse matrices or not may be given as an argument?

Maybe indeed. I am also thinking about an option that would apply to the whole algebra to state whether its coefficients structure are sparse or dense.

Should we overwrite the previous method for Cartan invariant matrix from #16659 with this new one ? Indeed the return should be the same and it's much faster!

This one is only valid in large enough characteristic. Also it can be good to have several algorithm for comparison. But I agree we probably want to have an option instead (and possibly several private methods behind the scene).

In this case maybe we may want to wait that #16659 is positive_reviewed to avoid merging issues.

Yeah, I'd rather wait for #16659 to be finished.

Everything else looks good to me (modulo the remaining documentation) I can do the aforementioned modifications.

Let's discuss this tomorrow with Florent. We might want to think about the graded Cartan matrix.

Cheers,

Nicolas

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5f18523	Merge branch 'develop' into representation_theory/finite_dimensional_algebras-16659
​661c008	16659: orthogonal_idempotents_central_mod_rad -> ...mod_radical + small doc fix
​ea552de	16659: split Algebras.Semisimple.FiniteDimensional.WithBasis in its own file: first step: copying the file
​ff577f3	16659: split Algebras.Semisimple.FiniteDimensional.WithBasis in its own file: actual work
​6dcb0c5	Merge branch 'representation_theory/finite_dimensional_algebras-16659' into representation_theory/finite_dimensional_algebras-18311

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ceb8afd	18336: algebra_generators in algebras_with_basis
​46f4f54	18336: moved default implementation of algebra_generators to MagmaticAlgebras.WithBasis + proofread doc
​6a7b4f5	16659: fixed crosslinks
​4d5e4f9	Merge branch 't/18336/t/default_behaviour_algebra_generators' into representation_theory/finite_dimensional_algebras-18311
​dca35bd	18311: finished previous merge + let multiplication_matrices work even if product_on_basis is NotImplemented