Opened 5 years ago
Closed 4 years ago
#21024 closed defect (fixed)
weak Popov form and row reduced form should only be for matrices over `k[x]`.
Reported by:  jsrn  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  linear algebra  Keywords:  matrix, polynomial, rd3 
Cc:  dlucas  Merged in:  
Authors:  Kwankyu Lee, Johan Rosenkilde  Reviewers:  Johan Rosenkilde, Kwankyu Lee 
Report Upstream:  N/A  Work issues:  
Branch:  d9e8ed8 (Commits, GitHub, GitLab)  Commit:  d9e8ed83ddb4b1eb3e3b246aa22ea0f05b7f52a6 
Dependencies:  Stopgaps: 
Description (last modified by )
The methods weak_popov_form
and row_reduced_form
currently appear on any matrix. But their main target should be matrices over k[x]
.
Change History (51)
comment:1 Changed 4 years ago by
 Branch set to public/21024
comment:2 Changed 4 years ago by
 Commit set to 2b1de832ce8ab9dfce18f9d46be12c20f374c4ad
comment:3 Changed 4 years ago by
 Description modified (diff)
The patch partially moves weak_popov_form
related methods to a new file matrix_polynomial_dense.pyx
. It is partial because the current weak_popov_form
and row_reduced_form
methods also works for polynomials over k(x)
not only over k[x]
. But I think these methods are basically only for matrices over k[x]
. Thus the leftover methods in matrix2.pyx
and matrix_misc.py
should be removed later by dropping support for matrices over k(x)
.
There is a newly added _weak_popov_form
method in matrix_polynomial_dense.pyx
. This is intended to replace the current weak_popov_form
when the deprecation period is over. See #16742.
comment:4 followup: ↓ 5 Changed 4 years ago by
Small comments: if you move existing code to a new file, I think you should also move attributions in the top of the new file (AUTHORS + copyright), like David Moedinger (20140730)
(and maybe others?).
comment:5 in reply to: ↑ 4 ; followup: ↓ 8 Changed 4 years ago by
Replying to slabbe:
Small comments: if you move existing code to a new file, I think you should also move attributions in the top of the new file (AUTHORS + copyright), like
David Moedinger (20140730)
(and maybe others?).
While I agree that we should respect attributions or credits in general, in this particular case I don't get what you mean. I moved two methods from other files, is_weak_popov
and row_reduced_form
. In top of the files from which these method have moved, I don't see any credit regarding the two methods. The attribution David Moedinger (20140730)
is in the docstring of the method is_weak_popov
, and hence has moved with the method. What else did I miss? Please be explicit.
Do you mean that the attribution David Moedinger (20140730)
found in somewhat obscure place should be moved to the top?
comment:6 Changed 4 years ago by
 Commit changed from 2b1de832ce8ab9dfce18f9d46be12c20f374c4ad to 2e2309deae30c4c41ebd132fbdea2bdb918b667b
Branch pushed to git repo; I updated commit sha1. New commits:
2e2309d  Rewrite the authorship

comment:7 Changed 4 years ago by
slabbe perhaps meant that I gave undue credit to the creator of the file, that is, me. So the last commit.
comment:8 in reply to: ↑ 5 ; followup: ↓ 9 Changed 4 years ago by
Sorry, I wrote my comment quickly. Maybe what I wrote was wrongly written. I was not meaning that you were trying to steal anybody's credit. Sorry if you understood that. That was clearly not my point. I just wanted to give proper credits to the initial author(s) of the moved code.
Do you mean that the attribution
David Moedinger (20140730)
found in somewhat obscure place should be moved to the top?
Yes. I am not a lawyer so I will not cite licences here, only my own opinion. If David Moedinger did not take copyrights in the original file, then, you might not include his name in the copyrights of the new file. But I would think it is a good idea to mention his name (maybe others?) in the AUTHORS field at the top of the module. An author may choose not to mention himself in the top of a module, but I think someone else has do it. That's is my opinion.
comment:9 in reply to: ↑ 8 Changed 4 years ago by
Replying to slabbe:
Do you mean that the attribution
David Moedinger (20140730)
found in somewhat obscure place should be moved to the top?Yes.
I could do it. But he wrote his name *there* (not in the top of the original file), and I fear that moving his name out of its original place might offend him. So I will not do it. But I would not object if other (he or you) do it.
If David Moedinger did not take copyrights in the original file, then, you might not include his name in the copyrights of the new file.
How one can "take copyrights" when he/she added code to a file? I don't understand...
But I would think it is a good idea to mention his name (maybe others?) in the AUTHORS field at the top of the module. An author may choose not to mention himself in the top of a module, but I think someone else has do it. That's is my opinion.
I will not object if anyone that has credit about any code in the file adds his or her name to the AUTHORS block. But I will not spend time to search for authors of each piece of code and add the names to the AUTHORS block.
comment:10 followup: ↓ 12 Changed 4 years ago by
Hi Kwankyu, Thanks for looking at this again!
I agree that the existing weak Popov algorithm should just be removed, the algorithm should not support k(x)
matrices but only k[x]
.
I am surprised that the implementation of #16742 is so slow, but I can confirm your conclusion. David Mödinger was hired by me for a short while to produce that code, and at the time I know he convinced me that his timings were better than my own implementation. However retesting now, the implementation in Codinglib beats both his and your implementation by a wide margin. In particular, it seems your implementation becomes slow for large, lowdegree matrices, since you iterate over, potentially, the whole matrix after every simple transformation:
 Timing test: Big matrix  Codinglib 60 x 60 with deg 20 took on average 2.15060825348 Klee 60 x 60 with deg 20 took on average 17.5283669949
