Create matrix class for FLINT's nmod_mat module

roed314 commented 3 years ago

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:

Changed echelon form over Zmod(N) for composite N to return the Howell form (see the introduction and Chapter 4 of 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.
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.
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).
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.
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).
Support multiplication of matrices with different implementations
Add FLINT's ulong_extras for number theoretic functions on longs
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.
Fix some doctests that relate to choosing different solutions in solve_right and getting different random matrices with a different implementation.

Depends on #31069

CC: @edgarcosta

Component: linear algebra

Author: David Roe, Edgar Costa

Branch/Commit: u/roed/nmod_mat @ a3c8e38

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/31548

roed314 commented 3 years ago

Description changed:

--- 
+++ 
@@ -1 +1,11 @@
+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:

+* Changed echelon form over `Zmod(N)` for composite `N` to return the Howell form (see the introduction and Chapter 4 of [Storjohann's thesis](https://cs.uwaterloo.ca/~astorjoh/diss2up.pdf)).  Since this echelon form can have more rows than the input matrix, made some supporting changes including a new method `_echelon_copy`.
+* 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.
+* 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).
+* 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.
+* 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).
+* Support multiplication of matrices with different implementations
+* Add FLINT's `ulong_extras` for number theoretic functions on longs
+* 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.
+* Fix some doctests that relate to choosing different solutions in `solve_right` and getting different random matrices with a different implementation.