Opened 7 years ago
Last modified 7 years ago
#18311 new enhancement
Improve radical_basis and cartan_invariants_matrix for a finite dimensional algebra — at Version 3
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: | 50867d895544ee5a449423bde74440ea8470f9ee |
Dependencies: | 18310, 6484 | 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 (3)
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)
Note: See
TracTickets for help on using
tickets.
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