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:  sage8.1 
Component:  algebra  Keywords:  matrix 
Cc:  jsrn, ghromainlebreton, 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: 
Description (last modified by )
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
 Description modified (diff)
comment:2 Changed 4 years ago by
 Description modified (diff)
comment:3 Changed 4 years ago by
 Branch set to u/vneiger/23619_polmat_helper
comment:4 Changed 4 years ago by
 Commit set to ec172a430570bce97ff58ee520248ac9d5582145
comment:5 Changed 4 years ago by
 Commit changed from ec172a430570bce97ff58ee520248ac9d5582145 to 4aa4338638fc25cf0dfb2824ae0feb4bd82b0325
Branch pushed to git repo; I updated commit sha1. New commits:
4aa4338  improved degree_matrix documentation

comment:6 Changed 4 years ago by
 Commit changed from 4aa4338638fc25cf0dfb2824ae0feb4bd82b0325 to 10be03dd10e85f406f9406823bdc365cd41c1c95
Branch pushed to git repo; I updated commit sha1. New commits:
10be03d  function and doc degree of a matrix

comment:7 Changed 4 years ago by
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
 Commit changed from 10be03dd10e85f406f9406823bdc365cd41c1c95 to 68de063497c111a12313d396361ebdb5db9fd963
comment:9 Changed 4 years ago by
 Commit changed from 68de063497c111a12313d396361ebdb5db9fd963 to af59287329f6c097a4d4b21f2c559912b5e2b2e8
Branch pushed to git repo; I updated commit sha1. New commits:
af59287  function and doc for is_reduced

comment:10 Changed 4 years ago by
 Commit changed from af59287329f6c097a4d4b21f2c559912b5e2b2e8 to 205e188377dccab4ce96a999a2b1372eca75cc56
comment:11 Changed 4 years ago by
 Commit changed from 205e188377dccab4ce96a999a2b1372eca75cc56 to c42794798eeb2e1e6d34c83c039cc32e48fb53f5
Branch pushed to git repo; I updated commit sha1. New commits:
c427947  class document, and cleaner documentation for methods

comment:12 followup: ↓ 14 Changed 4 years ago by
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 usethis 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 degreeNone
? Such a matrix has e.g. rank 0 and characteristic polynomial 1. Similar question forrowdegree
.
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 ofdefect
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 defineLM_s(M) := LM(M diag(x^{s_1},...,x^{s_n})
which I find easier to parse.
leading_matrix
: I don't think theself[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 ... leftmultiplying", add "(resp. rightmultiplying)".
pivot
: should the pivot degrees only be returned if the user wishes it (by setting a flagreturn_degree=False
)?
is_ordered_weak_popov
: should this be merged withis_weak_popov
by giving the latter an optional flagordered
?
comment:13 Changed 4 years ago by
 Commit changed from c42794798eeb2e1e6d34c83c039cc32e48fb53f5 to fff979b9365a34a650652c542b9e19644e834d28
comment:14 in reply to: ↑ 12 Changed 4 years ago by
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 degreeNone
? Such a matrix has e.g. rank 0 and characteristic polynomial 1. Similar question forrowdegree
.
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
 Commit changed from fff979b9365a34a650652c542b9e19644e834d28 to 817b81c6d4bc570ff5107c45501d63b14cf32919
comment:16 Changed 4 years ago by
Hi, looking better and better :)
leading_matrix
, perhaps elsewhere: Don't put parentheses around the condition of an ifstatement Prefer
a is None
compared toa == None
.  Class doc: forget
:meth:
forleading_matrix
reference.
Things we discussed face2face:
 pivot > leading_positions
 add order_by_degree and order_by_leading_position
 Raise ValueError? on zerorow or zerocolumn matrices
 Check lengths of shifts everywhere
comment:17 Changed 4 years ago by
 Commit changed from 817b81c6d4bc570ff5107c45501d63b14cf32919 to 660ab43b9fc8cda4a74f0a10457b00b64c33006e
Branch pushed to git repo; I updated commit sha1. New commits:
fe37dee  row_reduced > reduced, deprecation warning

91db615  check shift length

0545723  check shift length

e3064b0  pivot index > leading positions

ee2f999  some small fixes

e7d646f  pivot index > leading positions

660ab43  degrees and leading positions for empty matrices

comment:18 Changed 4 years ago by
 Description modified (diff)
Changed some names in the description, as discussed f2f. The code still needs to be updated.
comment:20 Changed 3 years ago by
 Commit changed from 660ab43b9fc8cda4a74f0a10457b00b64c33006e to 72fe310d3d7ecb10c9ed052a2d2f6ded4beae327
