Bill Allombert on Thu, 09 Mar 2017 20:41:35 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Linear algebra via CUP decomposition and reduction to matrix multiplication |
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.