Opened 5 years ago
Closed 5 years ago
#23619 closed enhancement (fixed)
Helper functions for polynomial matrices
Reported by: | Vincent Neiger | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.1 |
Component: | algebra | Keywords: | matrix |
Cc: | Johan Rosenkilde, Romain Lebreton, Bruno Grenet | 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 5 years ago by
Description: | modified (diff) |
---|
comment:2 Changed 5 years ago by
Description: | modified (diff) |
---|
comment:3 Changed 5 years ago by
Branch: | → u/vneiger/23619_polmat_helper |
---|
comment:4 Changed 5 years ago by
Commit: | → ec172a430570bce97ff58ee520248ac9d5582145 |
---|
comment:5 Changed 5 years ago by
Commit: | ec172a430570bce97ff58ee520248ac9d5582145 → 4aa4338638fc25cf0dfb2824ae0feb4bd82b0325 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
4aa4338 | improved degree_matrix documentation
|
comment:6 Changed 5 years ago by
Commit: | 4aa4338638fc25cf0dfb2824ae0feb4bd82b0325 → 10be03dd10e85f406f9406823bdc365cd41c1c95 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
10be03d | function and doc degree of a matrix
|
comment:7 Changed 5 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 5 years ago by
Commit: | 10be03dd10e85f406f9406823bdc365cd41c1c95 → 68de063497c111a12313d396361ebdb5db9fd963 |
---|
comment:9 Changed 5 years ago by
Commit: | 68de063497c111a12313d396361ebdb5db9fd963 → af59287329f6c097a4d4b21f2c559912b5e2b2e8 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
af59287 | function and doc for is_reduced
|
comment:10 Changed 5 years ago by
Commit: | af59287329f6c097a4d4b21f2c559912b5e2b2e8 → 205e188377dccab4ce96a999a2b1372eca75cc56 |
---|
comment:11 Changed 5 years ago by
Commit: | 205e188377dccab4ce96a999a2b1372eca75cc56 → c42794798eeb2e1e6d34c83c039cc32e48fb53f5 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
c427947 | class document, and cleaner documentation for methods
|
comment:12 follow-up: 14 Changed 5 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 forrow-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 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 ... left-multiplying", add "(resp. right-multiplying)".
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 5 years ago by
Commit: | c42794798eeb2e1e6d34c83c039cc32e48fb53f5 → fff979b9365a34a650652c542b9e19644e834d28 |
---|
comment:14 Changed 5 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 forrow-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 5 years ago by
Commit: | fff979b9365a34a650652c542b9e19644e834d28 → 817b81c6d4bc570ff5107c45501d63b14cf32919 |
---|
comment:16 Changed 5 years ago by
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 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 zero-row or zero-column matrices
- Check lengths of shifts everywhere
comment:17 Changed 5 years ago by
Commit: | 817b81c6d4bc570ff5107c45501d63b14cf32919 → 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 5 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 5 years ago by
Commit: | 660ab43b9fc8cda4a74f0a10457b00b64c33006e → 72fe310d3d7ecb10c9ed052a2d2f6ded4beae327 |
---|
comment:21 Changed 5 years ago by
Commit: | 72fe310d3d7ecb10c9ed052a2d2f6ded4beae327 → 7f6e36ebdb652d41dd343ff54697a93e4c7be5f2 |
---|
comment:22 Changed 5 years ago by
Commit: | 7f6e36ebdb652d41dd343ff54697a93e4c7be5f2 → 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 row-wise, right-hand side if column-wise)
|
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 5 years ago by
Branch: | u/vneiger/23619_polmat_helper → u/jsrn/23619_polmat_helper |
---|
comment:24 Changed 5 years ago by
Commit: | 9ed9b400de4dc9586112ba7091788cc586880b31 → 7af4cca233718feaf727265e7cde9114ce505d4d |
---|---|
Status: | new → needs_review |
Author forgot to set needs_review
(but said so in private conversation)
Last 10 new commits:
c44832e | Fixed some doc-tests
|
5d56351 | Classical Reed-Solomon codes
|
19ba6f5 | Fixed small doc-test 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 follow-up: 32 Changed 5 years ago by
Authors: | → Vincent Neiger |
---|---|
Reviewers: | → Johan Rosenkilde |
Status: | needs_review → 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 5 years ago by
Dependencies: | → 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 5 years ago by
Commit: | 7af4cca233718feaf727265e7cde9114ce505d4d → 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 5 years ago by
Commit: | 4830af1400ff1f18c436fdefb1851072d05150f5 → 9eaf1f558d8fe16c91f61ca04a994ccce3735621 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
9eaf1f5 | Spaces around operators
|
comment:29 Changed 5 years ago by
Dependencies: | 24640 |
---|
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 5 years ago by
Branch: | u/jsrn/23619_polmat_helper → u/vneiger/23619_polmat_helper |
---|
comment:31 Changed 5 years ago by
Commit: | 9eaf1f558d8fe16c91f61ca04a994ccce3735621 → 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 Reed-Solomon codes
|
19ba6f5 | Fixed small doc-test 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 follow-up: 33 Changed 5 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 follow-up: 34 Changed 5 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 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 Changed 5 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 upper-echelon Hermite form exactly whenJHJ
is in lower-echelon Hermite form, whereJ
is the anti-diagonal unit matrix (i.e.JHJ
isH
with both columns and rows reversed). Equivalently, the upper-echelon Hermite form ofM
should beJHJ
whereH
is the lower-echelon Hermite form ofJMJ
.
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 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 5 years ago by
Commit: | cfac2e494b315b1ca507b6d0cdd5c97ac265312a → a5d4b4726b360343da9ff3f0082df77794d4af6c |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
a5d4b47 | fixed bug in is_weak_popov
|
comment:36 Changed 5 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: 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 5 years ago by
Reviewers: | Johan Rosenkilde → Johan Rosenkilde, Romain Lebreton, Pascal Giorgi |
---|---|
Status: | needs_work → needs_review |
comment:38 Changed 5 years ago by
Cc: | Romain Lebreton added |
---|
comment:39 Changed 5 years ago by
Cc: | Bruno Grenet added |
---|---|
Reviewers: | Johan Rosenkilde, Romain Lebreton, Pascal Giorgi → Johan Rosenkilde, Romain Lebreton, Pascal Giorgi, Bruno Grenet |
comment:40 follow-up: 44 Changed 5 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 follow-up: 47 Changed 5 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 follow-up: 48 Changed 5 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 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 5 years ago by
Status: | needs_review → needs_work |
---|
comment:44 follow-up: 51 Changed 5 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 gh-romainlebreton:
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 5 years ago by
Commit: | a5d4b4726b360343da9ff3f0082df77794d4af6c → 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 5 years ago by
Commit: | 1bf254ebc97e6d716161a047f0f5549a11e9a235 → 386ce509266cf6ae60fb14c30d29801519ece49a |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
386ce50 | format of error messages
|
comment:47 Changed 5 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 follow-up: 56 Changed 5 years ago by
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 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 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 5 years ago by
Commit: | 386ce509266cf6ae60fb14c30d29801519ece49a → c0ffff7f5acfea11709a7647052aa2faa0cb0efa |
---|
comment:50 Changed 5 years ago by
Status: | needs_work → needs_review |
---|
comment:51 follow-up: 52 Changed 5 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 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?
comment:52 follow-up: 53 Changed 5 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 1199-1200, 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 follow-up: 55 Changed 5 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 5 years ago by
Commit: | c0ffff7f5acfea11709a7647052aa2faa0cb0efa → eb335fcdf824324d37aaf35565288e350d60a580 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
eb335fc | improve doc of reduced_form
|
comment:55 Changed 5 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 row-wise", and with a word about how things differ (or don't) if working column-wise.
comment:56 follow-up: 57 Changed 5 years ago by
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 follow-up: 58 Changed 5 years ago by
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 follow-up: 60 Changed 5 years ago by
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 5 years ago by
Commit: | eb335fcdf824324d37aaf35565288e350d60a580 → b67705257dc8f6c8bb15e0baca2fa85e7aef07ca |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
b677052 | right shift for Hermite form (d > deg(H))
|
comment:60 follow-up: 61 Changed 5 years ago by
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:
b677052 | right shift for Hermite form (d > deg(H))
|
comment:61 follow-up: 62 Changed 5 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 Changed 5 years ago by
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 5 years ago by
Commit: | b67705257dc8f6c8bb15e0baca2fa85e7aef07ca → 17b068c976c976b0035135f9740c0f21ca7990fd |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
17b068c | corrected shift used for is_hermite test
|
comment:64 Changed 5 years ago by
Status: | needs_review → positive_review |
---|
comment:65 follow-up: 67 Changed 5 years ago by
Status: | positive_review → needs_review |
---|
In is_hermite, the block SEEALSO requires :: at the end
comment:66 Changed 5 years ago by
Commit: | 17b068c976c976b0035135f9740c0f21ca7990fd → 5fc5fd6ce0d4ef3871f08c90131d93bb0a9adc61 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
5fc5fd6 | colon SEEALSO::
|
comment:67 Changed 5 years ago by
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:69 Changed 5 years ago by
Branch: | u/vneiger/23619_polmat_helper → 5fc5fd6ce0d4ef3871f08c90131d93bb0a9adc61 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Pushed the first function. Not ready for review.
New commits:
degree matrix function working