The above test was done by creating matrices which are extremely far from being row reduced: let A, B
be two random lowertriangular matrices with 1 on the diagonal and everything else has high degree. Then we compute the weak Popov form of A*B.transpose()
.
comment:11 Changed 4 years ago by
Deprecation period for #16896, which contains the many annoying deprecations in row_reduced_form
officially run out 19th January 2017.
I think this ticket is a good place to deprecate k(x)
matrices.
comment:12 in reply to: ↑ 10 ; followup: ↓ 13 Changed 4 years ago by
Replying to jsrn:
Hi Kwankyu, Thanks for looking at this again!
I agree that the existing weak Popov algorithm should just be removed, the algorithm should not support
k(x)
matrices but onlyk[x]
.
We can deprecate the support for k(x)
in this ticket.
the implementation in Codinglib beats both his and your implementation by a wide margin. In particular, it seems your implementation becomes slow for large, lowdegree matrices, since you iterate over, potentially, the whole matrix after every simple transformation
Right, I concerned about that. Are you willing to share your code for this ticket. You can add it as _weak_popov_form_jsrn
. Then I will test more. Then we can remove the slower one among yours and mine.
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 4 years ago by
Replying to klee:
We can deprecate the support for
k(x)
in this ticket.
Can we also not just throw away the old, slow _row_reduced_form
algorithm, and simply make row_reduced_form
an alias of weak_popov_form
? (the alias makes sense as there might later be faster algorithms for computing just a row_reduced_form
, particularly in a future release of LinBox?).
Right, I concerned about that. Are you willing to share your code for this ticket. You can add it as
_weak_popov_form_jsrn
. Then I will test more. Then we can remove the slower one among yours and mine.
Sure. I'll look at porting my code. It should be straightforward.
Best, Johan
comment:14 in reply to: ↑ 13 ; followup: ↓ 16 Changed 4 years ago by
Replying to jsrn:
Can we also not just throw away the old, slow
_row_reduced_form
algorithm, and simply makerow_reduced_form
an alias ofweak_popov_form
? (the alias makes sense as there might later be faster algorithms for computing just arow_reduced_form
, particularly in a future release of LinBox?).
I am confused. I did not throw anything regarding row_reduced_form
method. There was one row_reduced_form
method in matrix_misc.py
, and I moved its k[x]
part to matrix_polynomial_dense.pyx
, splitting out the algorithmic core to _row_reduced_form
method, if I did all this correctly.
And why make row_reduced_form
an alias of weak_popov_form
? Aren't they different algorithms, though currently weak_popov_form
method is an alias of row_reduced_form
because of a historical reason?
comment:15 Changed 4 years ago by
 Commit changed from 2e2309deae30c4c41ebd132fbdea2bdb918b667b to 65dd10366ba1cb645717f03453355ed9bc316cfe
Branch pushed to git repo; I updated commit sha1. New commits:
65dd103  Added _weak_popov_jsrn

