Helper functions for polynomial matrices

vneiger commented 7 years ago

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

CC: @johanrosenkilde @romainlebreton @bgrenet

Component: algebra

Keywords: matrix

Author: Vincent Neiger

Branch/Commit: 5fc5fd6

Reviewer: Johan Rosenkilde, Romain Lebreton, Pascal Giorgi, Bruno Grenet

Issue created by migration from https://trac.sagemath.org/ticket/23619

vneiger commented 7 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,6 @@
 Functions:
 - row/column degree,
+- pivot (row/column),
 - degree matrix,
 - leading matrix (row/column),
 - is_popov  (row/column),

vneiger commented 7 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,5 @@
 Functions:
+- degree,
 - row/column degree,
 - pivot (row/column),
 - degree matrix,

vneiger commented 7 years ago

Branch: u/vneiger/23619_polmat_helper

vneiger commented 7 years ago

Commit: ec172a4

vneiger commented 7 years ago

comment:4

Pushed the first function. Not ready for review.

New commits:

ec172a4 degree matrix function working

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from ec172a4 to 4aa4338

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

4aa4338 improved degree_matrix documentation

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 4aa4338 to 10be03d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

10be03d function and doc degree of a matrix

vneiger commented 7 years ago

comment:7

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 10be03d to 68de063

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

af59287 function and doc for is_reduced

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 68de063 to af59287

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from af59287 to 205e188

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

c427947 class document, and cleaner documentation for methods

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 205e188 to c427947

johanrosenkilde commented 7 years ago

comment:12

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<sup>{s_1},...,x</sup>{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?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from c427947 to fff979b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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`

vneiger commented 7 years ago

comment:14

Thank you for your numerous comments.

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

Replying to @johanrosenkilde:

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from fff979b to 817b81c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

`3d5797d`	`shifts as list/vector: ok now`
`817b81c`	`todo`

johanrosenkilde commented 7 years ago

comment:16

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 817b81c to 660ab43

johanrosenkilde commented 7 years ago

Description changed:

--- 
+++ 
@@ -1,8 +1,8 @@
 Functions:
 - degree,
-- row/column degree,
-- pivot (row/column),
-- degree matrix,
-- leading matrix (row/column),
-- is_popov  (row/column),
-- is_reduced (row/column).
+- `row_degree`, `column_degree`,
+- `row_pivots`, `column_pivots`,
+- `degree_matrix`,
+- `row_leading_matrix`, `column_leading_matrix`,
+- `is_popov`  (row/column),
+- `is_reduced` (row/column).

johanrosenkilde commented 7 years ago

comment:18

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

johanrosenkilde commented 7 years ago

Description changed:

--- 
+++ 
@@ -1,6 +1,6 @@
 Functions:
 - degree,
-- `row_degree`, `column_degree`,
+- `row_degrees`, `column_degrees`,
 - `row_pivots`, `column_pivots`,
 - `degree_matrix`,
 - `row_leading_matrix`, `column_leading_matrix`,

johanrosenkilde commented 7 years ago

comment:19

Let's go plural.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 660ab43 to 72fe310

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 72fe310 to 7f6e36e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 7f6e36e to 9ed9b40

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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`

johanrosenkilde commented 6 years ago

Changed branch from u/vneiger/23619_polmat_helper to u/jsrn/23619_polmat_helper

johanrosenkilde commented 6 years ago

Changed commit from 9ed9b40 to 7af4cca

johanrosenkilde commented 6 years ago

comment:24

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`

johanrosenkilde commented 6 years ago

comment:25

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 2n 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 20 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

johanrosenkilde commented 6 years ago

Reviewer: Johan Rosenkilde

johanrosenkilde commented 6 years ago

Author: Vincent Neiger

johanrosenkilde commented 6 years ago

Dependencies: 24640

johanrosenkilde commented 6 years ago

comment:26

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 7af4cca to 4830af1

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 4830af1 to 9eaf1f5

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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

9eaf1f5 Spaces around operators

johanrosenkilde commented 6 years ago

comment:29

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.

sagemath / sage

Helper functions for polynomial matrices #23619