is_weak_popov

[sagetrac-ketzu]

The target of this ticket is to provide/add a function is_weak_popov to the matrix interface. The function should return true if the matrix it is called on is in weak popov form. This ticket is independent from but connected to #16742.

Short description of weak popov form: Let R be an ordered Ring and A^mxn 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:

[x²+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.

[x²+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

CC: @johanrosenkilde

Component: linear algebra

Keywords: matrix weak-popov-form #16742

Author: David Mödinger

Branch/Commit: b29a645

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/16739

[sagetrac-ketzu]

Changed keywords from none to matrix

[sagetrac-ketzu]

Changed keywords from matrix to matrix weak-popov-form #16742

[sagetrac-ketzu]

Branch: u/ketzu/is_weak_popov

[sagetrac-git]

Commit: 3789869

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3789869

Added is_weak_popov(self) implementing a simple check if the matrix is in weak popov form for polynomials. Will raise a NotImplementedError if called on matrices containing elements that do not provide a degree(self) method, 3 doctests and comments added, sage -t sage/matrix/matrix0.pyx is passing all test.

[johanrosenkilde]

comment:13

Though the check is elegantly written in two lines, I think it has two
unnecessary downsides:

• It allocates a new matrix in the apply_map, instead of calculating
  the degrees on inspection.

• It doesn't fail fast: for instance, if the first two rows have the
  same leading position, we don't need to continue.

Both issues can be repaired by changing the outer list comprehension
into a loop, where one maintains an auxiliary set of already seen
leading positions.

Probably is_weak_popov will usually not be a performance bottleneck, but nonetheless.

Cheers,
jsrn

[johanrosenkilde]

comment:14

Btw. Sage usually has line wraps on doc strings, right? The line under OUTPUT is very long. Also, the last sentence there is missing a full stop.

Last pet peeve: can you change one or two of the doc tests to be
non-square matrices?

Come to think of it, if the matrix has more rows than cols, the function can immediately return False.

[sagetrac-ketzu]

comment:15

Line wraps are already in, but not pushed.
A fast fail for more rows than cols only works if zero lines are not ignored.

[sagetrac-ketzu]

comment:16

Doctests and fast fail/less overhead is in progress.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

654a51d	Only changed comment linebreaks.
7b56085	Added linebreaks to documentation, reworked listcomprehension into loops for efficiency, added more testcases.

[sagetrac-git]

Changed commit from 3789869 to 7b56085

[sagetrac-ketzu]

comment:18

Some simple measures for the change from list comprehension (probably more "pythonic") to double loops:

list comprehension:

sage: PF = PolynomialRing(GF(2!^32,'a'),'x')

sage: A = random_matrix(PF,400,400,degree=10)
sage: %timeit A.is_weak_popov()
1 loops, best of 3: 7.57 s per loop

sage: B = random_matrix(PF,10,10,degree=800)
sage: %timeit B.is_weak_popov()
1000 loops, best of 3: 554 µs per loop

---

loops

sage: A = random_matrix(PF,400,400,degree=10)
sage: %timeit A.is_weak_popov()
1000 loops, best of 3: 251 µs per loop
sage: A.is_weak_popov()
False

sage: for x in range(A.nrows()):
....:     A[x,x] = A[x,x].shift(11)
....:    
sage: A.is_weak_popov()
True
sage: %timeit A.is_weak_popov()
10 loops, best of 3: 69.1 ms per loop

sage: B = random_matrix(PF,10,10,degree=800)
sage: %timeit B.is_weak_popov()
100000 loops, best of 3: 8.73 µs per loop
sage: B.is_weak_popov()
False

sage: for x in range(B.nrows()):
....:     B[x,x] = B[x,x].shift(801)
....:

Now it's in wpf

sage: %timeit B.is_weak_popov()
10000 loops, best of 3: 46.7 µs per loop
sage: B.is_weak_popov()
True

---

New commits:

654a51d	Only changed comment linebreaks.
7b56085	Added linebreaks to documentation, reworked listcomprehension into loops for efficiency, added more testcases.

---

New commits:

654a51d	Only changed comment linebreaks.
7b56085	Added linebreaks to documentation, reworked listcomprehension into loops for efficiency, added more testcases.

[johanrosenkilde]

comment:19

Cool, looks good. And the timings are quite persuasive.

One thing: I don't see what you need the "p = self.ncols()-1" line for. p will always be reassigned if any element is non-zero. And if not, p will never be read.

[sagetrac-git]

Changed commit from 7b56085 to ca026c3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ca026c3

removed unnecessary line p=self.nrows()-1

[sagetrac-git]

Changed commit from ca026c3 to 1453fc6

[johanrosenkilde]

comment:22

Cool. Ready to mark as Needs Review? It might be too in-bred to make me review it...

[fchapoton]

comment:24

The doc syntax is not good. After any ::, the next line should be indented by 4. After any :, the next line should not be indented at all.

See http://www.sagemath.org/doc/developer/coding_basics.html

[sagetrac-git]

Changed commit from 1453fc6 to 26a5716

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

26a5716

Updated docstrings to match ::/: indentation, added REFERENCE and SEEALSO.

[sagetrac-git]

Changed commit from 26a5716 to 903d7d1

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

903d7d1

Corrected indentation for seealso block.

[fchapoton]

comment:29

Looks good enough. A few more minor things:

• in the doc please start with: Return True etc (no s at the end of Return)
  (recommended use of imperative mode)

• in the code, please put a space after the commas, and a space before and after == and <=
  (pep8 code formatting standard)

[sagetrac-git]

Changed commit from 903d7d1 to 1afe730

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

1afe730

Change of code/doc to make it conform to layout conventions.

[sagetrac-git]

Changed commit from 1afe730 to 89e927f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

89e927f

Line wrap update.

[fchapoton]

comment:32

Please write your real name in the Authors: field above.

[sagetrac-ketzu]

Author: David Mödinger

[fchapoton]

Reviewer: Frédéric Chapoton

[fchapoton]

Changed branch from u/ketzu/is_weak_popov to public/ticket/16739

[fchapoton]

Changed commit from 89e927f to b29a645

[fchapoton]

comment:34

I have made a reviewer's commit with small changes.

If you agree with my changes, you can set this to positive review on my behalf.

---

New commits:

0059337	Merge branch 'u/ketzu/is_weak_popov' of ssh://trac.sagemath.org:22/sage into 16739
b29a645	trac #16739 reviewer patch, minor changes

[sagetrac-ketzu]

comment:36

I apreciate your help, thank you for these changes, since I am still uneasy in python and english.

[vbraun]

Changed branch from public/ticket/16739 to b29a645