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: sage-7.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:

Status badges

Description (last modified by klee)

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 klee

  • Authors set to Kwankyu Lee
  • Branch set to public/21024

comment:2 Changed 4 years ago by git

  • Commit set to 2b1de832ce8ab9dfce18f9d46be12c20f374c4ad

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

058bbfdBugfix for zero lines and correction of an example.
5778084Added commentary for understanding the code.
2ea6433counting zero lines instead of negativ indices, changed to coding conventions
b6a84aaRename new implementation as _weak_popov_form
7b5401eSeparate new weak popov norm method
bdc4778Subclass matrix for univariate polynomial ring
d61d306Add my own weak popov implementation
4e83a97Remove weak_popov.pyx
2d8bfa0Polish docstrings
2b1de83Polish docstrings

comment:3 Changed 4 years ago by klee

  • 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 left-over 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 follow-up: Changed 4 years ago by 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 (2014-07-30) (and maybe others?).

comment:5 in reply to: ↑ 4 ; follow-up: Changed 4 years ago by klee

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 (2014-07-30) (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 (2014-07-30) 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 (2014-07-30) found in somewhat obscure place should be moved to the top?

comment:6 Changed 4 years ago by git

  • Commit changed from 2b1de832ce8ab9dfce18f9d46be12c20f374c4ad to 2e2309deae30c4c41ebd132fbdea2bdb918b667b

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

2e2309dRewrite the authorship

comment:7 Changed 4 years ago by klee

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 ; follow-up: Changed 4 years ago by slabbe

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 (2014-07-30) 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 klee

Replying to slabbe:

Do you mean that the attribution David Moedinger (2014-07-30) 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 follow-up: Changed 4 years ago by 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 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, low-degree 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 lower-triangular 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 jsrn

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 ; follow-up: Changed 4 years ago by klee

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 only k[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, low-degree 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 ; follow-up: Changed 4 years ago by jsrn

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 ; follow-up: Changed 4 years ago by klee

Replying to jsrn:

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?).

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 git

  • Commit changed from 2e2309deae30c4c41ebd132fbdea2bdb918b667b to 65dd10366ba1cb645717f03453355ed9bc316cfe

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

65dd103Added _weak_popov_jsrn

comment:16 in reply to: ↑ 14 Changed 4 years ago by jsrn

Replying to klee:

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?

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 jsrn

I've pushed a port of Codinglib's Mulders-Storjohann 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 lower-diagonal 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 follow-up: Changed 4 years ago by 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.

comment:19 Changed 4 years ago by git

  • Commit changed from 65dd10366ba1cb645717f03453355ed9bc316cfe to 6d04a55f19b144ecee693ea8a8666022154ef2be

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

6d04a55Better weak Popov form implementation

comment:20 in reply to: ↑ 18 Changed 4 years ago by klee

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 git

  • Commit changed from 6d04a55f19b144ecee693ea8a8666022154ef2be to b659e3c6f8998faa5f2abd5d791be69c88b939b0

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

b659e3cDeprecate support for matrices of rational functions

comment:22 Changed 4 years ago by klee

  • 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 follow-up: Changed 4 years ago by jsrn

OK, cool. Since we're at it, I think we should also:

  1. Remove deprecations from #16896 and cleanup the related code (this ticket won't be in a stable release before the deprecation period runs out).
  2. Add support for shifts, as you suggest.
  3. Remove the old row_reduced_form algorithm and just call Mulders--Storjohann.

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 klee

Replying to jsrn:

OK, cool. Since we're at it, I think we should also:

  1. Remove deprecations from #16896 and cleanup the related code (this ticket won't be in a stable release before the deprecation period runs out).
  2. Add support for shifts, as you suggest.
  3. Remove the old row_reduced_form algorithm and just call Mulders--Storjohann.

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 git

  • Commit changed from b659e3c6f8998faa5f2abd5d791be69c88b939b0 to 06738a6867a1ef238189728922059640f12a13c0

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

06738a6Remove weak_popov_form from matrix2.pyx

comment:26 Changed 4 years ago by git

  • Commit changed from 06738a6867a1ef238189728922059640f12a13c0 to 9a6fcb281b21d06be9897c317d53138187d65453

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

9a6fcb2Remove deprecated methods

comment:27 Changed 4 years ago by git

  • Commit changed from 9a6fcb281b21d06be9897c317d53138187d65453 to 4ba5068845409ea6a1389e1052c5a0fc0e358ff9

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

4ba5068Add an explanation for old_call argument

comment:28 Changed 4 years ago by git

  • Commit changed from 4ba5068845409ea6a1389e1052c5a0fc0e358ff9 to e86b9cff384cd65f1b61226524906465b3666b60

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

e86b9cfAdd an explanation for old_call argument

comment:29 Changed 4 years ago by git

  • Commit changed from e86b9cff384cd65f1b61226524906465b3666b60 to b7078feff0a9e748aae6b7c8cf14a0ff33f4af2a

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

0b41f2dMerge branch Sage 7.5 into trac21024
b7078feAdd examples for shifted weak popov form

comment:30 Changed 4 years ago by klee

  • Status changed from new to needs_review

comment:31 Changed 4 years ago by git

  • Commit changed from b7078feff0a9e748aae6b7c8cf14a0ff33f4af2a to 205b26062a79320e9e790ed2ac90769912f21a5e

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

205b260Fix a doctest failure

comment:32 Changed 4 years ago by klee

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

  • Milestone changed from sage-7.3 to sage-7.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 jsrn

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 git

  • Commit changed from 205b26062a79320e9e790ed2ac90769912f21a5e to c1f705a85b2126310f02e26567d6d06c16dac63f

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

189453dImproved some doc texts
2dd74dfImproved some doc strings. Rm test that wPf input is returned unchanged (why make such a promise?)
03d67d9More simple doc text polishing. Removed unnecessary _row_reduced_form
198b2d7Kill some deprecated call functionality. Add message for future cleanup
c1f705aAdd shifts to row_reduced_form. Simplify in Guruswami-Sudan now we have shifted row reduced form

comment:36 Changed 4 years ago by jsrn

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 to row_reduced_form. Removed _row_reduced_form from matrix_polynomial_dense.
  • Simplified Guruswami-Sudan 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 git

  • Commit changed from c1f705a85b2126310f02e26567d6d06c16dac63f to f77c3008dce25936a393444c01b08e291b9b93de

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

f77c300Add author

comment:38 Changed 4 years ago by jsrn

  • Authors changed from Kwankyu Lee to Kwankyu Lee, Johan Rosenkilde
  • Reviewers set to Johan Rosenkilde, Kwankyu Lee

Added myself as author on the weak_popopv_form implementation.

comment:39 Changed 4 years ago by jsrn

  • Keywords rd3 added

comment:40 Changed 4 years ago by klee

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 remove old_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 follow-up: Changed 4 years ago by jsrn

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 work-around 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 klee

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 jsrn

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 git

  • Commit changed from f77c3008dce25936a393444c01b08e291b9b93de to c4d227b7c4153027bcf4f7be343df9829e93ce9d

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

c4d227bFix a minor formatting error in a docstring

comment:45 Changed 4 years ago by klee

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

Thanks for the cooperation!

comment:47 Changed 4 years ago by vbraun

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

  • Commit changed from c4d227b7c4153027bcf4f7be343df9829e93ce9d to d9e8ed83ddb4b1eb3e3b246aa22ea0f05b7f52a6

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

d9e8ed8Fix docstring errors

comment:49 Changed 4 years ago by klee

  • Status changed from needs_work to needs_review

comment:50 Changed 4 years ago by klee

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

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