Processing Math: Done
jsMath
Differences between revisions 11 and 12
⇤ ← Revision 11 as of 2008-11-14 13:41:56 →
Size: 1572
Editor: anonymous
Comment: converted to 1.6 markup
← Revision 12 as of 2019-11-23 17:38:44 → ⇥
Size: 1563
Editor: chapoton
Comment:
Deletions are marked like this. Additions are marked like this.
Line 5: Line 5:
This [[http://trac.sagemath.org/sage_trac/ticket/3042|trac ticket]] has relevant code. This [[https://trac.sagemath.org/ticket/3042|trac ticket]] has relevant code.

Cyclotomic Linear Algebra

This wiki page is about implementing optimized algorithms for linear algebra over cyclotomic fields.

This trac ticket has relevant code.

This short PDF paper by Jen Balakrishnan and William Stein describes the basic idea behind reducing and lifting from mod p to characteristic 0

Some specific tasks

  1. Benchmarking

  2. (mostly done --works) Come up with a fast characteristic polynomial algorithm over cyclotomic fields.

  3. Implement an optimized matrix type Matrix_dense_number_field for matrices with entries in a number field.

  4. Implement a class Matrix_dense_cyclotomic_field that derives from the above class.
  5. Make very fast random_element methods for those matrix types. This will be needed for testing out our algorithms easily, and for tuning them.

  6. Implement multimodular matrix multiplication. This will reduce to doing a bunch of multiplies over GF(p) for many primes p.

  7. Implement p-adic solver with cyclotomic p-adic reconstruction algorithm.

  8. Implement echelon form using solver algorithm (just like we have for QQ).
  9. Maybe implement multimodular echelon form. Might as well.
  10. Implement decomposition.
  11. Sparse multimodular echelon form (this is a case where multimodular makes good sense). This will be needed for presentations of weight 2 modular symbols over cyclotomic fields.

cyclo (last edited 2019-11-23 17:38:44 by chapoton)