Opened 7 years ago
Last modified 7 years ago
#18311 new enhancement
Improve radical_basis and cartan_invariants_matrix for a finite dimensional algebra
Reported by:  nthiery  Owned by:  

Priority:  major  Milestone:  sage6.7 
Component:  algebra  Keywords:  
Cc:  hivert, saliola, virmaux, sagecombinat  Merged in:  
Authors:  Nicolas M. Thiéry  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/nthiery/representation_theory/finite_dimensional_algebras18311 (Commits, GitHub, GitLab)  Commit:  dca35bd3cbdc215a34862b654cba520659a63bee 
Dependencies:  #18310, #6484, #18336  Stopgaps: 
Description (last modified by )
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.
Change History (9)
comment:1 Changed 7 years ago by
 Cc hivert saliola virmaux sagecombinat added
 Description modified (diff)
comment:2 Changed 7 years ago by
 Branch set to u/nthiery/representation_theory/finite_dimensional_algebras18311
comment:3 Changed 7 years ago by
 Commit set to 50867d895544ee5a449423bde74440ea8470f9ee
 Dependencies set to 18310, 6484
 Description modified (diff)
comment:4 Changed 7 years ago by
 Dependencies changed from 18310, 6484 to #18310, #6484
Mainly to cc myself.
comment:5 followup: ↓ 6 Changed 7 years ago by
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.
comment:6 in reply to: ↑ 5 Changed 7 years ago by
Replying to virmaux:
I just took some time to read the patch.
Thanks!
FiniteDimensionalAlgebrasWithBasis.multiplication_matrix
the name is not very explicit, what aboutbasis_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
comment:7 Changed 7 years ago by
 Commit changed from 50867d895544ee5a449423bde74440ea8470f9ee to 6dcb0c5173f84d4920149641497fd343b73e2aea
Branch pushed to git repo; I updated commit sha1. New commits:
5f18523  Merge branch 'develop' into representation_theory/finite_dimensional_algebras16659

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_algebras16659' into representation_theory/finite_dimensional_algebras18311

comment:8 Changed 7 years ago by
 Dependencies changed from #18310, #6484 to #18310, #6484, #18336
comment:9 Changed 7 years ago by
 Commit changed from 6dcb0c5173f84d4920149641497fd343b73e2aea to dca35bd3cbdc215a34862b654cba520659a63bee
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_algebras18311

dca35bd  18311: finished previous merge + let multiplication_matrices work even if product_on_basis is NotImplemented

Last 10 new commits:
17696: factored out of the examples a basic implementation of the 0Hecke monoid
16659: proofreading and little additions to the doc; small refactoring of the code
16659: minor linesplit in the doc
16659: refactored _orthogonal_decomposition and updated doctests accordingly
16659: improved documentation for _orthogonal_decomposition
16659: improved documentation for _orthogonal_decomposition
17696: added crosslinks
16659: added missing hecke_monoid.py file
18310: Finite dimensional modules with basis: improved conversions to vectors and matrices
18311: O(n^3) algorithm for radical_basis in char 0 and faster Cartan invariants matrix by characters