comment:16 in reply to: ↑ 14 Changed 4 years ago by
Replying to klee:
I am confused. I did not throw anything regarding
row_reduced_form
method. There was onerow_reduced_form
method inmatrix_misc.py
, and I moved itsk[x]
part tomatrix_polynomial_dense.pyx
, splitting out the algorithmic core to_row_reduced_form
method, if I did all this correctly.And why make
row_reduced_form
an alias ofweak_popov_form
? Aren't they different algorithms, though currentlyweak_popov_form
method is an alias ofrow_reduced_form
because of a historical reason?
A matrix in weak Popov form is also row reduced. Thus, since either of our algorithms for weak Popov form are much faster than row_reduced_form
, we should just call weak Popov instead. The answer is still correct (the returned matrix is row reduced), and it is computed faster. Therefore, I propose that row_reduced_form
should just call the new weak_popov_form
algorithm. And the current algorithm for row_reduced_form
can be entirely removed.
comment:17 Changed 4 years ago by
I've pushed a port of Codinglib's MuldersStorjohann implementation. Here are some more timing results:
 Timing tests  Jsrn 10 x 10 with deg 10 took on average 0.0137166023254 Klee 10 x 10 with deg 10 took on average 0.016663980484 Jsrn 10 x 10 with deg 50 took on average 0.0350609779358 Klee 10 x 10 with deg 50 took on average 0.0676296234131 Jsrn 10 x 10 with deg 100 took on average 0.0774172306061 Klee 10 x 10 with deg 100 took on average 0.122051906586 Jsrn 20 x 20 with deg 10 took on average 0.050380563736 Klee 20 x 20 with deg 10 took on average 0.144425344467 Jsrn 20 x 20 with deg 20 took on average 0.0996264457703 Klee 20 x 20 with deg 20 took on average 0.320650005341 Jsrn 20 x 20 with deg 50 took on average 0.251339626312 Klee 20 x 20 with deg 50 took on average 0.6192029953 Jsrn 20 x 20 with deg 100 took on average 0.510989379883 Klee 20 x 20 with deg 100 took on average 1.29789443016 Jsrn 40 x 40 with deg 10 took on average 0.280953645706 Klee 40 x 40 with deg 10 took on average 1.82664017677 Jsrn 40 x 40 with deg 20 took on average 0.619099617004 Klee 40 x 40 with deg 20 took on average 3.85582876205 Jsrn 40 x 40 with deg 50 took on average 1.45434303284 Klee 40 x 40 with deg 50 took on average 8.04331936836 Jsrn 40 x 40 with deg 100 took on average 3.26861662865 Klee 40 x 40 with deg 100 took on average 16.6390136719 Jsrn 100 x 100 with deg 10 took on average 3.26953678131 Klee 100 x 100 with deg 10 took on average 65.4183327675
