Opened 4 years ago

Closed 3 years ago

#23619 closed enhancement (fixed)

Helper functions for polynomial matrices

Reported by: vneiger Owned by:
Priority: major Milestone: sage-8.1
Component: algebra Keywords: matrix
Cc: jsrn, gh-romainlebreton, bruno Merged in:
Authors: Vincent Neiger Reviewers: Johan Rosenkilde, Romain Lebreton, Pascal Giorgi, Bruno Grenet
Report Upstream: N/A Work issues:
Branch: 5fc5fd6 (Commits, GitHub, GitLab) Commit: 5fc5fd6ce0d4ef3871f08c90131d93bb0a9adc61
Dependencies: Stopgaps:

Status badges

Description (last modified by jsrn)

Functions:

  • degree,
  • row_degrees, column_degrees,
  • row_pivots, column_pivots,
  • degree_matrix,
  • row_leading_matrix, column_leading_matrix,
  • is_popov (row/column),
  • is_reduced (row/column).

Change History (69)

comment:1 Changed 4 years ago by vneiger

  • Description modified (diff)

comment:2 Changed 4 years ago by vneiger

  • Description modified (diff)

comment:3 Changed 4 years ago by vneiger

  • Branch set to u/vneiger/23619_polmat_helper

comment:4 Changed 4 years ago by vneiger

  • Commit set to ec172a430570bce97ff58ee520248ac9d5582145

Pushed the first function. Not ready for review.


New commits:

ec172a4degree matrix function working

comment:5 Changed 4 years ago by git

  • Commit changed from ec172a430570bce97ff58ee520248ac9d5582145 to 4aa4338638fc25cf0dfb2824ae0feb4bd82b0325

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

4aa4338improved degree_matrix documentation

comment:6 Changed 4 years ago by git

  • Commit changed from 4aa4338638fc25cf0dfb2824ae0feb4bd82b0325 to 10be03dd10e85f406f9406823bdc365cd41c1c95

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

10be03dfunction and doc degree of a matrix

comment:7 Changed 4 years ago by vneiger

Cleaned documentation for the (shifted) degree matrix, and wrote function/doc for degree of a matrix. Not ready for review.

comment:8 Changed 4 years ago by git

  • Commit changed from 10be03dd10e85f406f9406823bdc365cd41c1c95 to 68de063497c111a12313d396361ebdb5db9fd963

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

0fd8340function and doc for column degree and row degree
68de063function and documentation for leading matrix, row wise and column wise

comment:9 Changed 4 years ago by git

  • Commit changed from 68de063497c111a12313d396361ebdb5db9fd963 to af59287329f6c097a4d4b21f2c559912b5e2b2e8

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

af59287function and doc for is_reduced

comment:10 Changed 4 years ago by git

  • Commit changed from af59287329f6c097a4d4b21f2c559912b5e2b2e8 to 205e188377dccab4ce96a999a2b1372eca75cc56

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

baab67fsmall correction for degree: case of empty matrix
96c7e5atesting corner cases with <<empty>> matrices
205e188is_popov and is_ordered_weak_popov are in good state now; missing examples in the latter

comment:11 Changed 4 years ago by git

  • Commit changed from 205e188377dccab4ce96a999a2b1372eca75cc56 to c42794798eeb2e1e6d34c83c039cc32e48fb53f5

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

c427947class document, and cleaner documentation for methods

comment:12 follow-up: Changed 4 years ago by jsrn

The ticket is coming along very nicely. Some preliminary comments.

  • In docs, prefer "Return the ..." over "Returns the ...". I personally prefer "this matrix" over the less specific "the matrix" when talking about self. I would even use this polynomial matrix if I need to set it apart from e.g. an integer or scalar matrix.
  • degree, doc: "If the matrix is zero, this is a nonnegative integer" - do you mean "this is -\infty"?.
  • degree: why does the 0x0 matrix have degree None? Such a matrix has e.g. rank 0 and characteristic polynomial 1. Similar question for row-degree.
  • degree_matrix: I would prefer that you add a parameter check that the shift is a list of the right length. One could interpret the doc text as expecting the shift to be a vector of integers - is this a problem?
  • degree_matrix, examples: a long line needs wrapping.
  • About references: we don't have as high standards wrt. completeness of referencing all previous history as in journal publications. In fact, for a concept like row_degree I think Sage rarely has references - they are mostly used for algorithms. So I think 1 reference is plenty sufficient. I like your intention of drawing the reader to the related concept of defect but this maybe has most value if properly explained?

