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:

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 (9)

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

comment:4 Changed 7 years ago by tscrim

  • Dependencies changed from 18310, 6484 to #18310, #6484

Mainly to cc myself.

comment:5 follow-up: Changed 7 years ago by virmaux

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 nthiery

Replying to virmaux:

I just took some time to read the patch.

Thanks!

FiniteDimensionalAlgebrasWithBasis.multiplication_matrix the name is not very explicit, what about basis_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 git

  • Commit changed from 50867d895544ee5a449423bde74440ea8470f9ee to 6dcb0c5173f84d4920149641497fd343b73e2aea

Branch pushed to git repo; I updated commit sha1. New commits:

5f18523Merge branch 'develop' into representation_theory/finite_dimensional_algebras-16659
661c00816659: orthogonal_idempotents_central_mod_rad -> ...mod_radical + small doc fix
ea552de16659: split Algebras.Semisimple.FiniteDimensional.WithBasis in its own file: first step: copying the file
ff577f316659: split Algebras.Semisimple.FiniteDimensional.WithBasis in its own file: actual work
6dcb0c5Merge branch 'representation_theory/finite_dimensional_algebras-16659' into representation_theory/finite_dimensional_algebras-18311

comment:8 Changed 7 years ago by nthiery

  • Dependencies changed from #18310, #6484 to #18310, #6484, #18336

comment:9 Changed 7 years ago by git

  • Commit changed from 6dcb0c5173f84d4920149641497fd343b73e2aea to dca35bd3cbdc215a34862b654cba520659a63bee

Branch pushed to git repo; I updated commit sha1. New commits:

ceb8afd18336: algebra_generators in algebras_with_basis
46f4f5418336: moved default implementation of algebra_generators to MagmaticAlgebras.WithBasis + proofread doc
6a7b4f516659: fixed crosslinks
4d5e4f9Merge branch 't/18336/t/default_behaviour_algebra_generators' into representation_theory/finite_dimensional_algebras-18311
dca35bd18311: finished previous merge + let multiplication_matrices work even if product_on_basis is NotImplemented
Note: See TracTickets for help on using tickets.