Opened 4 years ago

Closed 3 years ago

# Helper functions for polynomial matrices

Reported by: Owned by: vneiger major sage-8.1 algebra matrix jsrn, gh-romainlebreton, bruno Vincent Neiger Johan Rosenkilde, Romain Lebreton, Pascal Giorgi, Bruno Grenet N/A 5fc5fd6 5fc5fd6ce0d4ef3871f08c90131d93bb0a9adc61

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

### 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:

 ​ec172a4 degree 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:

 ​4aa4338 improved 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:

 ​10be03d function 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:

 ​0fd8340 function and doc for column degree and row degree ​68de063 function 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:

 ​af59287 function 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:

 ​baab67f small correction for degree: case of empty matrix ​96c7e5a testing corner cases with <> matrices ​205e188 is_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:

 ​c427947 class document, and cleaner documentation for methods

### comment:12 follow-up: ↓ 14 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:  ​7e0f5e8 added examples for is_ordered_weak_popov ​fff979b Johan'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:  ​3d5797d shifts as list/vector: ok now ​817b81c todo ### 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:  ​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 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:  ​c6da217 plural for row degree / column degree ​72fe310 now 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 ​8064d7b is_popov now accepts zero rows + option for up-to-permutation test ​489344a remove old code ​7f6e36e small 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:  ​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 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:  ​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 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:  ​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 git • 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 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:  ​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 in reply to: ↑ 25 ; follow-up: ↓ 33 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: ↓ 34 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:  ​a5d4b47 fixed 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: ↓ 44 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: ↓ 47 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: ↓ 48 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: ↓ 51 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:  ​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 git • 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 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: ↓ 56 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:  ​2d85794 update doc to reflect updated error messages ​f05f3e3 corrected is_empty_popov ​6078e8e corrected pivot index / leading positions ​1337eae typo ​c0ffff7 typo ### comment:50 Changed 3 years ago by vneiger • Status changed from needs_work to needs_review ### comment:51 in reply to: ↑ 44 ; follow-up: ↓ 52 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: ↓ 53 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: ↓ 55 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:  ​eb335fc improve 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: ↓ 57 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: ↓ 58 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: ↓ 60 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:  ​b677052 right shift for Hermite form (d > deg(H)) ### comment:60 in reply to: ↑ 58 ; follow-up: ↓ 61 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:

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

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

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

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:

 ​17b068c corrected 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: ↓ 67 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:

 ​5fc5fd6 colon SEEALSO::

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

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.