In any case, references have to be entered in the special file $SAGE/src/doc/en/reference/references/index.rst and referred to using the syntax [Kai80].

  • leading_matrix, doc: Could you make a shorter explanation for the unshifted case first? I then prefer to define LM_s(M) := LM(M diag(x^{s_1},...,x^{s_n}) which I find easier to parse.
  • leading_matrix: I don't think the self[i,j] == 0 or requirements are necessary in each of the four cases.
  • is_reduced doc: first line, consider putting parentheses around "shifted". And later: "Equivalently, when considering ... left-multiplying", add "(resp. right-multiplying)".
  • pivot: should the pivot degrees only be returned if the user wishes it (by setting a flag return_degree=False)?
  • is_ordered_weak_popov: should this be merged with is_weak_popov by giving the latter an optional flag ordered?

comment:13 Changed 4 years ago by git

  • Commit changed from c42794798eeb2e1e6d34c83c039cc32e48fb53f5 to fff979b9365a34a650652c542b9e19644e834d28

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

7e0f5e8added examples for is_ordered_weak_popov
fff979bJohan's comments and cleaner doc

comment:14 in reply to: ↑ 12 Changed 4 years ago by vneiger

Thank you for your numerous comments.

All that is not commented below was taken into account in the last revision.

Replying to jsrn:

  • degree: why does the 0x0 matrix have degree None? Such a matrix has e.g. rank 0 and characteristic polynomial 1. Similar question for row-degree.

This is a good question and I have no answer. Another choice would be -1, but so far I see no reason to prefer one or the other. Do you?

  • degree_matrix: I would prefer that you add a parameter check that the shift is a list of the right length.

I was hesitating about such a parameter check. If we put one here, then we should do it for every method involving a shift, right?

One could interpret the doc text as expecting the shift to be a vector of integers - is this a problem?

I don't think this is a problem (if I understand well your question): we can input a vector (1,2,3) or a list [1,2,3], both will work.

comment:15 Changed 4 years ago by git

  • Commit changed from fff979b9365a34a650652c542b9e19644e834d28 to 817b81c6d4bc570ff5107c45501d63b14cf32919

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

3d5797dshifts as list/vector: ok now
817b81ctodo

comment:16 Changed 4 years ago by jsrn

Hi, looking better and better :-)

  • leading_matrix, perhaps elsewhere: Don't put parentheses around the condition of an if-statement
  • Prefer a is None compared to a == None.
  • Class doc: forget :meth: for leading_matrix reference.

Things we discussed face2face:

  • pivot -> leading_positions
  • add order_by_degree and order_by_leading_position
  • Raise ValueError? on zero-row or zero-column matrices
  • Check lengths of shifts everywhere

comment:17 Changed 4 years ago by git

  • Commit changed from 817b81c6d4bc570ff5107c45501d63b14cf32919 to 660ab43b9fc8cda4a74f0a10457b00b64c33006e

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

fe37deerow_reduced --> reduced, deprecation warning
91db615check shift length
0545723check shift length
e3064b0pivot index --> leading positions
ee2f999some small fixes
e7d646fpivot index --> leading positions
660ab43degrees and leading positions for empty matrices

comment:18 Changed 4 years ago by jsrn

  • Description modified (diff)

Changed some names in the description, as discussed f2f. The code still needs to be updated.

comment:19 Changed 4 years ago by jsrn

  • Description modified (diff)

Let's go plural.

comment:20 Changed 3 years ago by git

  • Commit changed from 660ab43b9fc8cda4a74f0a10457b00b64c33006e to 72fe310d3d7ecb10c9ed052a2d2f6ded4beae327

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

c6da217plural for row degree / column degree
72fe310now is_reduced accepts zero rows/columns

comment:21 Changed 3 years ago by git

  • Commit changed from 72fe310d3d7ecb10c9ed052a2d2f6ded4beae327 to 7f6e36ebdb652d41dd343ff54697a93e4c7be5f2

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

b5aa3da is_weak_popov now accepts zero rows / columns
8064d7bis_popov now accepts zero rows + option for up-to-permutation test
489344aremove old code
7f6e36esmall code simplification

comment:22 Changed 3 years ago by git

  • Commit changed from 7f6e36ebdb652d41dd343ff54697a93e4c7be5f2 to 9ed9b400de4dc9586112ba7091788cc586880b31

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

3a336c9working on is_hermite
a266d99now, in ordered weak Popov and in Popov the zero rows must appear at the end (bottom if row-wise, right-hand side if column-wise)
dd920d4is_hermite now works, it simply calls is_popov with the right shift
92356cbis_hermite cleaned, lower_echelon option correct now
de58683add test to support empty matrices in is_{hermite,popov,weak_popov,reduced}
9ed9b40added some SEEALSO blocks

comment:23 Changed 3 years ago by jsrn

  • Branch changed from u/vneiger/23619_polmat_helper to u/jsrn/23619_polmat_helper

comment:24 Changed 3 years ago by jsrn

  • Commit changed from 9ed9b400de4dc9586112ba7091788cc586880b31 to 7af4cca233718feaf727265e7cde9114ce505d4d
  • Status changed from new to needs_review

Author forgot to set needs_review (but said so in private conversation)


Last 10 new commits:

c44832eFixed some doc-tests
5d56351Classical Reed-Solomon codes
19ba6f5Fixed small doc-test failure
37515a0Merge branch 'u/vneiger/23619_polmat_helper' of git://trac.sagemath.org/sage into 23619_polmat_helper
c67c7a3Spaces around operators
805ecd7Plural row/col degrees in various doc text
bb7f3a6Fixed a SEEALSO
03cf1a8Simplified some logic in is_reduced
3a03af4Improved reduced_form doc to conform to the rest of the file. A few other small fixes
7af4ccaImproved doc and examples of weak_popov_form

comment:25 follow-up: Changed 3 years ago by jsrn

  • Authors set to Vincent Neiger
  • Reviewers set to Johan Rosenkilde
  • Status changed from needs_review to needs_work

Hi Vincent,

I've carefully gone over the entire file now and I like it - we're almost there. I took the liberty to implement directly some smaller fixes, and also to use this ticket to include some improvements to existing docs and examples in that file. Please review these changes.

As to your changes, I'm ready to green light everything except for the following comments:

  • What's the point of is_empty_popov? Why not just implement the empty case in is_*_popov? If you only have the method for this reason, then the function shoulde be hidden (i.e. start with an underscore). Besides, I find the convention strange: a 2*n matrix can be in Popov form for any n>0 (if n=1 then the second row must be zero for it to be in Popov form). Why disallow 2*0 matrices to be in Popov form?
  • I'm thinking that the is_hermite argument lower_echelon is overkill. I'm not firm on this point since you already implemented it, but is it really useful? Just because not all papers ever agreed on this minor point doesn't mean we should support it everywhere. If the user really wants to, he can easily flip all the rows himself by M.permute_rows(Permutation(range(M.nrows(),0,-1))).
  • If you keep lower_echelon=True, there should be an example using it where the answer is True.

