Opened 8 years ago
Closed 8 years ago
#16739 closed enhancement (fixed)
is_weak_popov
Reported by:  ketzu  Owned by:  

Priority:  minor  Milestone:  sage6.4 
Component:  linear algebra  Keywords:  matrix weakpopovform #16742 
Cc:  jsrn  Merged in:  
Authors:  David Mödinger  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  b29a645 (Commits, GitHub, GitLab)  Commit:  b29a645d2c0d6c86a127574031b59bbc43811fcf 
Dependencies:  Stopgaps: 
Description (last modified by )
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^{2}+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^{2}+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/techreports/3xx/356.pdf
Change History (38)
comment:1 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:2 Changed 8 years ago by
 Component changed from PLEASE CHANGE to linear algebra
 Description modified (diff)
 Keywords matrix added
 Priority changed from major to minor
comment:3 Changed 8 years ago by
 Description modified (diff)
comment:4 Changed 8 years ago by
 Description modified (diff)
comment:5 Changed 8 years ago by
 Keywords weakpopovform #16742 added
comment:6 Changed 8 years ago by
 Cc jsrn added
comment:7 Changed 8 years ago by
 Type changed from PLEASE CHANGE to enhancement
comment:8 Changed 8 years ago by
 Branch set to u/ketzu/is_weak_popov
comment:9 Changed 8 years ago by
 Commit set to 37898695c0dc92f7e9cd1d0a99fe63c854e18253
comment:10 Changed 8 years ago by
 Description modified (diff)
comment:11 Changed 8 years ago by
 Description modified (diff)
comment:12 Changed 8 years ago by
 Description modified (diff)
comment:13 Changed 8 years ago by
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
comment:14 Changed 8 years ago by
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 nonsquare matrices?
Come to think of it, if the matrix has more rows than cols, the function can immediately return False.
comment:15 Changed 8 years ago by
Line wraps are already in, but not pushed. A fast fail for more rows than cols only works if zero lines are not ignored.
comment:16 Changed 8 years ago by
Doctests and fast fail/less overhead is in progress.
comment:17 Changed 8 years ago by
 Commit changed from 37898695c0dc92f7e9cd1d0a99fe63c854e18253 to 7b56085920bd58a400f9e3f97c0e544333ac12f8
comment:18 Changed 8 years ago by
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.

comment:19 Changed 8 years ago by
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 nonzero. And if not, p will never be read.
comment:20 Changed 8 years ago by
 Commit changed from 7b56085920bd58a400f9e3f97c0e544333ac12f8 to ca026c37322359d29727d8aafe9c5c6f6948eb3f
Branch pushed to git repo; I updated commit sha1. New commits:
ca026c3  removed unnecessary line p=self.nrows()1

comment:21 Changed 8 years ago by
 Commit changed from ca026c37322359d29727d8aafe9c5c6f6948eb3f to 1453fc60a274d68c820e377f9927e5596f5415b2
Branch pushed to git repo; I updated commit sha1. New commits:
1453fc6  Fixed > to >= to make sure it takes the rightmost value and added a TESTS Block to check for this potential bug.

comment:22 Changed 8 years ago by
Cool. Ready to mark as Needs Review? It might be too inbred to make me review it...
comment:23 Changed 8 years ago by
 Status changed from new to needs_review
comment:24 Changed 8 years ago by
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
comment:25 Changed 8 years ago by
 Status changed from needs_review to needs_work
comment:26 Changed 8 years ago by
 Commit changed from 1453fc60a274d68c820e377f9927e5596f5415b2 to 26a57163c892269005901e92dcf1525811e5c677
Branch pushed to git repo; I updated commit sha1. New commits:
26a5716  Updated docstrings to match ::/: indentation, added REFERENCE and SEEALSO.

comment:27 Changed 8 years ago by
 Status changed from needs_work to needs_review
comment:28 Changed 8 years ago by
 Commit changed from 26a57163c892269005901e92dcf1525811e5c677 to 903d7d1d693e55d067f343eb9fbbcb15cc1109e0
Branch pushed to git repo; I updated commit sha1. New commits:
903d7d1  Corrected indentation for seealso block.

comment:29 Changed 8 years ago by
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)
comment:30 Changed 8 years ago by
 Commit changed from 903d7d1d693e55d067f343eb9fbbcb15cc1109e0 to 1afe730a87c92d997d1b3d012a4c96ad1389d609
Branch pushed to git repo; I updated commit sha1. New commits:
1afe730  Change of code/doc to make it conform to layout conventions.

comment:31 Changed 8 years ago by
 Commit changed from 1afe730a87c92d997d1b3d012a4c96ad1389d609 to 89e927f9beb7d86b63e6feb0b71695633d38e9d3
Branch pushed to git repo; I updated commit sha1. New commits:
89e927f  Line wrap update.

comment:32 Changed 8 years ago by
Please write your real name in the Authors: field above.
comment:33 Changed 8 years ago by
comment:34 Changed 8 years ago by
 Branch changed from u/ketzu/is_weak_popov to public/ticket/16739
 Commit changed from 89e927f9beb7d86b63e6feb0b71695633d38e9d3 to b29a645d2c0d6c86a127574031b59bbc43811fcf
 Reviewers set to Frédéric Chapoton
comment:35 Changed 8 years ago by
 Status changed from needs_review to positive_review
comment:36 Changed 8 years ago by
I apreciate your help, thank you for these changes, since I am still uneasy in python and english.
comment:37 Changed 8 years ago by
 Description modified (diff)
comment:38 Changed 8 years ago by
 Branch changed from public/ticket/16739 to b29a645d2c0d6c86a127574031b59bbc43811fcf
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
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.