Re: Linear algebra via CUP decomposition and reduction to matrix multiplication

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Mar 09, 2017 at 11:02:43AM +0100, Peter Bruin wrote:
> Hello,
> 
> Here is a set of patches that speeds up many linear algebra computations
> over fields of small characteristic (Flm, FlxqM) by using the CUP matrix
> decomposition [1].  This decomposes any m × n matrix of rank r over a
> field as C*U*P with C in column echelon form of size m × r, U upper
> triangular of size r × n and P a permutation matrix of size n × n.
> 
> There is one small user-visible change: the various gauss_pivot and
> indexrank functions used to return the list of pivot columns in the row
> echelon form, and for each pivot column the first possible pivot row.
> The new algorithm instead returns the list of pivot rows in the column
> echelon from, and for each pivot row some choice of pivot column.  This
> explains the changed output in the "nf" and "rnfkummer" tests in the
> last patch.  I checked that the new output is mathematically equivalent
> to the old output.

Applied, thanks!

I took the opportunuity to add a GP function permsign.

Cheers,
Bill.