Compute J-ideal of a matrix #21992

cheuberg · 2016-11-29T16:36:50Z

In [HR2016], an algorithm for computing the J-ideal of a matrix is given: Given a matrix B over a principal ideal domain R and an ideal (a), the (a) ideal of B consists of those polynomials over R[X] which map B to a matrix in M_n((a)).

This ticket contains the accompanying code.

[HR2016] Clemens Heuberger and Roswitha Rissner, Computing J-Ideals of a Matrix Over a Principal Ideal Domain, [https://arxiv.org/abs/1611.10308 arXiv 1611.10308 [math.AC]], 2016.

CC: @dkrenn @rosirot

Component: linear algebra

Author: Clemens Heuberger, Roswitha Rissner

Branch/Commit: 079f8f1

Reviewer: Daniel Krenn, Travis Scrimshaw

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

The text was updated successfully, but these errors were encountered:

cheuberg · 2016-11-30T14:31:52Z

Last 10 new commits:

`c7837e7`	`adapt import statements`
`56028e4`	`Cache G and previous nu`
`458067e`	`Avoid computing lifting twice for debugging`
`902c344`	`Implement method integer_valued_polynomials`
`c63f37b`	`Improve documentation`
`0291daa`	`Merge stand alone branch 't/21992/compute-j-ideal'`
`5ebd5e2`	`Trac #21992: fix doctests after integration into sage`
`b9e7acf`	`Trac #21992: include into documentation`
`0324154`	`Trac #21992: Fix indentations`
`c3433e2`	`Trac #21992: make compute_J_ideal accessible`

cheuberg · 2016-11-30T14:31:52Z

Commit: c3433e2

cheuberg · 2016-11-30T14:31:52Z

Branch: u/cheuberg/compute-j-ideal

sagetrac-git · 2016-12-01T06:35:19Z

Changed commit from c3433e2 to 78f6f33

sagetrac-git · 2016-12-01T06:35:19Z

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

`78f6f33`	`Trac #21992: insert arXiv link`

dkrenn · 2017-01-01T16:00:17Z

Reviewer: Daniel Krenn

dkrenn · 2017-01-01T16:00:17Z

comment:4

Code looks good, is extensively tested, docs are fine. I only found the following minor issues / suggestions:

correct the 2 lines with whitespace errors
Python 3:
- imports at top of file
```
from __future__ import print_function
from __future__ import absolute_import
```
AFAIK, we put this now in all SageMath-files which are already
Python3-compatibel
- print_function in doctests (simply use print(...),
  which works in Python2 and 3
- iteritems/iterkeys: use e.g. six
refactor imports to be more locally:
e.g. heapq is only needed in one function/method, so you can put it there.
I tend to use file-global imports only when really needed there (e.g. SageObject).
print *.null_ideal(...) in all doctests: maybe do not break
'Univariate Polynomial Ring'; I find this hard to read
then. Maybe break already after the preceding 'of'
Not sure if this helps, but and/or: indent the second line.
(Default: ...) vs. (default: ...); I think SageMath has a preference
for the latter:

sage -grep "(default:" | wc -l
4920
sage -grep "(Default:" | wc -l
92

doc p_minimal_polynomial, INPUT s_max vs. last sentence before EXAMPLES:
At first sight it seems weird that in the INPUT block it can easily be
described what happens when s_max is set, whereas in the sentence
before the EXAMPLES block a much longer explaination is needed. Also
t <= s_max vs s <= s_max confuses when reading first. Moreover I find the
sentence before the EXAMPLES block hard to read.
So maybe could be rewritten to make it easier understandable.
Adapt this in matrix_integer_dense as well.
L 328: "square matrix required." full stop at end, but in no
other raised exception.
As we are already talking about exceptions and FYI, sometimes they
are formulated as proper English sentences like
s is not in N_{(%s^%s)}(B)
(but omiting the full stop, where I personally would put one as the
sentence ends here, but I am aware that there are different
perspectives here), sometime not like
%s not in (%s^%s)-ideal
L559: two blanks after "return"
FYI, between two methods there are two empty lines most of the time,
but not always
matrix_integer_dense, p_minimal_polynomials: Should it be explained
what the (p^t)-minimal polynomials \nu_t of this matrix are?

I am not sure, why no patchbot tested this ticket yet...

sagetrac-git · 2017-01-02T12:13:40Z

Changed commit from 78f6f33 to 0b218b1

sagetrac-git · 2017-01-02T12:13:40Z

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

`361c8cf`	`Trac #21992.1: remove trailing white space`
`b50f81e`	`Trac #21992.2: Python3 compatibility`
`b157039`	`Trac #21992.3: refactor imports`
`34b4d50`	`Trac #21992.4: Change linebreaks in doctests`
`c79014a`	`Trac #21992.5: "Default" -> "default"`
`d7e519a`	`Trac #21992.6: reformulate description of s_max`
`7db28fe`	`Trac #21992.7+8: rephrase exceptions`
`f64dd65`	`Trac #21992.9: remove superfluous white space`
`36b084d`	`Trac #21992.10: Double blank line before methods`
`0b218b1`	`Trac #21992.11: Explain p^s-minimal polynomial`

cheuberg · 2017-01-02T12:22:50Z

comment:6

Thank you for your review. I modified the branch taking all your comments into account.
6. I split the sentence into two parts, perhaps it is now easier to understand. I also added a "see below" in the documentation for the input parameter to at least announce that it is somewhat tricky. I replaced several t by s to have more homogeneous notation.
7. done
8. Abbreviated all but one exception to non-sentences without full stop; one exception has been upgraded to a full sentence with full stop because I did not see a concise non-sentence formulation.
I am not sure about the patchbot; I now added the "?kick" parameter.

dkrenn · 2017-01-02T12:49:40Z

comment:7

Replying to @cheuberg:

Thank you for your review. I modified the branch taking all your comments into account.

LGTM.

I split the sentence into two parts, perhaps it is now easier to understand. I also added a "see below" in the documentation for the input parameter to at least announce that it is somewhat tricky. I replaced several t by s to have more homogeneous notation.

Ok, thank you. I think this is much better now.

Abbreviated all but one exception to non-sentences without full stop; one exception has been upgraded to a full sentence with full stop because I did not see a concise non-sentence formulation.

Ok.

I am not sure about the patchbot; I now added the "?kick" parameter.

So, this is a positive review from my side. I suggest to wait some more days to see if the patchbot with all plugins agrees as well.

tscrim · 2017-01-03T00:13:13Z

comment:8

Some very minor points:

References should go in the master reference file.

INPUT's should not end in a period. One of the longer ones should be changed to:

  - ``G`` -- a matrix over `D[X]`; the columns of
    `\begin{pmatrix}p^{t-1}I& G\end{pmatrix}` are generators
    of `\{ f\in D[X]^d \mid Af \equiv 0\pmod{p^{t-1}}\}`;
    can be set to ``None`` if ``t`` is zero

The other long one to change:

      - ``s_max`` -- a positive integer (default: ``None``); if set, only
        `(p^s)`-minimal polynomials for ``s <= s_max`` are computed
        (see below for details)

To one line:

-        raise ValueError(
-            "A*G not zero mod %s^%s" % (p, t-1))
+        raise ValueError("A*G not zero mod %s^%s" % (p, t-1))

The asserts are just checking that the Smith normal form is correct? I know its considered good form, but all asserts are (currently) checked in Sage.

This break is strange:

-    return sum(c//p * X**i for
-               i, c in enumerate(f.list())
+    return sum(c//p * X**i for i, c in enumerate(f.list())
                if c % p == 0)

Move the description of what the method does before the INPUT: and OUTPUT:. It makes it easier to parse and (IMO) is more important information.
Use the Sage macro \ZZ instead of \mathbb{Z}. Same for \QQ.
Add some whitespace around the latex. While it doesn't make a difference in the html/pdf rendered doc, it makes it easier to read when using the ?.
You can freely split lines in .. MATH:: blocks.

sagetrac-git · 2017-01-03T06:48:43Z

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

`b034597`	`Trac #21992: Merge 7.5.rc1 for master bibliography`
`0fbef2c`	`Trac #21992.12: Move references to master file`
`7f4d71c`	`Trac #21992.13: INPUT: do not end in a period`
`87a11d7`	`Trac #21992.14: remove line break`
`15f6cf9`	`Trac #21992.15: comment out assert`
`e1c91c9`	`Trac #21992.16: change line break`
`2f819d8`	`Trac #21192.17: use long descriptions`
`25c6da2`	`Trac #21992.18: \mathbb{Z}->\ZZ, \mathbb{Q}->\QQ`
`306cd06`	`Trac #21992.20: break lines in MATH`

sagetrac-git · 2017-01-03T06:48:43Z

Changed commit from 0b218b1 to 306cd06

cheuberg · 2017-01-03T06:53:58Z

comment:10

Replying to @tscrim:

Some very minor points:

Thank you for your comments. I pushed changes.

References should go in the master reference file.

done. This required merging a 6.5.rc1 (until now, the branch was based on 6.4 which had no master reference file).

The asserts are just checking that the Smith normal form is correct? I know its considered good form, but all asserts are (currently) checked in Sage.

Yes, and to recall what matrix is what. I commented out those asserts checking Smith normal form.
There are several other asserts scattered through the code checking that our own code here works as expected. I kept those.

Move the description of what the method does before the INPUT: and OUTPUT:. It makes it easier to parse and (IMO) is more important information.

I did this in two instances; it does not seem to be trivial because the information from the input section is somehow needed. So this introduces some redundancy.

Add some whitespace around the latex. While it doesn't make a difference in the html/pdf rendered doc, it makes it easier to read when using the ?.

Please be more specific where you want to have whitespace added. There is quite a number of LaTeX formulae throughout the module.

dkrenn · 2017-01-03T10:19:02Z

comment:11

Dear Travis,

Replying to @tscrim:

INPUT's should not end in a period. One of the longer ones should be changed to:

  - ``G`` -- a matrix over `D[X]`; the columns of
    `\begin{pmatrix}p^{t-1}I& G\end{pmatrix}` are generators
    of `\{ f\in D[X]^d \mid Af \equiv 0\pmod{p^{t-1}}\}`;
    can be set to ``None`` if ``t`` is zero

I agree that constructs like

``G`` -- a matrix over `D[X]`

should not end in a period (by our new convention), but
the part after the first ; is a proper English sentence, thus I think it should end in a period.

Best, Daniel

dkrenn · 2017-01-03T11:22:14Z

comment:12

Replying to @dkrenn:

[...], but
the part after the first ; is a proper English sentence, thus I think it should end in a period.

Maybe this would be a good compromise:

  - ``G`` -- a matrix over `D[X]`

    The columns of
    `\begin{pmatrix}p^{t-1}I& G\end{pmatrix}` are generators
    of `\{ f\in D[X]^d \mid Af \equiv 0\pmod{p^{t-1}}\}`.
    This parameter can be set to ``None`` if ``t`` is zero.

tscrim · 2017-01-03T14:11:25Z

comment:13

Redundancy is not necessarily a bad thing, especially when it comes to documenting inputs.

Also, why did you leave in the .. TODO:: about the tests? I feel like that could be easily done.

For the latex and spacing, I think this is the worst one (I'm also okay with no space after \max):

-        For `0<t\le \max\mathcal{S}`, a `(p^t)`-minimal polynomial is
-        For `0 < t \le \max \mathcal{S}`, a `(p^t)`-minimal polynomial is
         given by `\nu_s` where
-        `s=\min\{ r\in\mathcal{S}\mid r\ge t\}`.
-        For `t>\max\mathcal{S}`, the minimal polynomial of `B` is
+        `s = \min\{ r \in \mathcal{S} \mid r \ge t\}`.
+        For `t > \max \mathcal{S}`, the minimal polynomial of `B` is
         also a `(p^t)`-minimal polynomial.

Also, for null_ideal, I would be a bit more verbose and document it as:

     def null_ideal(self, b=0):
         r"""
-        Return the `(b)`-ideal `N_{(b)}(B)=\{f\in \ZZ[X] \mid f(B)\in M_n(b\ZZ)\}` where `B`
-        is this matrix.
+        Return the null ideal corresponding to ``b`` of ``self``.
+
+        Let `B` be an `n \times n` matrix. The *null ideal* of `b`, or `(b)`-ideal, is
+
+        .. MATH::
+
+            N_{(b)}(B) = \{f \in \ZZ[X] \mid f(B) \in M_n(b\ZZ)\}.
+

For integer_valued_polynomials, I would expect, based on the method name, that the output would be a list/tuple of polynomials. Also, overall, I'm far less convinced than other people about the necessity of an OUTPUT block when the documentation clearly described the output.

I like the compromise less than just allowing the periods. While I would like to adhere more to our (long standing) conventions of allowing things closer to run-on sentences to not end in periods in INPUT bullets, this is long enough that I am okay with it going in.

sagetrac-git · 2017-01-03T15:02:41Z

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

`b0104fc`	`Trac #21992.19: Insert blanks into TeX code`
`cce8dd4`	`Trac #21992.21: rewrite doc of null_ideal`
`a915d56`	`Trac #21992: missing empty line`

sagetrac-git · 2017-01-03T15:02:41Z

Changed commit from 306cd06 to a915d56

cheuberg · 2017-01-03T15:26:34Z

comment:15

Replying to @tscrim:

Also, why did you leave in the .. TODO:: about the tests? I feel like that could be easily done.

Because it does not work: First problem is that the first step (prime_candidates) needs Frobenius Rational Form and this is only implemented over ZZ.

Next problem is some kind of bug in lifting, cf. https://ask.sagemath.org/question/35555/lifting-a-matrix-from-mathbbqyy-1/ .

At this point, we stopped trying and decided to concentrate on the integer case first.

For the latex and spacing, I think this is the worst one (I'm also okay with no space after \max):

done.

Also, for null_ideal, I would be a bit more verbose and document it as:

done (in slightly different wording). This concerns the documentation in matrix_integer_dense.
In compute_J_ideal.py, the explanation is at the top of the module.

For integer_valued_polynomials, I would expect, based on the method name, that the output would be a list/tuple of polynomials.

The set of integer valued polynomials of the matrix B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]]) is
(x<sup>3+x</sup>2−12x−20)QQ[X]+ZZ[X]+(1/4)(x^2+3x+2)ZZ[X].
As a ZZ[X] module, this is not finitely generated. It is not a QQ[X] module. Therefore, its description needs two components. Therefore, the output is a pair where the second component is a list of polynomials.

I like the compromise less than just allowing the periods. While I would like to adhere more to our (long standing) conventions of allowing things closer to run-on sentences to not end in periods in INPUT bullets, this is long enough that I am okay with it going in.

Can we leave it in the current form?

tscrim · 2017-01-04T12:35:41Z

comment:16

Replying to @cheuberg:

Replying to @tscrim:

Also, why did you leave in the .. TODO:: about the tests? I feel like that could be easily done.

Because it does not work: First problem is that the first step (prime_candidates) needs Frobenius Rational Form and this is only implemented over ZZ.

Next problem is some kind of bug in lifting, cf. https://ask.sagemath.org/question/35555/lifting-a-matrix-from-mathbbqyy-1/ .

Could you add these to the .. TODO::, because I think anyone else reading the code will ask the same question I did.

For integer_valued_polynomials, I would expect, based on the method name, that the output would be a list/tuple of polynomials.

The set of integer valued polynomials of the matrix B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]]) is
(x<sup>3+x</sup>2−12x−20)QQ[X]+ZZ[X]+(1/4)(x^2+3x+2)ZZ[X].
As a ZZ[X] module, this is not finitely generated. It is not a QQ[X] module. Therefore, its description needs two components. Therefore, the output is a pair where the second component is a list of polynomials.

I think a bit more verbose name is warranted here, something like generators_integer_valued_polynomials. If you want the method to be named integer_valued_polynomials, then it should return the set (algebra?) of integer valued polynomials.

I like the compromise less than just allowing the periods. While I would like to adhere more to our (long standing) conventions of allowing things closer to run-on sentences to not end in periods in INPUT bullets, this is long enough that I am okay with it going in.

Can we leave it in the current form?

Yes.

sagetrac-git · 2017-01-04T13:46:00Z

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

`3e31602`	`Trac #21992.22: expand TODO block: explain problem`
`079f8f1`	`Trac #21992.23: integer_valued_polynomials_generators`

sagetrac-git · 2017-01-04T13:46:00Z

Changed commit from a915d56 to 079f8f1

cheuberg · 2017-01-04T13:48:18Z

comment:18

Replying to @tscrim:

Replying to @cheuberg:

Replying to @tscrim:

Also, why did you leave in the .. TODO:: about the tests? I feel like that could be easily done.

Because it does not work: First problem is that the first step (prime_candidates) needs Frobenius Rational Form and this is only implemented over ZZ.

Next problem is some kind of bug in lifting, cf. https://ask.sagemath.org/question/35555/lifting-a-matrix-from-mathbbqyy-1/ .

Could you add these to the .. TODO::, because I think anyone else reading the code will ask the same question I did.

Done.

I think a bit more verbose name is warranted here, something like generators_integer_valued_polynomials. If you want the method to be named integer_valued_polynomials, then it should return the set (algebra?) of integer valued polynomials.

I renamed the method to integer_valued_polynomials_generators for the sake of tab completion.

tscrim · 2017-01-04T23:19:54Z

comment:19

LGTM. Daniel, any other comments before we set this to a positive review.

tscrim · 2017-01-04T23:19:54Z

Changed reviewer from Daniel Krenn to Daniel Krenn, Travis Scrimshaw

dkrenn · 2017-01-05T08:19:51Z

comment:20

Replying to @tscrim:

LGTM. Daniel, any other comments before we set this to a positive review.

Fine for me as well.

vbraun · 2017-01-18T20:39:00Z

Changed branch from u/cheuberg/compute-j-ideal to 079f8f1

cheuberg added this to the sage-7.5 milestone Nov 29, 2016

cheuberg added c: linear algebra labels Nov 29, 2016

cheuberg added the s: needs review label Nov 30, 2016

This comment has been minimized.

Sign in to view

dkrenn added s: needs work and removed s: needs review labels Jan 1, 2017

cheuberg added s: needs review and removed s: needs work labels Jan 2, 2017

dkrenn added s: positive review and removed s: needs review labels Jan 5, 2017

vbraun removed the s: positive review label Jan 18, 2017

vbraun closed this as completed in fa35715 Jan 18, 2017

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Compute J-ideal of a matrix #21992

Compute J-ideal of a matrix #21992

cheuberg commented Nov 29, 2016

cheuberg commented Nov 30, 2016

cheuberg commented Nov 30, 2016

cheuberg commented Nov 30, 2016

sagetrac-git mannequin commented Dec 1, 2016

sagetrac-git mannequin commented Dec 1, 2016

This comment has been minimized.

dkrenn commented Jan 1, 2017

dkrenn commented Jan 1, 2017

sagetrac-git mannequin commented Jan 2, 2017

sagetrac-git mannequin commented Jan 2, 2017

cheuberg commented Jan 2, 2017

dkrenn commented Jan 2, 2017

tscrim commented Jan 3, 2017

sagetrac-git mannequin commented Jan 3, 2017

sagetrac-git mannequin commented Jan 3, 2017

cheuberg commented Jan 3, 2017

dkrenn commented Jan 3, 2017

dkrenn commented Jan 3, 2017

tscrim commented Jan 3, 2017

sagetrac-git mannequin commented Jan 3, 2017

sagetrac-git mannequin commented Jan 3, 2017

cheuberg commented Jan 3, 2017

tscrim commented Jan 4, 2017

sagetrac-git mannequin commented Jan 4, 2017

sagetrac-git mannequin commented Jan 4, 2017

cheuberg commented Jan 4, 2017

tscrim commented Jan 4, 2017

tscrim commented Jan 4, 2017

dkrenn commented Jan 5, 2017

vbraun commented Jan 18, 2017

Compute J-ideal of a matrix #21992

Compute J-ideal of a matrix #21992

Comments

cheuberg commented Nov 29, 2016

cheuberg commented Nov 30, 2016

cheuberg commented Nov 30, 2016

cheuberg commented Nov 30, 2016

sagetrac-git mannequin commented Dec 1, 2016

sagetrac-git mannequin commented Dec 1, 2016

This comment has been minimized.

dkrenn commented Jan 1, 2017

dkrenn commented Jan 1, 2017

sagetrac-git mannequin commented Jan 2, 2017

sagetrac-git mannequin commented Jan 2, 2017

cheuberg commented Jan 2, 2017

dkrenn commented Jan 2, 2017

tscrim commented Jan 3, 2017

sagetrac-git mannequin commented Jan 3, 2017

sagetrac-git mannequin commented Jan 3, 2017

cheuberg commented Jan 3, 2017

dkrenn commented Jan 3, 2017

dkrenn commented Jan 3, 2017

tscrim commented Jan 3, 2017

sagetrac-git mannequin commented Jan 3, 2017

sagetrac-git mannequin commented Jan 3, 2017

cheuberg commented Jan 3, 2017

tscrim commented Jan 4, 2017

sagetrac-git mannequin commented Jan 4, 2017

sagetrac-git mannequin commented Jan 4, 2017

cheuberg commented Jan 4, 2017

tscrim commented Jan 4, 2017

tscrim commented Jan 4, 2017

dkrenn commented Jan 5, 2017

vbraun commented Jan 18, 2017