|
Size: 1563
Comment:
|
Size: 1572
Comment: converted to 1.6 markup
|
| 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 [[http://trac.sagemath.org/sage_trac/ticket/3042|trac ticket]] has relevant code. |
| Line 7: | Line 7: |
| [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] | [[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]] |
| Line 12: | Line 12: |
| 1. [:/benchmark: Benchmarking] | 1. [[/benchmark| Benchmarking]] |
| Line 14: | Line 14: |
| 1. (mostly done --works) [:/charpoly: Come up with a fast characteristic polynomial algorithm over cyclotomic fields.] | 1. (mostly done --works) [[/charpoly| Come up with a fast characteristic polynomial algorithm over cyclotomic fields.]] |
| Line 16: | Line 16: |
| 1. [:/matrix_dense_nf: Implement an optimized matrix type Matrix_dense_number_field for matrices with entries in a number field.] | 1. [[/matrix_dense_nf| Implement an optimized matrix type Matrix_dense_number_field for matrices with entries in a number field.]] |
| Line 22: | Line 22: |
| 1. [:/multipy: Implement multimodular matrix multiplication.] This will reduce to doing a bunch of multiplies over GF(p) for many primes p. | 1. [[/multipy| Implement multimodular matrix multiplication.]] This will reduce to doing a bunch of multiplies over GF(p) for many primes p. |
| Line 24: | Line 24: |
| 1. [:/padicsolver: Implement p-adic solver with cyclotomic p-adic reconstruction algorithm.] | 1. [[/padicsolver| Implement p-adic solver with cyclotomic p-adic reconstruction algorithm.]] |
Cyclotomic Linear Algebra
This wiki page is about implementing optimized algorithms for linear algebra over cyclotomic fields.
This trac ticket has relevant code.
Some specific tasks
(mostly done --works) Come up with a fast characteristic polynomial algorithm over cyclotomic fields.
- Implement a class Matrix_dense_cyclotomic_field that derives from the above class.
- Make very fast random_element methods for those matrix types. This will be needed for testing out our algorithms easily, and for tuning them.
Implement multimodular matrix multiplication. This will reduce to doing a bunch of multiplies over GF(p) for many primes p.
Implement p-adic solver with cyclotomic p-adic reconstruction algorithm.
- Implement echelon form using solver algorithm (just like we have for QQ).
- Maybe implement multimodular echelon form. Might as well.
- Implement decomposition.
- 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.