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 1

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: Commit:
Dependencies: 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).

Change History (1)

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)
Note: See TracTickets for help on using tickets.