comment:21 Changed 3 years ago by
 Commit changed from 72fe310d3d7ecb10c9ed052a2d2f6ded4beae327 to 7f6e36ebdb652d41dd343ff54697a93e4c7be5f2
comment:22 Changed 3 years ago by
 Commit changed from 7f6e36ebdb652d41dd343ff54697a93e4c7be5f2 to 9ed9b400de4dc9586112ba7091788cc586880b31
Branch pushed to git repo; I updated commit sha1. New commits:
3a336c9  working on is_hermite

a266d99  now, in ordered weak Popov and in Popov the zero rows must appear at the end (bottom if rowwise, righthand side if columnwise)

dd920d4  is_hermite now works, it simply calls is_popov with the right shift

92356cb  is_hermite cleaned, lower_echelon option correct now

de58683  add test to support empty matrices in is_{hermite,popov,weak_popov,reduced }

9ed9b40  added some SEEALSO blocks

comment:23 Changed 3 years ago by
 Branch changed from u/vneiger/23619_polmat_helper to u/jsrn/23619_polmat_helper
comment:24 Changed 3 years ago by
 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:
c44832e  Fixed some doctests

5d56351  Classical ReedSolomon codes

19ba6f5  Fixed small doctest failure

37515a0  Merge branch 'u/vneiger/23619_polmat_helper' of git://trac.sagemath.org/sage into 23619_polmat_helper

c67c7a3  Spaces around operators

805ecd7  Plural row/col degrees in various doc text

bb7f3a6  Fixed a SEEALSO

03cf1a8  Simplified some logic in is_reduced

3a03af4  Improved reduced_form doc to conform to the rest of the file. A few other small fixes

7af4cca  Improved doc and examples of weak_popov_form

comment:25 followup: ↓ 32 Changed 3 years ago by
 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 inis_*_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
argumentlower_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 byM.permute_rows(Permutation(range(M.nrows(),0,1)))
.
 If you keep
lower_echelon=True
, there should be an example using it where the answer isTrue
.
Also, I like your fix for allowing other row orderings in is_popov
!
Best, Johan
comment:26 Changed 3 years ago by
 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
 Commit changed from 7af4cca233718feaf727265e7cde9114ce505d4d to 4830af1400ff1f18c436fdefb1851072d05150f5
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
129aa97  Merge commit '9ed9b40' into 23619_polmat_helper_nodep

7b51228  Plural row/col degrees in various doc text

b70bb38  Fixed a SEEALSO

376759f  Simplified some logic in is_reduced

0a14228  Improved reduced_form doc to conform to the rest of the file. A few other small fixes

4830af1  Improved doc and examples of weak_popov_form

comment:28 Changed 3 years ago by
 Commit changed from 4830af1400ff1f18c436fdefb1851072d05150f5 to 9eaf1f558d8fe16c91f61ca04a994ccce3735621
Branch pushed to git repo; I updated commit sha1. New commits:
9eaf1f5  Spaces around operators

