Opened 6 years ago

Closed 5 years ago

#21992 closed enhancement (fixed)

Compute J-ideal of a matrix

Reported by: cheuberg Owned by:
Priority: major Milestone: sage-7.5
Component: linear algebra Keywords:
Cc: dkrenn, rrissner Merged in:
Authors: Clemens Heuberger, Roswitha Rissner Reviewers: Daniel Krenn, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 079f8f1 (Commits, GitHub, GitLab) Commit: 079f8f1de35ab2eb3a5a964a7f9d8c642afe6b6e
Dependencies: Stopgaps:

Status badges

Description (last modified by cheuberg)

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, arXiv 1611.10308 [math.AC], 2016.

Change History (21)

comment:1 Changed 6 years ago by cheuberg

  • Branch set to u/cheuberg/compute-j-ideal
  • Commit set to c3433e210fbd50348bdc22dbf900ee8bb6a5fbcc
  • Status changed from new to needs_review

Last 10 new commits:

c7837e7adapt import statements
56028e4Cache G and previous nu
458067eAvoid computing lifting twice for debugging
902c344Implement method integer_valued_polynomials
c63f37bImprove documentation
0291daaMerge stand alone branch 't/21992/compute-j-ideal'
5ebd5e2Trac #21992: fix doctests after integration into sage
b9e7acfTrac #21992: include into documentation
0324154Trac #21992: Fix indentations
c3433e2Trac #21992: make compute_J_ideal accessible

comment:2 Changed 6 years ago by git

  • Commit changed from c3433e210fbd50348bdc22dbf900ee8bb6a5fbcc to 78f6f33d4879e0ff445a51e72d1a86a5e4befc0f

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

78f6f33Trac #21992: insert arXiv link

comment:3 Changed 6 years ago by cheuberg

  • Description modified (diff)

comment:4 Changed 5 years ago by dkrenn

  • Reviewers set to Daniel Krenn
  • Status changed from needs_review to needs_work

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

  1. correct the 2 lines with whitespace errors
  2. 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
  3. 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?).
  4. 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.
  5. (Default: ...) vs. (default: ...); I think SageMath has a preference for the latter:
    sage -grep "(default:" | wc -l
    4920
    sage -grep "(Default:" | wc -l
    92
    
  6. 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.
  7. L 328: "square matrix required." full stop at end, but in no other raised exception.
  8. 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
  9. L559: two blanks after "return"
  10. FYI, between two methods there are two empty lines most of the time, but not always
  11. 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...

comment:5 Changed 5 years ago by git

  • Commit changed from 78f6f33d4879e0ff445a51e72d1a86a5e4befc0f to 0b218b1360af5b55354714cb9494c7e9b2fcd4f4

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

361c8cfTrac #21992.1: remove trailing white space
b50f81eTrac #21992.2: Python3 compatibility
b157039Trac #21992.3: refactor imports
34b4d50Trac #21992.4: Change linebreaks in doctests
c79014aTrac #21992.5: "Default" -> "default"
d7e519aTrac #21992.6: reformulate description of s_max
7db28feTrac #21992.7+8: rephrase exceptions
f64dd65Trac #21992.9: remove superfluous white space
36b084dTrac #21992.10: Double blank line before methods
0b218b1Trac #21992.11: Explain p^s-minimal polynomial

comment:6 follow-up: Changed 5 years ago by cheuberg

  • Status changed from needs_work to needs_review

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

  1. 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.
  2. done
  3. 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.

comment:7 in reply to: ↑ 6 Changed 5 years ago by dkrenn

Replying to cheuberg:

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

LGTM.

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

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

comment:8 follow-ups: Changed 5 years ago by tscrim

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.

comment:9 Changed 5 years ago by git

  • Commit changed from 0b218b1360af5b55354714cb9494c7e9b2fcd4f4 to 306cd06623c572d852041dd1e0a645893b7d6c1f

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

b034597Trac #21992: Merge 7.5.rc1 for master bibliography
0fbef2cTrac #21992.12: Move references to master file
7f4d71cTrac #21992.13: INPUT: do not end in a period
87a11d7Trac #21992.14: remove line break
15f6cf9Trac #21992.15: comment out assert
e1c91c9Trac #21992.16: change line break
2f819d8Trac #21192.17: use long descriptions
25c6da2Trac #21992.18: \mathbb{Z}->\ZZ, \mathbb{Q}->\QQ
306cd06Trac #21992.20: break lines in MATH

comment:10 in reply to: ↑ 8 Changed 5 years ago by cheuberg

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.

comment:11 in reply to: ↑ 8 ; follow-up: Changed 5 years ago by dkrenn

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

Last edited 5 years ago by dkrenn (previous) (diff)

comment:12 in reply to: ↑ 11 Changed 5 years ago by dkrenn

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.

comment:13 follow-up: Changed 5 years ago by tscrim

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.

comment:14 Changed 5 years ago by git

  • Commit changed from 306cd06623c572d852041dd1e0a645893b7d6c1f to a915d564e6fbbf500d1cdecf2756a69a7b46ff1f

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

b0104fcTrac #21992.19: Insert blanks into TeX code
cce8dd4Trac #21992.21: rewrite doc of null_ideal
a915d56Trac #21992: missing empty line

comment:15 in reply to: ↑ 13 ; follow-up: Changed 5 years ago by 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/ .

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^3+x^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?

comment:16 in reply to: ↑ 15 ; follow-up: Changed 5 years ago by 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.

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^3+x^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.

comment:17 Changed 5 years ago by git

  • Commit changed from a915d564e6fbbf500d1cdecf2756a69a7b46ff1f to 079f8f1de35ab2eb3a5a964a7f9d8c642afe6b6e

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

3e31602Trac #21992.22: expand TODO block: explain problem
079f8f1Trac #21992.23: integer_valued_polynomials_generators

comment:18 in reply to: ↑ 16 Changed 5 years ago by cheuberg

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.

comment:19 follow-up: Changed 5 years ago by tscrim

  • Reviewers changed from Daniel Krenn to Daniel Krenn, Travis Scrimshaw

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

comment:20 in reply to: ↑ 19 Changed 5 years ago by dkrenn

  • Status changed from needs_review to positive_review

Replying to tscrim:

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

Fine for me as well.

comment:21 Changed 5 years ago by vbraun

  • Branch changed from u/cheuberg/compute-j-ideal to 079f8f1de35ab2eb3a5a964a7f9d8c642afe6b6e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.