Those timings were produced with the following test code:
import time def make_invertible_lower(PF, m, N=100): "Create a lowerdiagonal polynomial matrix which is invertible" def cell(i,j): if i<j: return PF.zero() elif i==j: return PF.one() else: return PF.random_element(degree=randint(0,N//2)) return matrix(PF, m, m, cell) def make_totally_reducible(PF, m, N=100): A = make_invertible_lower(PF, m, N=N//2) B = make_invertible_lower(PF, m, N=N//2) return A * B.transpose() def time_weak_popov(m, N, iters, alg, verify=True): sum_time = 0 for i in range(iters): M = make_totally_reducible(PF, m, N) now = time.time() W = alg(M) sum_time += time.time()  now if verify: assert W.is_weak_popov() return sum_time/iters iters = 5 for (m,N) in [ (10, 10), (10, 50), (10, 100), (20, 10), (20,20), (20, 50), (20, 100), (40, 10), (40, 20), (40,50), (40,100), (100, 10), (100,100) ]: print "Jsrn %s x %s with deg %s took on average\t%s" % (m,m, N, time_weak_popov(m,N,iters, alg=lambda M: M._weak_popov_form_jsrn())) print "Klee %s x %s with deg %s took on average\t%s" % (m,m, N, time_weak_popov(m,N,iters, alg=lambda M: M._weak_popov_form())) print
comment:18 followup: ↓ 20 Changed 4 years ago by
Btw, my implementation is ready for also supporting shifts without too much penalty. This is something we should definitely add support for, though perhaps not in this ticket.
comment:19 Changed 4 years ago by
 Commit changed from 65dd10366ba1cb645717f03453355ed9bc316cfe to 6d04a55f19b144ecee693ea8a8666022154ef2be
Branch pushed to git repo; I updated commit sha1. New commits:
6d04a55  Better weak Popov form implementation

comment:20 in reply to: ↑ 18 Changed 4 years ago by
Replying to jsrn:
Btw, my implementation is ready for also supporting shifts without too much penalty. This is something we should definitely add support for, though perhaps not in this ticket.
Why not? Your code is already equipped with it. You need to just add some examples.
Please also add your name to AUTHORS, to the code and to this ticket.
Did I say it? Your implementation is clear winner! :)
comment:21 Changed 4 years ago by
 Commit changed from 6d04a55f19b144ecee693ea8a8666022154ef2be to b659e3c6f8998faa5f2abd5d791be69c88b939b0
Branch pushed to git repo; I updated commit sha1. New commits:
b659e3c  Deprecate support for matrices of rational functions

comment:22 Changed 4 years ago by
 Description modified (diff)
 Summary changed from weak Popov form and row reduced should only be for matrices over `k(x)` or `k[x]`. to weak Popov form and row reduced should only be for matrices over `k[x]`.
comment:23 followup: ↓ 24 Changed 4 years ago by
OK, cool. Since we're at it, I think we should also:
 Remove deprecations from #16896 and cleanup the related code (this ticket won't be in a stable release before the deprecation period runs out).
 Add support for shifts, as you suggest.
 Remove the old
row_reduced_form
algorithm and just call MuldersStorjohann.
I'm pretty tied up this week, but I can try to get these last things done. Best, Johan
comment:24 in reply to: ↑ 23 Changed 4 years ago by
Replying to jsrn:
OK, cool. Since we're at it, I think we should also:
 Remove deprecations from #16896 and cleanup the related code (this ticket won't be in a stable release before the deprecation period runs out).
 Add support for shifts, as you suggest.
 Remove the old
row_reduced_form
algorithm and just call MuldersStorjohann.I'm pretty tied up this week, but I can try to get these last things done.
I already did (3) in the last commit. I can do (1). I can also do (2) if you comment here some nice examples; I will copy and paste.
comment:25 Changed 4 years ago by
 Commit changed from b659e3c6f8998faa5f2abd5d791be69c88b939b0 to 06738a6867a1ef238189728922059640f12a13c0
Branch pushed to git repo; I updated commit sha1. New commits:
06738a6  Remove weak_popov_form from matrix2.pyx

comment:26 Changed 4 years ago by
 Commit changed from 06738a6867a1ef238189728922059640f12a13c0 to 9a6fcb281b21d06be9897c317d53138187d65453
Branch pushed to git repo; I updated commit sha1. New commits:
9a6fcb2  Remove deprecated methods

comment:27 Changed 4 years ago by
 Commit changed from 9a6fcb281b21d06be9897c317d53138187d65453 to 4ba5068845409ea6a1389e1052c5a0fc0e358ff9
Branch pushed to git repo; I updated commit sha1. New commits:
4ba5068  Add an explanation for old_call argument

comment:28 Changed 4 years ago by
 Commit changed from 4ba5068845409ea6a1389e1052c5a0fc0e358ff9 to e86b9cff384cd65f1b61226524906465b3666b60
Branch pushed to git repo; I updated commit sha1. New commits:
e86b9cf  Add an explanation for old_call argument

comment:29 Changed 4 years ago by
 Commit changed from e86b9cff384cd65f1b61226524906465b3666b60 to b7078feff0a9e748aae6b7c8cf14a0ff33f4af2a
comment:30 Changed 4 years ago by
 Status changed from new to needs_review
comment:31 Changed 4 years ago by
 Commit changed from b7078feff0a9e748aae6b7c8cf14a0ff33f4af2a to 205b26062a79320e9e790ed2ac90769912f21a5e
Branch pushed to git repo; I updated commit sha1. New commits:
205b260  Fix a doctest failure

comment:32 Changed 4 years ago by
 Summary changed from weak Popov form and row reduced should only be for matrices over `k[x]`. to weak Popov form and row reduced form should only be for matrices over `k[x]`.
comment:33 Changed 4 years ago by
 Milestone changed from sage7.3 to sage7.6
To the reviewer: the startup plugin failure is due to adding a separate file for matrices over univariate polynomial rings. As this is the main point of the ticket, I have nothing to do for the failure. The new file is a platform on which to build fast algorithms specialized for the polynomial matrices.
comment:34 Changed 4 years ago by
Sorry for my inactivity. I will definitely look at this ticket on Tuesday for Sage Review Days 3.
comment:35 Changed 4 years ago by
 Commit changed from 205b26062a79320e9e790ed2ac90769912f21a5e to c1f705a85b2126310f02e26567d6d06c16dac63f
Branch pushed to git repo; I updated commit sha1. New commits:
189453d  Improved some doc texts

2dd74df  Improved some doc strings. Rm test that wPf input is returned unchanged (why make such a promise?)

03d67d9  More simple doc text polishing. Removed unnecessary _row_reduced_form

198b2d7  Kill some deprecated call functionality. Add message for future cleanup

c1f705a  Add shifts to row_reduced_form. Simplify in GuruswamiSudan now we have shifted row reduced form

comment:36 Changed 4 years ago by
OK, so I've reviewed the existing changes, and made some more changes which now needs review. To ease the burden of this future reviewer, here is a description:
 Improved formatting of many doc tests so matrices can be visually inspected.
 Improved grammar of some doc strings.
 Remove the
old_call
optional argument which was deprecated >1 year ago in #16896.  Add
shifts
torow_reduced_form
. Removed_row_reduced_form
frommatrix_polynomial_dense
.  Simplified GuruswamiSudan interpolation function which manually handled shifts in call to row reduced. This allowed simplifying some helper functions into one function (which we, in the future, probably want to have on polynomial vectors and matrices).
comment:37 Changed 4 years ago by
 Commit changed from c1f705a85b2126310f02e26567d6d06c16dac63f to f77c3008dce25936a393444c01b08e291b9b93de
Branch pushed to git repo; I updated commit sha1. New commits:
f77c300  Add author

comment:38 Changed 4 years ago by
 Reviewers set to Johan Rosenkilde, Kwankyu Lee
Added myself as author on the weak_popopv_form
implementation.
comment:39 Changed 4 years ago by
 Keywords rd3 added
comment:40 Changed 4 years ago by
From the description of #16896:
In one year, we'll change the default behaviour but retain
old_call
as an acceptable argument, but print a deprecation warning if one sets it. In two years, we can finally removeold_call
and have the clean calling convention.
The logic seems that the deprecation period of the old calling convention is over, but that of old_call
itself is still one year from now. So shouldn't we keep old_call
for another year? Sigh...
comment:41 followup: ↓ 42 Changed 4 years ago by
Oh yeah, I came up with that actually. Since then, I decided (with myself) that it was stupid. After all, old_call
was clearly instated as a quick workaround for users to make their code work. If they used it, it should be clear to them that they were stepping on melting ice.
I think it should be safe to remove it and return sanity to the code...
comment:42 in reply to: ↑ 41 Changed 4 years ago by
Replying to jsrn:
I think it should be safe to remove it and return sanity to the code...
I agree :)
comment:43 Changed 4 years ago by
Can you positive review my changes, then? ;) (I have "positive reviewed" your changes, modulo the changes I've already added).
comment:44 Changed 4 years ago by
 Commit changed from f77c3008dce25936a393444c01b08e291b9b93de to c4d227b7c4153027bcf4f7be343df9829e93ce9d
Branch pushed to git repo; I updated commit sha1. New commits:
c4d227b  Fix a minor formatting error in a docstring

comment:45 Changed 4 years ago by
 Status changed from needs_review to positive_review
Positive review to the changes by the other author/reviewer.
comment:46 Changed 4 years ago by
Thanks for the cooperation!
comment:47 Changed 4 years ago by
 Status changed from positive_review to needs_work
PDF docs don't build:
[docpdf] ! LaTeX Error: Bad math environment delimiter. [docpdf] [docpdf] See the LaTeX manual or LaTeX Companion for explanation. [docpdf] Type H <return> for immediate help. [docpdf] ... [docpdf] [docpdf] l.29239 form, where \(\math [docpdf] {diag}\) denotes a diagonal matrix..
comment:48 Changed 4 years ago by
 Commit changed from c4d227b7c4153027bcf4f7be343df9829e93ce9d to d9e8ed83ddb4b1eb3e3b246aa22ea0f05b7f52a6
Branch pushed to git repo; I updated commit sha1. New commits:
d9e8ed8  Fix docstring errors

comment:49 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:50 Changed 4 years ago by
 Status changed from needs_review to positive_review
As this is a trivial fix, I take the liberty to give positive review to my own change.
comment:51 Changed 4 years ago by
 Branch changed from public/21024 to d9e8ed83ddb4b1eb3e3b246aa22ea0f05b7f52a6
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
Bugfix for zero lines and correction of an example.
Added commentary for understanding the code.
counting zero lines instead of negativ indices, changed to coding conventions
Rename new implementation as _weak_popov_form
Separate new weak popov norm method
Subclass matrix for univariate polynomial ring
Add my own weak popov implementation
Remove weak_popov.pyx
Polish docstrings
Polish docstrings