Opened 8 years ago

Closed 8 years ago

#16739 closed enhancement (fixed)

is_weak_popov

Reported by: ketzu Owned by:
Priority: minor Milestone: sage-6.4
Component: linear algebra Keywords: matrix weak-popov-form #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:

Status badges

Description (last modified by 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 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

Change History (38)

comment:1 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:2 Changed 8 years ago by ketzu

  • 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 ketzu

  • Description modified (diff)

comment:4 Changed 8 years ago by ketzu

  • Description modified (diff)

comment:5 Changed 8 years ago by ketzu

  • Keywords weak-popov-form #16742 added

comment:6 Changed 8 years ago by ketzu

  • Cc jsrn added

comment:7 Changed 8 years ago by ketzu

  • Type changed from PLEASE CHANGE to enhancement

comment:8 Changed 8 years ago by ketzu

  • Branch set to u/ketzu/is_weak_popov

comment:9 Changed 8 years ago by git

  • Commit set to 37898695c0dc92f7e9cd1d0a99fe63c854e18253

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

3789869Added 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.

comment:10 Changed 8 years ago by ketzu

  • Description modified (diff)

comment:11 Changed 8 years ago by ketzu

  • Description modified (diff)

comment:12 Changed 8 years ago by ketzu

  • Description modified (diff)

comment:13 Changed 8 years ago by jsrn

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 jsrn

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.

comment:15 Changed 8 years ago by ketzu

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 ketzu

Doctests and fast fail/less overhead is in progress.

comment:17 Changed 8 years ago by git

  • Commit changed from 37898695c0dc92f7e9cd1d0a99fe63c854e18253 to 7b56085920bd58a400f9e3f97c0e544333ac12f8

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

654a51dOnly changed comment linebreaks.
7b56085Added linebreaks to documentation, reworked listcomprehension into loops for efficiency, added more testcases.

comment:18 Changed 8 years ago by ketzu

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:

654a51dOnly changed comment linebreaks.
7b56085Added linebreaks to documentation, reworked listcomprehension into loops for efficiency, added more testcases.

New commits:

654a51dOnly changed comment linebreaks.
7b56085Added linebreaks to documentation, reworked listcomprehension into loops for efficiency, added more testcases.

comment:19 Changed 8 years ago by jsrn

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.

comment:20 Changed 8 years ago by git

  • Commit changed from 7b56085920bd58a400f9e3f97c0e544333ac12f8 to ca026c37322359d29727d8aafe9c5c6f6948eb3f

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

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

comment:21 Changed 8 years ago by git

  • Commit changed from ca026c37322359d29727d8aafe9c5c6f6948eb3f to 1453fc60a274d68c820e377f9927e5596f5415b2

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

1453fc6Fixed > 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 jsrn

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

comment:23 Changed 8 years ago by ketzu

  • Status changed from new to needs_review

comment:24 Changed 8 years ago by chapoton

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 chapoton

  • Status changed from needs_review to needs_work

comment:26 Changed 8 years ago by git

  • Commit changed from 1453fc60a274d68c820e377f9927e5596f5415b2 to 26a57163c892269005901e92dcf1525811e5c677

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

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

comment:27 Changed 8 years ago by ketzu

  • Status changed from needs_work to needs_review

comment:28 Changed 8 years ago by git

  • Commit changed from 26a57163c892269005901e92dcf1525811e5c677 to 903d7d1d693e55d067f343eb9fbbcb15cc1109e0

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

903d7d1Corrected indentation for seealso block.

comment:29 Changed 8 years ago by chapoton

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 git

  • Commit changed from 903d7d1d693e55d067f343eb9fbbcb15cc1109e0 to 1afe730a87c92d997d1b3d012a4c96ad1389d609

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

1afe730Change of code/doc to make it conform to layout conventions.

comment:31 Changed 8 years ago by git

  • Commit changed from 1afe730a87c92d997d1b3d012a4c96ad1389d609 to 89e927f9beb7d86b63e6feb0b71695633d38e9d3

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

89e927fLine wrap update.

comment:32 Changed 8 years ago by chapoton

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

comment:33 Changed 8 years ago by ketzu

  • Authors set to David Mödinger

comment:34 Changed 8 years ago by chapoton

  • 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

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:

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

comment:35 Changed 8 years ago by ketzu

  • Status changed from needs_review to positive_review

comment:36 Changed 8 years ago by ketzu

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 ketzu

  • Description modified (diff)

comment:38 Changed 8 years ago by vbraun

  • Branch changed from public/ticket/16739 to b29a645d2c0d6c86a127574031b59bbc43811fcf
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.