1 | | This tickets adds a new class for dense matrices over `Zmod(N)` implemented using FLINT's `nmod_mat_t` type, along with some supporting ancillary changes: |
2 | | |
3 | | * Changed echelon form over `Zmod(N)` for composite `N` to return the Howell form (see the introduction and Chapter 4 of [https://cs.uwaterloo.ca/~astorjoh/diss2up.pdf Storjohann's thesis]). Since this echelon form can have more rows than the input matrix, made some supporting changes including a new method `_echelon_copy`. |
4 | | * Changed rank over `Zmod(N)` to return the number of leading 1s in Howell form (it raised a `NotImplementedError` before), and `pivots` to be the locations of these leading 1s. There is also a method `_pivots` for accessing the columns where the leading entry is not 1. |
5 | | * Matrices modulo composite `N` have improved speed and functionality for inversion, `charpoly`, `det`, `minpoly`, `echelon_form`, `solve_right` and `right_kernel_matrix`. There is also a new method `minpoly_ideal` for the ideal vanishing on a matrix (the natural generalization of the minimal polynomial, which generates this ideal when it is principal). |
6 | | * Changed `stack` and `augment` to return a matrix over a common base ring of the two inputs, rather than just using the top/left matrix to determine the base ring. |
7 | | * A new method `_change_implementation` on matrices, together with rough heuristics for matrices on matrices mod `N` in determining when it's worth switching between FLINT and linbox (linbox is faster for large matrices, FLINT for smaller, and FLINT offers extra functionality for matrices modulo composite integers). |
8 | | * Support multiplication of matrices with different implementations |
9 | | * Add FLINT's `ulong_extras` for number theoretic functions on longs |
10 | | * Add some iterators related to split primes in cyclotomic fields in support of changes to `matrix_cyclo_dense` (which uses a multimodular approach), and moved the `_reduction_matrix` method to the base field which will yield better caching behavior. |
11 | | * Fix some doctests that relate to choosing different solutions in `solve_right` and getting different random matrices with a different implementation. |
| 1 | (I accidentally made a comment instead of editing the ticket description) |