Also, I like your fix for allowing other row orderings in is_popov!

Best, Johan

comment:26 Changed 3 years ago by jsrn

  • Dependencies set to 24640

Oh yeah, I also merged in 24640 since I was worried about a conflict. There seems to have been no conflict with 24640 itself, so technically, I should remove that merge, but there was a conflict with some other parts of rebasing this patch to a newer version of Sage.

comment:27 Changed 3 years ago by git

  • Commit changed from 7af4cca233718feaf727265e7cde9114ce505d4d to 4830af1400ff1f18c436fdefb1851072d05150f5

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

129aa97Merge commit '9ed9b40' into 23619_polmat_helper_nodep
7b51228Plural row/col degrees in various doc text
b70bb38Fixed a SEEALSO
376759fSimplified some logic in is_reduced
0a14228Improved reduced_form doc to conform to the rest of the file. A few other small fixes
4830af1Improved doc and examples of weak_popov_form

comment:28 Changed 3 years ago by git

  • Commit changed from 4830af1400ff1f18c436fdefb1851072d05150f5 to 9eaf1f558d8fe16c91f61ca04a994ccce3735621

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

9eaf1f5Spaces around operators

comment:29 Changed 3 years ago by jsrn

  • Dependencies 24640 deleted

Yay to rewriting history! So I decided to untangle the dependency on #24640 after all, and this was not difficult at all (make new branch off develop, merge in your last commit, cherry-pick my commits). Except that I screwed up and cherry-picked one commit too little (doing git cherry-pick <commitA>..<commitB> does not include <commitA>!) and so ended up adding that after the others. Then git push --force and all is well :-) Now we also know that the patch merges on the latest develop.

comment:30 Changed 3 years ago by vneiger

  • Branch changed from u/jsrn/23619_polmat_helper to u/vneiger/23619_polmat_helper

comment:31 Changed 3 years ago by vneiger

  • Commit changed from 9eaf1f558d8fe16c91f61ca04a994ccce3735621 to cfac2e494b315b1ca507b6d0cdd5c97ac265312a

Oops, I just did "git trac push" just before reading your email. I hope I did not break everything...


Last 10 new commits:

5d56351Classical Reed-Solomon codes
19ba6f5Fixed small doc-test failure
37515a0Merge branch 'u/vneiger/23619_polmat_helper' of git://trac.sagemath.org/sage into 23619_polmat_helper
c67c7a3Spaces around operators
805ecd7Plural row/col degrees in various doc text
bb7f3a6Fixed a SEEALSO
03cf1a8Simplified some logic in is_reduced
3a03af4Improved reduced_form doc to conform to the rest of the file. A few other small fixes
7af4ccaImproved doc and examples of weak_popov_form
cfac2e4some fixes + is_empty_popov now hidden

comment:32 in reply to: ↑ 25 ; follow-up: Changed 3 years ago by vneiger

Replying to jsrn:

Hi Vincent,

I've carefully gone over the entire file now and I like it - we're almost there. I took the liberty to implement directly some smaller fixes, and also to use this ticket to include some improvements to existing docs and examples in that file. Please review these changes.

I have checked all changes in the diff, and everything is good. Thank you for fixing this previously existing code (I was unsure if that needed a separate ticket... still learning :-) ).

  • What's the point of is_empty_popov? Why not just implement the empty case in is_*_popov? If you only have the method for this reason, then the function shoulde be hidden (i.e. start with an underscore). Besides, I find the convention strange: a 2*n matrix can be in Popov form for any n>0 (if n=1 then the second row must be zero for it to be in Popov form). Why disallow 2*0 matrices to be in Popov form?

It is indeed used in is_reduced, is_weak_popov, and is_popov. So I wrote it only once. Now it is hidden (and it does not check anymore that the input is indeed empty). You are right that there were problems with some matrices; to make it behave like other is_* functions, I added a parameter "include_zero_vectors" (True by default, in which case any empty matrix is in shifted Popov form for any shift) and updated the code to reflect this. When one does not want zero rows/vectors in Popov forms, I still think that we should require the number of rows to be at most the number of columns even when the matrix is empty.

  • I'm thinking that the is_hermite argument lower_echelon is overkill. I'm not firm on this point since you already implemented it, but is it really useful? Just because not all papers ever agreed on this minor point doesn't mean we should support it everywhere. If the user really wants to, he can easily flip all the rows himself by M.permute_rows(Permutation(range(M.nrows(),0,-1))).

It is in fact more complicated than this; it is not just a permutation, the two forms are actually quite different and can have very different degree profiles. Since both are in the literature and both seem to be used frequently, I really prefer keeping this optional argument.

  • If you keep lower_echelon=True, there should be an example using it where the answer is True.

Done!

This made me realise that there is a bug with zero rows in is_weak_popov. I will fix this today.

Best,

Vincent

Last edited 3 years ago by vneiger (previous) (diff)

comment:33 in reply to: ↑ 32 ; follow-up: Changed 3 years ago by jsrn

Hi Vincent,

I think you did just bulldoze over my git magic. I'll try to redo it later, but I don't have time right now.

  • What's the point of is_empty_popov? Why not just implement the empty case in is_*_popov? If you only have the method for this reason, then the function shoulde be hidden (i.e. start with an underscore). Besides, I find the convention strange: a 2*n matrix can be in Popov form for any n>0 (if n=1 then the second row must be zero for it to be in Popov form). Why disallow 2*0 matrices to be in Popov form?

