This PR is about the fraction reconstruction part of the block-Wiedemann approach for the change of monomial order. For this, the main tool provided here is a Flint implementation of the algorithm PM-Basis (Giorgi, Jeannerod, Villard, ISSAC 2003).
The last missing part for the block-Wiedemann approach (deducing the lexicographical Gröbner basis from the reconstructed matrix fraction denominator) will be provided in a subsequent PR.
For efficiency, this requires quite a few additions to existing Flint polynomial matrix code (in nmod_poly_mat), in particular for manipulating polynomial matrices seen as a polynomial with matrix coefficient (coined nmod_mat_poly here). Thanks to this, the base case of the recursion ("M-Basis") is fast, comparable to the state-of-the-art implementation in LinBox while supporting prime fields up to about 60 bits. On the other hand, there is still a significant improvement to be expected on the whole recursion ("PM-Basis"), currently quite slower than the state of the art. This will be achieved thanks to the work-in-progress acceleration of Flint's nmod_poly_mat_mul.
Many correctness tests have been performed, and testing code is available in PML (see in particular https://github.com/vneiger/pml/tree/master/flint-extras/nmod_poly_mat_extra/test ). These tests will not be duplicated here for obvious reasons, but specific tests of the whole block-Wiedemann approach will be added once this approach has been completely integrated in the change of ordering code of msolve.
This PR is about the fraction reconstruction part of the block-Wiedemann approach for the change of monomial order. For this, the main tool provided here is a Flint implementation of the algorithm PM-Basis (Giorgi, Jeannerod, Villard, ISSAC 2003).
The last missing part for the block-Wiedemann approach (deducing the lexicographical Gröbner basis from the reconstructed matrix fraction denominator) will be provided in a subsequent PR.
For efficiency, this requires quite a few additions to existing Flint polynomial matrix code (in
nmod_poly_mat), in particular for manipulating polynomial matrices seen as a polynomial with matrix coefficient (coinednmod_mat_polyhere). Thanks to this, the base case of the recursion ("M-Basis") is fast, comparable to the state-of-the-art implementation in LinBox while supporting prime fields up to about 60 bits. On the other hand, there is still a significant improvement to be expected on the whole recursion ("PM-Basis"), currently quite slower than the state of the art. This will be achieved thanks to the work-in-progress acceleration of Flint'snmod_poly_mat_mul.Many correctness tests have been performed, and testing code is available in PML (see in particular https://github.com/vneiger/pml/tree/master/flint-extras/nmod_poly_mat_extra/test ). These tests will not be duplicated here for obvious reasons, but specific tests of the whole block-Wiedemann approach will be added once this approach has been completely integrated in the change of ordering code of msolve.