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: | sage-6.7 |
Component: | algebra | Keywords: | |
Cc: | hivert, saliola, virmaux, sage-combinat | Merged in: | |
Authors: | Nicolas M. Thiéry | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | u/nthiery/representation_theory/finite_dimensional_algebras-18311 (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 sage-combinat added
- Description modified (diff)
comment:2 Changed 7 years ago by
- Branch set to u/nthiery/representation_theory/finite_dimensional_algebras-18311
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 follow-up: ↓ 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_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
|
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_algebras-18311
|
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 0-Hecke monoid
16659: proofreading and little additions to the doc; small refactoring of the code
16659: minor line-split 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