weak Popov form and row reduced form should only be for matrices over `k[x]`.

[jsrn]

The methods weak_popov_form and row_reduced_form currently appear on any matrix. But their main target should be matrices over k[x].

[git]

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

​058bbfd	Bugfix for zero lines and correction of an example.
​5778084	Added commentary for understanding the code.
​2ea6433	counting zero lines instead of negativ indices, changed to coding conventions
​b6a84aa	Rename new implementation as _weak_popov_form
​7b5401e	Separate new weak popov norm method
​bdc4778	Subclass matrix for univariate polynomial ring
​d61d306	Add my own weak popov implementation
​4e83a97	Remove weak_popov.pyx
​2d8bfa0	Polish docstrings
​2b1de83	Polish docstrings

[klee]

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.

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

[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?

[git]

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

​2e2309d

Rewrite the authorship

[klee]

slabbe perhaps meant that I gave undue credit to the creator of the file, that is, me. So the last commit.

[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.

[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.

[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().

[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.

[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.

[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

[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?

[git]

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

​65dd103

Added _weak_popov_jsrn

[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.

[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

[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.

[git]

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

​6d04a55

Better weak Popov form implementation

[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! :-)

[git]

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

​b659e3c

Deprecate support for matrices of rational functions

[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

[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.

[git]

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

​06738a6

Remove weak_popov_form from matrix2.pyx

[git]

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

​9a6fcb2

Remove deprecated methods

[git]

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

​4ba5068

Add an explanation for old_call argument

[git]

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

​e86b9cf

Add an explanation for old_call argument

[git]

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

​0b41f2d	Merge branch Sage 7.5 into trac21024
​b7078fe	Add examples for shifted weak popov form

[git]

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

​205b260

Fix a doctest failure

[klee]

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.

[jsrn]

Sorry for my inactivity. I will definitely look at this ticket on Tuesday for Sage Review Days 3.

[git]

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 Guruswami-Sudan now we have shifted row reduced form

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

[git]

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

​f77c300

Add author

[jsrn]

Added myself as author on the weak_popopv_form implementation.

[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...

[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...

[klee]

Replying to jsrn:

I think it should be safe to remove it and return sanity to the code...

I agree :-)

[jsrn]

Can you positive review my changes, then? ;-) (I have "positive reviewed" your changes, modulo the changes I've already added).

[git]

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

​c4d227b

Fix a minor formatting error in a docstring

[klee]

Positive review to the changes by the other author/reviewer.

[jsrn]

Thanks for the cooperation!

[vbraun]

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

[git]

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

​d9e8ed8

Fix docstring errors

[klee]

As this is a trivial fix, I take the liberty to give positive review to my own change.