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:

Status badges

Description (last modified by 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.

Change History (3)

comment:1 Changed 7 years ago by nthiery

  • Authors set to Nicolas M. Thiéry
  • Cc hivert saliola virmaux sage-combinat added
  • Description modified (diff)

comment:2 Changed 7 years ago by nthiery

  • Branch set to u/nthiery/representation_theory/finite_dimensional_algebras-18311

comment:3 Changed 7 years ago by nthiery

  • Commit set to 50867d895544ee5a449423bde74440ea8470f9ee
  • Dependencies set to 18310, 6484
  • Description modified (diff)

Last 10 new commits:

cba7c8d17696: factored out of the examples a basic implementation of the 0-Hecke monoid
6e81e4b16659: proofreading and little additions to the doc; small refactoring of the code
19756de16659: minor line-split in the doc
fd8e1ad16659: refactored _orthogonal_decomposition and updated doctests accordingly
cc327ef16659: improved documentation for _orthogonal_decomposition
e00dfdb16659: improved documentation for _orthogonal_decomposition
cce7d3d17696: added crosslinks
faf83a116659: added missing hecke_monoid.py file
223e55818310: Finite dimensional modules with basis: improved conversions to vectors and matrices
50867d818311: O(n^3) algorithm for radical_basis in char 0 and faster Cartan invariants matrix by characters
Note: See TracTickets for help on using tickets.