Cyclotomic Linear Algebra

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

This [http://trac.sagemath.org/sage_trac/ticket/3042 trac ticket] has relevant code.

[attachment:jen.pdf 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. [:/benchmark: Benchmarking]
2. (mostly done --works) [:/charpoly: Come up with a fast characteristic polynomial algorithm over cyclotomic fields.]
3. [:/matrix_dense_nf: 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. [:/multipy: Implement multimodular matrix multiplication.] This will reduce to doing a bunch of multiplies over GF(p) for many primes p.
7. [:/padicsolver: 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.