It is indeed used in is_reduced, is_weak_popov, and is_popov. So I wrote it only once. Now it is hidden (and it does not check anymore that the input is indeed empty). You are right that there were problems with some matrices; to make it behave like other is_* functions, I added a parameter "include_zero_vectors" (True by default, in which case any empty matrix is in shifted Popov form for any shift) and updated the code to reflect this. When one does not want zero rows/vectors in Popov forms, I still think that we should require the number of rows to be at most the number of columns even when the matrix is empty.

OK, I can agree to this.

  • I'm thinking that the is_hermite argument lower_echelon is overkill. I'm not firm on this point since you already implemented it, but is it really useful? Just because not all papers ever agreed on this minor point doesn't mean we should support it everywhere. If the user really wants to, he can easily flip all the rows himself by M.permute_rows(Permutation(range(M.nrows(),0,-1))).

It is in fact more complicated than this; it is not just a permutation, the two forms are actually quite different and can have very different degree profiles. Since both are in the literature and both seem to be used frequently, I really prefer keeping this optional argument.

Ah, yes I see I was mistaken. But isn't it true that H is in upper-echelon Hermite form exactly when JHJ is in lower-echelon Hermite form, where J is the anti-diagonal unit matrix (i.e. JHJ is H with both columns and rows reversed). Equivalently, the upper-echelon Hermite form of M should be JHJ where H is the lower-echelon Hermite form of JMJ.

Note also that our current hermite_form algorithm does not support computing the upper-echelon variant. Are you planning to add that? (even if you're not, I'm not against keeping lower_echelon in is_hermite).

Best, Johan

comment:34 in reply to: ↑ 33 Changed 3 years ago by vneiger

Replying to jsrn:

Hi Vincent,

I think you did just bulldoze over my git magic. I'll try to redo it later, but I don't have time right now.

Argh... sorry.

isn't it true that H is in upper-echelon Hermite form exactly when JHJ is in lower-echelon Hermite form, where J is the anti-diagonal unit matrix (i.e. JHJ is H with both columns and rows reversed). Equivalently, the upper-echelon Hermite form of M should be JHJ where H is the lower-echelon Hermite form of JMJ.

Yes, I agree, this seems correct.

Note also that our current hermite_form algorithm does not support computing the upper-echelon variant. Are you planning to add that? (even if you're not, I'm not against keeping lower_echelon in is_hermite).

In fact the current code computes the upper echelon and not the lower, and I am among the ones preferring the lower, this is what led me to put this option in is_hermite despite the existing code.

So I am considering adding support for lower echelon in hermite_form, simply by making sure your remark above is correct and using it in the straightforward way (if lower echelon, then start by replacing M by JMJ, run the current code, and then finish by replacing H by JHJ). Does this sound ok?

Best, Vincent

comment:35 Changed 3 years ago by git

  • Commit changed from cfac2e494b315b1ca507b6d0cdd5c97ac265312a to a5d4b4726b360343da9ff3f0082df77794d4af6c

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

a5d4b47fixed bug in is_weak_popov

comment:36 Changed 3 years ago by vneiger

Ok, the bug is fixed. All seems to work fine now.

There could be a line of work around making previously existing functions work with options in a more unified way: include-zero-vectors and row-wise options for Hermite form, reduced form, weak Popov form, lower-echelon option for Hermite form, etc.

In my opinion this could be a separate ticket about these computations of matrix forms, where we should also consider implementing Popov form computation (probably with Mulders-Storjohann algorithm, starting from a weak Popov matrix).

What do you think?

Best, -- Vincent

comment:37 Changed 3 years ago by vneiger

  • Reviewers changed from Johan Rosenkilde to Johan Rosenkilde, Romain Lebreton, Pascal Giorgi
  • Status changed from needs_work to needs_review

comment:38 Changed 3 years ago by vneiger

  • Cc gh-romainlebreton added

comment:39 Changed 3 years ago by gh-romainlebreton

  • Cc bruno added
  • Reviewers changed from Johan Rosenkilde, Romain Lebreton, Pascal Giorgi to Johan Rosenkilde, Romain Lebreton, Pascal Giorgi, Bruno Grenet

comment:40 follow-up: Changed 3 years ago by gh-romainlebreton

Hey Vincent,

I have started to review your code and I want to give you my first comment since I don't know when I will have time to continue the review. First of all, your code is really nice to read, so thank you for your contribution

General Comments

Add your name as author ?

You should have created multiple small tickets, possibly one by small group of functions

Why import from sage.matrix.matrix2 cimport Matrix if sage.matrix.matrix2.Matrix is never used ? However, it may be faster to call directly sage.matrix.matrix2.Matrix instead of sage.matrix.constructor.Matrix.

Tests fail (see Continuous integration) in src/sage/coding/ because of deprecated row_reduced_form

sage -t src/sage/coding/extended_code.py  # 1 doctest failed
sage -t src/sage/coding/guruswami_sudan/gs_decoder.py  # 1 doctest failed
sage -t src/sage/coding/guruswami_sudan/interpolation.py  # 1 doctest failed
sage -t src/sage/coding/bch.py  # 1 doctest failed

_check_shift_dimension

What is the point of argument 'shifts' being optional ? If you check shifts dimension, you should provide shifts.

column_degrees

You should have a code closer to row_degrees, which is cleaner. In particular, please remove if self.nrows() == 0: ... on line 354

leading_matrix

