Changes between Initial Version and Version 1 of Ticket #31548, comment 29


Ignore:
Timestamp:
Apr 27, 2021, 12:03:33 AM (21 months ago)
Author:
David Roe
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #31548, comment 29

    initial v1  
    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)
    122----
    133New commits: