id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
16742 Reimplementation of weak_popov_form for matrices ketzu "The target of this ticket is to enhance the function weak_popov of the matrix interface. The function should transform the matrix in weak popov form, it will use mulders-storjohann algorithm and should be much faster than the current implementation but will not work for polynomials over a fraction field only for polynomial rings over finite fields.
This ticket is independent from but connected to #16739.
Short description of weak popov form: Let R be an ordered Ring and Amxn a matrix over R. The leading position of a row is called the position i in [1,m) such that the order of A[i,_] is maximal within the row. If there are multiple entries with the maximum order, the highest i is the leading position (the furthest to the right in the matrix). A is in weak popov form if all leading positions are different (zero lines ignored).
The function will implement this only for polynomial rings, the order function is the degree of the polynomial. Example:
[x2+1, x]
[x, x+1]
is in weak popov form: Row 1 has the degrees 2 and 1, the leading position is for i=0, row 2 has two times degree 1 so the higher i is chosen with i=1.
[x2+1, x]
[x,0]
is NOT in weak popov form, row 1 has now degrees 1 and -1, so the leading position is i=0 as in row 1.
See: [MS] Mulders, Storjohann, On Lattice Reduction for Polynomial Matrices, ftp://ftp.inf.ethz.ch/pub/publications/tech-reports/3xx/356.pdf" enhancement closed minor sage-duplicate/invalid/wontfix performance wontfix matrix weak-popov-form #16739 sd75 jsrn dlucas cpernet David Mödinger N/A u/ketzu/overload_for_faster_weak_popov_form e464be9e38cd84c8d52d9c117724e4a9f0ce01e7 #16888,#16896