Suggestion: I am not sure that the part "Going over the Laurent polynomials" is useful to understand the behavior of the function. It is important scientifically to manipulate leading matrices, in particular for understanding the leading matrix of the product, but not so much for its definition.

reduced_form

You should add documentation about option "row_wise"

Best, Romain

comment:41 follow-up: Changed 3 years ago by vdelecroix

Side remark: error message should start with lower case and not have punctuation similarly to

sage: l = []
sage: l[1]
Traceback (most recent call last):
...
IndexError: list index out of range

comment:42 follow-up: Changed 3 years ago by gh-romainlebreton

Hey Vincent,

here is the second and final part of my review. I really like your contribution and I appreciate the effort that you have put into it !

Here are my comments suggestions

_is_empty_popov

l501

if not include_zero_vectors:
   return True

should be

if include_zero_vectors:
   return True

Also your tests should capture this behavior.

is_reduced

  • l518 with $k \leq n$ -> with $k \leq m$ ?
  • l525 with $k \leq m$ -> with $k \leq n$ ?
  • l578 return self._is_empty_popov(row_wise)

I'm not able to tell if it is correct or if it should be return self._is_empty_popov(row_wise,include_zero_vectors)

  • l609 "The definition is similar if working column-wise"

It would be nice to mention here too that "we choose bottommost entry in case of degree equality"

leading_positions

  • l594 "(also known as the pivot index)" -> pivot indices

  • l594 pivot degree -> pivot degrees
  • idem l772
  • l602 "Then the pivot degree of the vector is the degree $\deg(p_j)$"

Is it really $\deg(p_j)$ or should it be $\deg(p_j) + s_j$ instead ?

is_weak_popov

l772 pivot index -> pivot indices

is_popov

l957 not up_to_permutation,

I don't understand why you negate up_to_permutation here. Can you please check ?

is_hermite

Maybe copy the sentence at l74 "In fact, if $d$ is the largest degree ..." relating Popov and Hermite at the end of the comments of the function

Is the "+ 1" in lines 1071 and 1073 really necessary ?

weak_popov_form

l1096 If this is True

Is there a good reason to not implement option row_wise here ?

reduced_form

Should add documentation about option "row_wise"

l1291 If this **is** ``True``

Best,

Romain

comment:43 Changed 3 years ago by gh-romainlebreton

  • Status changed from needs_review to needs_work

comment:44 in reply to: ↑ 40 ; follow-up: Changed 3 years ago by vneiger

Hi Romain,

Thank you very much for your careful review. I have worked on correcting/updating the code, and here are below some answers to specific points.

Replying to gh-romainlebreton:

General Comments

Add your name as author ?

Done.

Why import from sage.matrix.matrix2 cimport Matrix if sage.matrix.matrix2.Matrix is never used ? However, it may be faster to call directly sage.matrix.matrix2.Matrix instead of sage.matrix.constructor.Matrix.

I am not familiar with this: this was already imported in this file prior to that ticket. To avoid breaking something that others wrote, I prefer leaving it as is... but please advise me if you are certain of a solution to make this point cleaner.

Tests fail (see Continuous integration) in src/sage/coding/ because of deprecated row_reduced_form

sage -t src/sage/coding/extended_code.py  # 1 doctest failed
sage -t src/sage/coding/guruswami_sudan/gs_decoder.py  # 1 doctest failed
sage -t src/sage/coding/guruswami_sudan/interpolation.py  # 1 doctest failed
sage -t src/sage/coding/bch.py  # 1 doctest failed

I have modified these files to use the new function name, thank you.

_check_shift_dimension

What is the point of argument 'shifts' being optional ? If you check shifts dimension, you should provide shifts.

This was corrected, thank you. Now, 'shifts' must be given, and is still allowed to be 'None' because this happens to be convenient in other functions.

column_degrees

You should have a code closer to row_degrees, which is cleaner. In particular, please remove if self.nrows() == 0: ... on line 354

This has been done. Thank you.

leading_matrix

Suggestion: I am not sure that the part "Going over the Laurent polynomials" is useful to understand the behavior of the function. It is important scientifically to manipulate leading matrices, in particular for understanding the leading matrix of the product, but not so much for its definition.

Thank you for the suggestion; I agree that this is not essential here and does not add much to the first definition given in the documentation. To make the documentation easier to follow, I removed this remark.

reduced_form

You should add documentation about option "row_wise"

Done, thank you for noticing.

I'll continue right now with your other batch of remarks.

Vincent

comment:45 Changed 3 years ago by git

  • Commit changed from a5d4b4726b360343da9ff3f0082df77794d4af6c to 1bf254ebc97e6d716161a047f0f5549a11e9a235

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

3a62826add author name
56a1427updated author + corrected check_shifts + corrected column_degree
38c2a94simplified documentation of leading_matrix
7b4944cadded row wise in input in documentation of row_reduced
1bf254eupdating code with new function name

comment:46 Changed 3 years ago by git

  • Commit changed from 1bf254ebc97e6d716161a047f0f5549a11e9a235 to 386ce509266cf6ae60fb14c30d29801519ece49a

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

386ce50format of error messages

comment:47 in reply to: ↑ 41 Changed 3 years ago by vneiger

Replying to vdelecroix:

Side remark: error message should start with lower case and not have punctuation similarly to ...

Dear Vincent,

Thank you very much, this has been corrected.

Best,

Vincent

comment:48 in reply to: ↑ 42 ; follow-up: Changed 3 years ago by vneiger

Replying to gh-romainlebreton:

here is the second and final part of my review. I really like your contribution and I appreciate the effort that you have put into it !