comment:29 Changed 3 years ago by
 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, cherrypick my commits). Except that I screwed up and cherrypicked one commit too little (doing git cherrypick <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
 Branch changed from u/jsrn/23619_polmat_helper to u/vneiger/23619_polmat_helper
comment:31 Changed 3 years ago by
 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:
5d56351  Classical ReedSolomon codes

19ba6f5  Fixed small doctest failure

37515a0  Merge branch 'u/vneiger/23619_polmat_helper' of git://trac.sagemath.org/sage into 23619_polmat_helper

c67c7a3  Spaces around operators

805ecd7  Plural row/col degrees in various doc text

bb7f3a6  Fixed a SEEALSO

03cf1a8  Simplified some logic in is_reduced

3a03af4  Improved reduced_form doc to conform to the rest of the file. A few other small fixes

7af4cca  Improved doc and examples of weak_popov_form

cfac2e4  some fixes + is_empty_popov now hidden

comment:32 in reply to: ↑ 25 ; followup: ↓ 33 Changed 3 years ago by
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 inis_*_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
argumentlower_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 byM.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 isTrue
.
Done!
This made me realise that there is a bug with zero rows in is_weak_popov. I will fix this today.
Best,
Vincent
comment:33 in reply to: ↑ 32 ; followup: ↓ 34 Changed 3 years ago by
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 inis_*_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
argumentlower_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 byM.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 upperechelon Hermite form exactly when JHJ
is in lowerechelon Hermite form, where J
is the antidiagonal unit matrix (i.e. JHJ
is H
with both columns and rows reversed). Equivalently, the upperechelon Hermite form of M
should be JHJ
where H
is the lowerechelon Hermite form of JMJ
.
Note also that our current hermite_form
algorithm does not support computing the upperechelon 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
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 upperechelon Hermite form exactly whenJHJ
is in lowerechelon Hermite form, whereJ
is the antidiagonal unit matrix (i.e.JHJ
isH
with both columns and rows reversed). Equivalently, the upperechelon Hermite form ofM
should beJHJ
whereH
is the lowerechelon Hermite form ofJMJ
.
Yes, I agree, this seems correct.
Note also that our current
hermite_form
algorithm does not support computing the upperechelon variant. Are you planning to add that? (even if you're not, I'm not against keepinglower_echelon
inis_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
 Commit changed from cfac2e494b315b1ca507b6d0cdd5c97ac265312a to a5d4b4726b360343da9ff3f0082df77794d4af6c
Branch pushed to git repo; I updated commit sha1. New commits:
a5d4b47  fixed bug in is_weak_popov

comment:36 Changed 3 years ago by
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: includezerovectors and rowwise options for Hermite form, reduced form, weak Popov form, lowerechelon 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 MuldersStorjohann algorithm, starting from a weak Popov matrix).
What do you think?
Best,  Vincent
comment:37 Changed 3 years ago by
 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
 Cc ghromainlebreton added
comment:39 Changed 3 years ago by
 Cc bruno added
 Reviewers changed from Johan Rosenkilde, Romain Lebreton, Pascal Giorgi to Johan Rosenkilde, Romain Lebreton, Pascal Giorgi, Bruno Grenet
comment:40 followup: ↓ 44 Changed 3 years ago by
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 followup: ↓ 47 Changed 3 years ago by
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 followup: ↓ 48 Changed 3 years ago by
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 columnwise"
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
 Status changed from needs_review to needs_work
comment:44 in reply to: ↑ 40 ; followup: ↓ 51 Changed 3 years ago by
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 ghromainlebreton:
General Comments
Add your name as author ?
Done.
Why import
from sage.matrix.matrix2 cimport Matrix
ifsage.matrix.matrix2.Matrix
is never used ? However, it may be faster to call directlysage.matrix.matrix2.Matrix
instead ofsage.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
 Commit changed from a5d4b4726b360343da9ff3f0082df77794d4af6c to 1bf254ebc97e6d716161a047f0f5549a11e9a235
Branch pushed to git repo; I updated commit sha1. New commits:
3a62826  add author name

56a1427  updated author + corrected check_shifts + corrected column_degree

38c2a94  simplified documentation of leading_matrix

7b4944c  added row wise in input in documentation of row_reduced

1bf254e  updating code with new function name

comment:46 Changed 3 years ago by
 Commit changed from 1bf254ebc97e6d716161a047f0f5549a11e9a235 to 386ce509266cf6ae60fb14c30d29801519ece49a
Branch pushed to git repo; I updated commit sha1. New commits:
386ce50  format of error messages

comment:47 in reply to: ↑ 41 Changed 3 years ago by
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 ; followup: ↓ 56 Changed 3 years ago by
Replying to ghromainlebreton:
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 Trueshould be
if include_zero_vectors: return TrueAlso 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 lengthn 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 columnwise"
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 rowwise Hermite form. For example, working rowwise and with uppertriangular 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
 Commit changed from 386ce509266cf6ae60fb14c30d29801519ece49a to c0ffff7f5acfea11709a7647052aa2faa0cb0efa
comment:50 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:51 in reply to: ↑ 44 ; followup: ↓ 52 Changed 3 years ago by
Replying to vneiger:
Why import
from sage.matrix.matrix2 cimport Matrix
ifsage.matrix.matrix2.Matrix
is never used ? However, it may be faster to call directlysage.matrix.matrix2.Matrix
instead ofsage.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 11991200, 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?
comment:52 in reply to: ↑ 51 ; followup: ↓ 53 Changed 3 years ago by
Hi Bruno,
Replying to bruno:
Replying to vneiger:
Why import
from sage.matrix.matrix2 cimport Matrix
ifsage.matrix.matrix2.Matrix
is never used ? However, it may be faster to call directlysage.matrix.matrix2.Matrix
instead ofsage.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
fromsage.matrix.matrix2
) at lines 11991200, so itshouldmust be imported. You could also importMatrix
fromsage.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
toreduced_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 ; followup: ↓ 55 Changed 3 years ago by
Another point: I read that the renaming of
row_reduced_form
toreduced_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 namedrow_X
andcolumn_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
 Commit changed from c0ffff7f5acfea11709a7647052aa2faa0cb0efa to eb335fcdf824324d37aaf35565288e350d60a580