Thank you :-) And I greatly appreciate your very careful and useful reviewing work.

_is_empty_popov

l501

if not include_zero_vectors:
   return True

should be

if include_zero_vectors:
   return True

Also your tests should capture this behavior.

Oh, big mistake, now corrected. Thank you for noticing.

is_reduced

  • l518 with $k \leq n$ -> with $k \leq m$ ?
  • l525 with $k \leq m$ -> with $k \leq n$ ?

I think what is written is correct. What you suggest is correct too (the number of nonzero rows is obviously at most m). The fact that the number of nonzero rows must be at most the number n of columns is because a row reduced matrix represents a basis of some submodule of length-n polynomial vectors (such a submodule is free and its basis has at most n elements). In some papers the definition of reduced does not require this, but then it becomes relatively more complicated and makes it more difficult to manipulate reduced forms, while it is not clear to me what advantages this more general definition could bring except possibly in very particular cases.

  • l578 return self._is_empty_popov(row_wise)

I'm not able to tell if it is correct or if it should be return self._is_empty_popov(row_wise,include_zero_vectors)

This should be the latter version indeed, thank you.

  • l609 "The definition is similar if working column-wise"

It would be nice to mention here too that "we choose bottommost entry in case of degree equality"

Done.

leading_positions

  • l594 "(also known as the pivot index)" -> pivot indices

  • l594 pivot degree -> pivot degrees
  • idem l772

There has been a small discussion with Johan on this; in the literature there is a mix of singular and plural. The 'pivot degree' is a tuple of pivot degrees... anyway, for me both are fine, and since we used plural for 'positions' I suppose we should use plural for indices/degrees.

  • l602 "Then the pivot degree of the vector is the degree $\deg(p_j)$"

Is it really $\deg(p_j)$ or should it be $\deg(p_j) + s_j$ instead ?

The pivot degree is the actual degree of the polynomial, and if you add the shift this would be the (shifted) row degree. Both are useful.

is_popov

l957 not up_to_permutation,

I don't understand why you negate up_to_permutation here. Can you please check ?

The argument ordered of is_weak_popov will require that the leading positions are strictly increasing; so it should be false when we are testing that the matrix is in Popov form up to row permutation (and true otherwise).

is_hermite

Maybe copy the sentence at l74 "In fact, if $d$ is the largest degree ..." relating Popov and Hermite at the end of the comments of the function

I incorporated this remark, than you for the suggestion.

Is the "+ 1" in lines 1071 and 1073 really necessary ?

Yes, because of the way we choose leading positions (rightmost nonzero), and because there is an option to have the upper triangular row-wise Hermite form. For example, working row-wise and with upper-triangular Hermite, a 2x2 matrix with rows [X X] and [1 X^2] is (2,0)-Popov but not Hermite; so if we used this shift (2,0) instead of (2+1,0) (where 2 is the degree of the matrix), the Hermite test relying on (2,0)-Popov form would give a wrong answer.

weak_popov_form

l1096 If this is True

Corrected, thank you!

Is there a good reason to not implement option row_wise here ?

This was considered out of the scope of this ticket, since there is anyway some work to be done on these reduction functions (adding Popov form, cleaning existing code using the new functions...).

reduced_form

Should add documentation about option "row_wise"

l1291 If this **is** ``True``

Corrected, thank you!

Please let me know if you have further suggestions for improvements.

Best,

Vincent

comment:49 Changed 3 years ago by git

  • Commit changed from 386ce509266cf6ae60fb14c30d29801519ece49a to c0ffff7f5acfea11709a7647052aa2faa0cb0efa

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

2d85794update doc to reflect updated error messages
f05f3e3corrected is_empty_popov
6078e8ecorrected pivot index / leading positions
1337eaetypo
c0ffff7typo

comment:50 Changed 3 years ago by vneiger

  • Status changed from needs_work to needs_review

comment:51 in reply to: ↑ 44 ; follow-up: Changed 3 years ago by bruno

Replying to vneiger:

Why import from sage.matrix.matrix2 cimport Matrix if sage.matrix.matrix2.Matrix is never used ? However, it may be faster to call directly sage.matrix.matrix2.Matrix instead of sage.matrix.constructor.Matrix.

I am not familiar with this: this was already imported in this file prior to that ticket. To avoid breaking something that others wrote, I prefer leaving it as is... but please advise me if you are certain of a solution to make this point cleaner.

It is actually used (the Matrix from sage.matrix.matrix2) at lines 1199-1200, so it should must be imported. You could also import Matrix from sage.matrix.constructor at the beginning of the file using another name for it as follows: from sage.matrix.constructor import Matrix as Matrix_constructor. I do not know which one is better...

Another point: I read that the renaming of row_reduced_form to reduced_form what discussed between Johan and you. What is the rationale?

Last edited 3 years ago by bruno (previous) (diff)

comment:52 in reply to: ↑ 51 ; follow-up: Changed 3 years ago by vneiger

Hi Bruno,

Replying to bruno:

Replying to vneiger:

Why import from sage.matrix.matrix2 cimport Matrix if sage.matrix.matrix2.Matrix is never used ? However, it may be faster to call directly sage.matrix.matrix2.Matrix instead of sage.matrix.constructor.Matrix.

I am not familiar with this: this was already imported in this file prior to that ticket. To avoid breaking something that others wrote, I prefer leaving it as is... but please advise me if you are certain of a solution to make this point cleaner.

It is actually used (the Matrix from sage.matrix.matrix2) at lines 1199-1200, so it should must be imported. You could also import Matrix from sage.matrix.constructor at the beginning of the file using another name for it as follows: from sage.matrix.constructor import Matrix as Matrix_constructor. I do not know which one is better...

Me neither..

Another point: I read that the renaming of row_reduced_form to reduced_form what discussed between Johan and you. What is the rationale?

Now, the function computes either a row reduced form or a column reduced form, depending on the optional parameter row_wise (default: true). Most other functions are like this in this file; it seemed better and more compact than always having two extremely similar functions named row_X and column_X . There might be other solutions we did not think of...

Vincent

comment:53 in reply to: ↑ 52 ; follow-up: Changed 3 years ago by bruno

Another point: I read that the renaming of row_reduced_form to reduced_form what discussed between Johan and you. What is the rationale?

Now, the function computes either a row reduced form or a column reduced form, depending on the optional parameter row_wise (default: true). Most other functions are like this in this file; it seemed better and more compact than always having two extremely similar functions named row_X and column_X . There might be other solutions we did not think of...

That's fine, but shouldn't the documentation reflect this? I now says Return a row reduced form of this matrix (and "row reduced" is used several other times in the doc).

comment:54 Changed 3 years ago by git

  • Commit changed from c0ffff7f5acfea11709a7647052aa2faa0cb0efa to eb335fcdf824324d37aaf35565288e350d60a580

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

eb335fcimprove doc of reduced_form

comment:55 in reply to: ↑ 53 Changed 3 years ago by vneiger

Replying to bruno:

Another point: I read that the renaming of row_reduced_form to reduced_form what discussed between Johan and you. What is the rationale?

Now, the function computes either a row reduced form or a column reduced form, depending on the optional parameter row_wise (default: true). Most other functions are like this in this file; it seemed better and more compact than always having two extremely similar functions named row_X and column_X . There might be other solutions we did not think of...

That's fine, but shouldn't the documentation reflect this? I now says Return a row reduced form of this matrix (and "row reduced" is used several other times in the doc).