Branch pushed to git repo; I updated commit sha1. New commits:
eb335fc  improve doc of reduced_form

comment:55 in reply to: ↑ 53 Changed 3 years ago by
Replying to bruno:
Another point: I read that the renaming of
row_reduced_form
toreduced_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 namedrow_X
andcolumn_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 rowwise", and with a word about how things differ (or don't) if working columnwise.
comment:56 in reply to: ↑ 48 ; followup: ↓ 57 Changed 3 years ago by
Replying to vneiger:
Replying to ghromainlebreton:
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 rowwise Hermite form. For example, working rowwise and with uppertriangular 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,(n1)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 ; followup: ↓ 58 Changed 3 years ago by
Replying to ghromainlebreton:
Replying to vneiger:
Replying to ghromainlebreton:
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 rowwise Hermite form. For example, working rowwise and with uppertriangular 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,(n1)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 rowwise one, or as the upper triangular columnwise one. For the two others (upper triangular rowwise and lower triangular columnwise), 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 rowwise, bottommost nonzero for columnwise).
My suggestion is to make this more clear on line 992, as follows: "Note that, working rowwise, 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,(n1)d)$, where $n$ is the column dimension. (This is valid with lower triangular Hermite forms; if working rowwise 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 ; followup: ↓ 60 Changed 3 years ago by
Replying to vneiger:
I see: in this comment, the "shifted Popov form" is understood as the lower triangular rowwise one, or as the upper triangular columnwise one. For the two others (upper triangular rowwise and lower triangular columnwise), 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 rowwise, bottommost nonzero for columnwise).
My suggestion is to make this more clear on line 992, as follows: "Note that, working rowwise, 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,(n1)d)$, where $n$ is the column dimension. (This is valid with lower triangular Hermite forms; if working rowwise 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,(n1)d)$.
Best,
R.
comment:59 Changed 3 years ago by
 Commit changed from eb335fcdf824324d37aaf35565288e350d60a580 to b67705257dc8f6c8bb15e0baca2fa85e7aef07ca
Branch pushed to git repo; I updated commit sha1. New commits:
b677052  right shift for Hermite form (d > deg(H))

comment:60 in reply to: ↑ 58 ; followup: ↓ 61 Changed 3 years ago by
Replying to ghromainlebreton:
Replying to vneiger:
I see: in this comment, the "shifted Popov form" is understood as the lower triangular rowwise one, or as the upper triangular columnwise one. For the two others (upper triangular rowwise and lower triangular columnwise), 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 rowwise, bottommost nonzero for columnwise).
My suggestion is to make this more clear on line 992, as follows: "Note that, working rowwise, 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,(n1)d)$, where $n$ is the column dimension. (This is valid with lower triangular Hermite forms; if working rowwise 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,(n1)d)$.
Best,
R.
Ok, I have chosen this solution which is indeed simpler.
Vincent
New commits:
b677052  right shift for Hermite form (d > deg(H))

comment:61 in reply to: ↑ 60 ; followup: ↓ 62 Changed 3 years ago by
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
Replying to ghromainlebreton:
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 rowwise 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
 Commit changed from b67705257dc8f6c8bb15e0baca2fa85e7aef07ca to 17b068c976c976b0035135f9740c0f21ca7990fd
Branch pushed to git repo; I updated commit sha1. New commits:
17b068c  corrected shift used for is_hermite test

comment:64 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:65 followup: ↓ 67 Changed 3 years ago by
 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
 Commit changed from 17b068c976c976b0035135f9740c0f21ca7990fd to 5fc5fd6ce0d4ef3871f08c90131d93bb0a9adc61
Branch pushed to git repo; I updated commit sha1. New commits:
5fc5fd6  colon SEEALSO::

comment:67 in reply to: ↑ 65 Changed 3 years ago by
Replying to ghromainlebreton:
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
 Status changed from needs_review to positive_review
Looks good to me :)
comment:69 Changed 3 years ago by
 Branch changed from u/vneiger/23619_polmat_helper to 5fc5fd6ce0d4ef3871f08c90131d93bb0a9adc61
 Resolution set to fixed
 Status changed from positive_review to closed
Pushed the first function. Not ready for review.
New commits:
degree matrix function working