Indeed, for this method the doc was not well written. I have made an attempt at improving it. For the other methods, "row reduced" is indeed used but with the explicit mention "if working row-wise", and with a word about how things differ (or don't) if working column-wise.

comment:56 in reply to: ↑ 48 ; follow-up: Changed 3 years ago by gh-romainlebreton

Replying to vneiger:

Replying to gh-romainlebreton:

Is the "+ 1" in lines 1071 and 1073 really necessary ?

Yes, because of the way we choose leading positions (rightmost nonzero), and because there is an option to have the upper triangular row-wise Hermite form. For example, working row-wise and with upper-triangular Hermite, a 2x2 matrix with rows [X X] and [1 X^2] is (2,0)-Popov but not Hermite; so if we used this shift (2,0) instead of (2+1,0) (where 2 is the degree of the matrix), the Hermite test relying on (2,0)-Popov form would give a wrong answer.

I think that your comment on line 992 had me confused:

"Note that, if $d$ is the largest degree appearing in the Hermite form, then the Hermite form coincide with the shifted Popov form with the shifts $(0,d,2d,\ldots,(n-1)d)$, where $n$ is the column dimension."

Is it really $d$ or should it be $d+1$ in this comment ?

comment:57 in reply to: ↑ 56 ; follow-up: Changed 3 years ago by vneiger

Replying to gh-romainlebreton:

Replying to vneiger:

Replying to gh-romainlebreton:

Is the "+ 1" in lines 1071 and 1073 really necessary ?

Yes, because of the way we choose leading positions (rightmost nonzero), and because there is an option to have the upper triangular row-wise Hermite form. For example, working row-wise and with upper-triangular Hermite, a 2x2 matrix with rows [X X] and [1 X^2] is (2,0)-Popov but not Hermite; so if we used this shift (2,0) instead of (2+1,0) (where 2 is the degree of the matrix), the Hermite test relying on (2,0)-Popov form would give a wrong answer.

I think that your comment on line 992 had me confused:

"Note that, if $d$ is the largest degree appearing in the Hermite form, then the Hermite form coincide with the shifted Popov form with the shifts $(0,d,2d,\ldots,(n-1)d)$, where $n$ is the column dimension."

Is it really $d$ or should it be $d+1$ in this comment ?

I see: in this comment, the "shifted Popov form" is understood as the lower triangular row-wise one, or as the upper triangular column-wise one. For the two others (upper triangular row-wise and lower triangular column-wise), these forms do not coincide anymore as showed by the example in my previous answer; the difference comes from the way pivots are chosen (rightmost nonzero for row-wise, bottommost nonzero for column-wise).

My suggestion is to make this more clear on line 992, as follows: "Note that, working row-wise, if $d$ is the largest degree appearing in the Hermite form, then the Hermite form coincides with the shifted Popov form with the shifts $(0,d,2d,\ldots,(n-1)d)$, where $n$ is the column dimension. (This is valid with lower triangular Hermite forms; if working row-wise but with upper triangular Hermite forms, one would need to take $d+1$ in the shifts instead of $d$.)"

Would this remove any confusion?

Vincent

comment:58 in reply to: ↑ 57 ; follow-up: Changed 3 years ago by gh-romainlebreton

Replying to vneiger:

I see: in this comment, the "shifted Popov form" is understood as the lower triangular row-wise one, or as the upper triangular column-wise one. For the two others (upper triangular row-wise and lower triangular column-wise), these forms do not coincide anymore as showed by the example in my previous answer; the difference comes from the way pivots are chosen (rightmost nonzero for row-wise, bottommost nonzero for column-wise).

My suggestion is to make this more clear on line 992, as follows: "Note that, working row-wise, if $d$ is the largest degree appearing in the Hermite form, then the Hermite form coincides with the shifted Popov form with the shifts $(0,d,2d,\ldots,(n-1)d)$, where $n$ is the column dimension. (This is valid with lower triangular Hermite forms; if working row-wise but with upper triangular Hermite forms, one would need to take $d+1$ in the shifts instead of $d$.)"

Would this remove any confusion?

Hi Vincent, thank you for the explanation, it is now clear for me. I would suggest that you keep it simple in the comments : take $d$ (strictly) greater than all degrees in the matrix (so d would be "d+1") and shifts $(0,d,2d,\ldots,(n-1)d)$.

Best,

R.

comment:59 Changed 3 years ago by git

  • Commit changed from eb335fcdf824324d37aaf35565288e350d60a580 to b67705257dc8f6c8bb15e0baca2fa85e7aef07ca

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

b677052right shift for Hermite form (d > deg(H))

comment:60 in reply to: ↑ 58 ; follow-up: Changed 3 years ago by vneiger

Replying to gh-romainlebreton:

Replying to vneiger:

I see: in this comment, the "shifted Popov form" is understood as the lower triangular row-wise one, or as the upper triangular column-wise one. For the two others (upper triangular row-wise and lower triangular column-wise), these forms do not coincide anymore as showed by the example in my previous answer; the difference comes from the way pivots are chosen (rightmost nonzero for row-wise, bottommost nonzero for column-wise).

My suggestion is to make this more clear on line 992, as follows: "Note that, working row-wise, if $d$ is the largest degree appearing in the Hermite form, then the Hermite form coincides with the shifted Popov form with the shifts $(0,d,2d,\ldots,(n-1)d)$, where $n$ is the column dimension. (This is valid with lower triangular Hermite forms; if working row-wise but with upper triangular Hermite forms, one would need to take $d+1$ in the shifts instead of $d$.)"

Would this remove any confusion?

Hi Vincent, thank you for the explanation, it is now clear for me. I would suggest that you keep it simple in the comments : take $d$ (strictly) greater than all degrees in the matrix (so d would be "d+1") and shifts $(0,d,2d,\ldots,(n-1)d)$.

Best,

R.

Ok, I have chosen this solution which is indeed simpler.

Vincent


New commits:

b677052right shift for Hermite form (d > deg(H))
Last edited 3 years ago by vneiger (previous) (diff)

comment:61 in reply to: ↑ 60 ; follow-up: Changed 3 years ago by gh-romainlebreton

Replying to vneiger:

Ok, I have chosen this solution which is indeed simpler.

Great! However I am still unsure about line 1070

shift = [j*self.degree() + 1 for j in range(self.ncols())]

which gives [1, d + 1, 2*d + 1, 3*d + 1, ...] with d the degree. It does not seem coherent with what we said ; I seems to me that it should be

shift = [j*(self.degree() + 1) for j in range(self.ncols())]

R.

comment:62 in reply to: ↑ 61 Changed 3 years ago by vneiger

Replying to gh-romainlebreton:

Replying to vneiger:

Ok, I have chosen this solution which is indeed simpler.

Great! However I am still unsure about line 1070

shift = [j*self.degree() + 1 for j in range(self.ncols())]

which gives [1, d + 1, 2*d + 1, 3*d + 1, ...] with d the degree. It does not seem coherent with what we said ; I seems to me that it should be

shift = [j*(self.degree() + 1) for j in range(self.ncols())]

R.

Oh... you are totally right. This is a bug, thank you for noticing. Adding 1 to all entries of the shift is useless concerning normal forms and so this shift is equivalent to (0,d,2d,...). Which is not right: I have just actually tested my example above, of a matrix which is not even triangular, and it does wrongly return True :

sage: pR.<x> = GF(7)[]
sage: M = Matrix(pR,2,2,[[x,x],[1,x^2]])
sage: M
[  x   x]
[  1 x^2]
sage: M.is_popov(shifts=[2,0])
True
sage: M.is_hermite()  # defaut is row-wise upper triangular
True

The shift in this example should of course be (d+1,0) = (3,0), while the current code uses (d+1,1) = (3,1), which is equivalent to (2,0) and not the right one as we discussed above.

I'm going to fix this in a commit in a few seconds.

Thank you again.

Vincent

comment:63 Changed 3 years ago by git

  • Commit changed from b67705257dc8f6c8bb15e0baca2fa85e7aef07ca to 17b068c976c976b0035135f9740c0f21ca7990fd

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

17b068ccorrected shift used for is_hermite test

comment:64 Changed 3 years ago by gh-romainlebreton

  • Status changed from needs_review to positive_review

comment:65 follow-up: Changed 3 years ago by gh-romainlebreton

  • Status changed from positive_review to needs_review

In is_hermite, the block SEEALSO requires :: at the end

comment:66 Changed 3 years ago by git

  • Commit changed from 17b068c976c976b0035135f9740c0f21ca7990fd to 5fc5fd6ce0d4ef3871f08c90131d93bb0a9adc61

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

5fc5fd6colon SEEALSO::

comment:67 in reply to: ↑ 65 Changed 3 years ago by vneiger

Replying to gh-romainlebreton:

In is_hermite, the block SEEALSO requires :: at the end

Hi Romain, Thank you for noticing this. This is fixed.

Best,

Vincent

comment:68 Changed 3 years ago by gh-romainlebreton

  • Status changed from needs_review to positive_review

Looks good to me :-)

comment:69 Changed 3 years ago by vbraun

  • Branch changed from u/vneiger/23619_polmat_helper to 5fc5fd6ce0d4ef3871f08c90131d93bb0a9adc61
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.