Opened 5 years ago

Closed 5 years ago

#23450 closed enhancement (fixed)

Smith form of p-adic matrices

Reported by: Xavier Caruso Owned by:
Priority: major Milestone: sage-8.2
Component: padics Keywords: sd87
Cc: David Roe, Julian Rüth, Tristan Vaccon, Kiran Kedlaya Merged in:
Authors: Xavier Caruso, Julian Rüth, David Roe Reviewers: Julian Rüth, David Roe
Report Upstream: N/A Work issues:
Branch: e6f54bb (Commits, GitHub, GitLab) Commit: e6f54bb5b0849b7654d645dc63171af9001e7ae9
Dependencies: Stopgaps:

Status badges

Description (last modified by Xavier Caruso)

Currently Smith form are not implemented over inexact rings.

This ticket provides a (currently unoptimized) implementation of Smith normal form over complete discrete valuation rings/fields (e.g. p-adic rings/fields).

Change History (59)

comment:1 Changed 5 years ago by Xavier Caruso

Branch: u/caruso/padic_smith

comment:2 Changed 5 years ago by Julian Rüth

Commit: 879f4eb46b700d0d3c4a0779b8293158ea4af298

This is great. I was hoping that you would implement this for a while ;)

Have you thought about not creating a separate class for this but implementing it in the base ring (or in the category), i.e., provide _matrix_smith_form on the ring/category and call it from the generic matrix code if it is defined (otherwise fall back to the generic implementation). In other words, do what is already done for things like polynomial factorization.

Also, should this code be used for "exact" CDVRs such as the ones backed by absolute number fields?


New commits:

879f4ebSmith form of a p-adic matrix

comment:3 Changed 5 years ago by Julian Rüth

Component: PLEASE CHANGEpadics

comment:4 Changed 5 years ago by git

Commit: 879f4eb46b700d0d3c4a0779b8293158ea4af298595bc117c7becc12c9e6afcefcc372b46320384e

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

595bc11Code moved into the category

comment:5 Changed 5 years ago by Xavier Caruso

Description: modified (diff)
Status: newneeds_review

Ok, I've moved the code to the category (CDVF and CDVR) as you suggested.

I've also tried to be more rigourous regarding precision and figured out what is the correct precision on the transformation matrices. (My first implementation was too optimistic.) Actually, it turns out that finding the optimal precision is costly, except in the particular case where the input matrix is given at flat precision (i.e. all the entries are given at the same precision). For this reason, I've overestimated the loss of precision for a general input matrix (by reducing to the case of flat precision).

I've also removed the method that computes the determinant of a matrix because again it only worked for matrices given at flat precision.

The ticket is ready for review.

comment:6 Changed 5 years ago by git

Commit: 595bc117c7becc12c9e6afcefcc372b46320384ee2cdd995a80e859027ffd5685f1d96cc480d4277

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

1832757Factorisation of code
e2cdd99Small fix

comment:7 Changed 5 years ago by git

Commit: e2cdd995a80e859027ffd5685f1d96cc480d42771fd67fe26e5c1afb90f68127fdbd8a40bd01c75e

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

7ae1018Move relevant code to sage.matrix.matrix_cdv_dense
7e73fd2Fix import
1fd67feAdd method tracks_precision()

comment:8 Changed 5 years ago by git

Commit: 1fd67fe26e5c1afb90f68127fdbd8a40bd01c75e1f07da52c7769205e3549df079699202afbd4195

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

1f731eeCheck correctly (hopefully) that precision on input is enough
1f07da5Small fixes

comment:9 Changed 5 years ago by Xavier Caruso

I think (hope) that this ticket is now *really* ready for review :-)

comment:10 Changed 5 years ago by Julian Rüth

Reviewers: Julian Rüth

I'll try to review this tomorrow.

comment:11 Changed 5 years ago by git

Commit: 1f07da52c7769205e3549df079699202afbd419555b99df7b752c66cf6256b1adf7a7f0951f71808

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

55b99dfSmall fix in lift_to_maximal_precision

comment:12 Changed 5 years ago by git

Commit: 55b99df7b752c66cf6256b1adf7a7f0951f718081ea48acfe280981d969970384e10309a9c8211db

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

1ea48acTwo small bugs fixed

comment:13 Changed 5 years ago by git

Commit: 1ea48acfe280981d969970384e10309a9c8211dbf27820a66d4de7f972f4b59df5b5d53f31463ae1

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

65ffbc6Use the name "integral_smith_form" for matrices over CDVF
f27820aSmall fixes

comment:14 Changed 5 years ago by Julian Rüth

Work issues: drop lift_to_maximal_precision

comment:15 Changed 5 years ago by Julian Rüth

Status: needs_reviewneeds_work
Work issues: drop lift_to_maximal_precision

Xavier, I am refactoring this a fair bit. Hope you don't mind.

comment:16 Changed 5 years ago by Julian Rüth

Branch: u/caruso/padic_smithu/saraedum/padic_smith

comment:17 Changed 5 years ago by Julian Rüth

Branch: u/saraedum/padic_smithu/caruso/padic_smith

(and sorry, the category idea was a very bad call. I'm fixing it right now.)

comment:18 Changed 5 years ago by Julian Rüth

Branch: u/caruso/padic_smithu/saraedum/padic_smith

comment:19 Changed 5 years ago by Julian Rüth

Commit: f27820a66d4de7f972f4b59df5b5d53f31463ae1e635699dfab09b4ba86ee3f83eb95d0d5f8463dc
Work issues: failing unit tests

New commits:

8e00041Replace lift_to_maximal_precision() with lift_to_precision(None)
5802a8cMove Smith Normal Form Code
2713b74Remove CDV matrix classes
ad1632cImplement tracks_precision() on base classes
2771757prettify documentation
922ea39remove lift_to_maximal_precision
e04b26fremove lift_to_maximal_precision
ea1f480fix doctests
7198f2brebase _matrix_smith_form
e635699implement Smith form tests

comment:20 Changed 5 years ago by Julian Rüth

sage -t --warn-long 61.6 src/sage/rings/padics/padic_base_leaves.py  # 3 doctests failed
sage -t --warn-long 61.6 src/sage/rings/padics/padic_extension_leaves.py  # 2 doctests failed
Last edited 5 years ago by Julian Rüth (previous) (diff)

comment:21 Changed 5 years ago by git

Commit: e635699dfab09b4ba86ee3f83eb95d0d5f8463dc39665f03bbcf456a592a86af5b8c55c8d114ef29

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

39665f0S is not square

comment:22 Changed 5 years ago by Julian Rüth

The problem is always:

    Failure in _test_matrix_smith:
    Traceback (most recent call last):
      File "/projects/da1818ed-996d-4de6-acc6-361415b7725d/Src/sage-saraedum/local/lib/python2.7/site-packages/sage/misc/sage_unittest.py", line 293, in run
        test_method(tester = tester)
      File "/projects/da1818ed-996d-4de6-acc6-361415b7725d/Src/sage-saraedum/local/lib/python2.7/site-packages/sage/rings/padics/local_generic.py", line 768, in _test_matrix_smith
        S,U,V = M.smith_form()
      File "sage/matrix/matrix2.pyx", line 13267, in sage.matrix.matrix2.Matrix.smith_form (/projects/da1818ed-996d-4de6-acc6-361415b7725d/Src/sage-saraedum/src/build/cythonized/sage/matrix/matrix2.c:94870)
        return R._matrix_smith_form(self,transformation=transformation)
      File "/projects/da1818ed-996d-4de6-acc6-361415b7725d/Src/sage-saraedum/local/lib/python2.7/site-packages/sage/rings/padics/local_generic.py", line 727, in _matrix_smith_form
        inv = (S[piv,piv] >> val).inverse_of_unit()
      File "sage/rings/padics/local_generic_element.pyx", line 160, in sage.rings.padics.local_generic_element.LocalGenericElement.inverse_of_unit (build/cythonized/sage/rings/padics/local_generic_element.c:2339)
        raise ZeroDivisionError("Inverse does not exist.")
    ZeroDivisionError: Inverse does not exist.

comment:23 Changed 5 years ago by Julian Rüth

Xavier: I am a bit confused. Is integral_smith_form the same as change_ring(integer_ring).smith_form?

Last edited 5 years ago by Julian Rüth (previous) (diff)

comment:24 Changed 5 years ago by Xavier Caruso

If the coefficients of the matrix lie in the integer ring, it is. But integral_smith_form is defined for any matrix defined over the fraction field.

comment:25 Changed 5 years ago by git

Commit: 39665f03bbcf456a592a86af5b8c55c8d114ef29554dffcb26886add95f3260cc21a607ba5e46706

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

554dffcUpdate documentation of smith_form

comment:26 Changed 5 years ago by Julian Rüth

Ok. I got confused by the comment:

- if `d_i` denotes the `(i,i)` entry of `S`, then `d_i`
divides `d_{i+1}` in the ring of integers for all `i`.

New commits:

554dffcUpdate documentation of smith_form

comment:27 Changed 5 years ago by git

Commit: 554dffcb26886add95f3260cc21a607ba5e467069cc114e999d46f5f710d631e1f4ebd48036213d8

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

9cc114eclarify diagonal entries

comment:28 Changed 5 years ago by git

Commit: 9cc114e999d46f5f710d631e1f4ebd48036213d8e4a9ad729e31ca6edbe94e68a8b85134eaa0e468

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

e4a9ad7Implement integral for smith normal form over local rings

comment:29 Changed 5 years ago by git

Commit: e4a9ad729e31ca6edbe94e68a8b85134eaa0e468502c8872f4db9c738b36947dca442e875b4cd70a

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

2a519abadd itegral handling for Smith form over local rings
502c887Add integral keyword to smith_form implementations

comment:30 Changed 5 years ago by Julian Rüth

Authors: Xavier CarusoXavier Caruso, Julian Rüth
Status: needs_workneeds_review

Xavier: That's about what I had in mind. What do you think? (There are still some failing tests.)

comment:31 Changed 5 years ago by Xavier Caruso

Ok for factoring the code this way if you prefer.

However, I think that the current code doesn't output the expected answer for matrices over Qp with integral=None (though I haven't checked it). In that case, I would say that the entries of Smith normal norm should all be 0 or 1.

In the doctest, I think that we should precise that we require (1) that the matrices U and V are invertible over the subring and (2) that d_{i+1}/d_i lies in the subring for all i.

Last edited 5 years ago by Xavier Caruso (previous) (diff)

comment:32 Changed 5 years ago by Julian Rüth

Work issues: failing unit testsfailing unit tests, clarify meaning of integral, talk about precision

Xavier: Could you write something about what it means for an entry on the diagonal to be zero (in the field case)? I mean it is somewhat unclear since we compute with inexact elements.

comment:33 Changed 5 years ago by Frédéric Chapoton

doc does not build

+[dochtml] [matrices ] docstring of sage.matrix.matrix2.Matrix.smith_form:26: WARNING: Bullet list ends without a blank line; unexpected unindent.
+[dochtml] [matrices ] docstring of sage.matrix.matrix2.Matrix.smith_form:29: WARNING: Bullet list ends without a blank line; unexpected unindent.
Version 0, edited 5 years ago by Frédéric Chapoton (next)

comment:34 Changed 5 years ago by Alyson Deines

Branch: u/saraedum/padic_smithu/aly.deines/padic_smith

comment:35 Changed 5 years ago by Alyson Deines

Commit: 502c8872f4db9c738b36947dca442e875b4cd70a89ec3ab13eb92d68c4ad2f12b10151041d31aefe
Status: needs_reviewneeds_work

New commits:

1fd5309Merge branch 'u/saraedum/padic_smith' of git://trac.sagemath.org/sage into t/23450/padic_smith
89ec3abRemoved trailing whitespace.

comment:36 Changed 5 years ago by Alyson Deines

Changed to needs work because of above issues.

comment:37 Changed 5 years ago by Simon Brandhorst

*ping* - I could really use this p-adic smith form. (over ZZp) Need help? (not an expert though)

comment:38 Changed 5 years ago by Kiran Kedlaya

Cc: Kiran Kedlaya added

comment:39 Changed 5 years ago by Frédéric Chapoton

Branch: u/aly.deines/padic_smithpublic/23450
Commit: 89ec3ab13eb92d68c4ad2f12b10151041d31aefe8b239f40ab22a1e524073e1a8765d034c86254da
Status: needs_workneeds_review

New commits:

d92d3e9Merge branch 'u/aly.deines/padic_smith' in 8.1.rc4
8b239f4trac 23450 details of doc

comment:40 Changed 5 years ago by Frédéric Chapoton

Status: needs_reviewneeds_work

comment:41 Changed 5 years ago by git

Commit: 8b239f40ab22a1e524073e1a8765d034c86254da14f591c94af65b88673f0c295f3c00c093468755

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

93d4e32Merge branch 'public/23450' in 8.1
14f591cfixing 2 doctests

comment:42 Changed 5 years ago by git

Commit: 14f591c94af65b88673f0c295f3c00c093468755cf85a341259e09416413bd7b29ec99e8e0597c62

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

cf85a34Merge branch 'public/23450' of ssh://trac.sagemath.org/sage into t/23450/padic_smith

comment:43 Changed 5 years ago by git

Commit: cf85a341259e09416413bd7b29ec99e8e0597c627ad838a41517a89f6906ec1fda018e3029db7436

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

7ad838aRemove _get_matrix_class that was inadvertently added in a merge

comment:44 Changed 5 years ago by git

Commit: 7ad838a41517a89f6906ec1fda018e3029db7436b5863a1757c05e36e832fd1f743d31127edbe7a0

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

b5863a1Add newline back in from fix to matrix_space.py

comment:45 Changed 5 years ago by git

Commit: b5863a1757c05e36e832fd1f743d31127edbe7a0777f494e5c8a9924c740c55f636b1e9f10454cb4

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

777f494Remove the tracks_precision method and update the p-adic smith form to be able to deal with lattice elements

comment:46 Changed 5 years ago by git

Commit: 777f494e5c8a9924c740c55f636b1e9f10454cb4d78a1d58857c0a635f6a0f451ccac57e29df28c3

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

d78a1d5Add exact parameter to _matrix_smith_form, fix precision behavior and allow integral=True for non-padic matrices

comment:47 Changed 5 years ago by David Roe

Authors: Xavier Caruso, Julian RüthXavier Caruso, Julian Rüth, David Roe
Reviewers: Julian RüthJulian Rüth, David Roe
Status: needs_workneeds_review

If Xavier is happy with my changes, I'm happy to give this positive review.

comment:48 Changed 5 years ago by git

Commit: d78a1d58857c0a635f6a0f451ccac57e29df28c3f7d4e3833eee9ef8138d2d01bb3ffbce400ba9d0

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

f7d4e38lift_to_precision() was missing at some point

comment:49 Changed 5 years ago by git

Commit: f7d4e3833eee9ef8138d2d01bb3ffbce400ba9d00d46aa51e56133ec125d90698ffb1974f186a31d

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

0d46aa5Add a test: Smith form of the zero matrix

comment:50 Changed 5 years ago by Xavier Caruso

I've fixed a small issue with precision.

Now, everything seems fine to me. I let you give a positive review if you're OK (and if the patchbot is happy)

comment:51 Changed 5 years ago by David Roe

Milestone: sage-8.1
Status: needs_reviewpositive_review

Patchbot is green, so positive review.

comment:52 Changed 5 years ago by Frédéric Chapoton

Milestone: sage-8.2

comment:53 Changed 5 years ago by Frédéric Chapoton

Work issues: failing unit tests, clarify meaning of integral, talk about precision

comment:54 Changed 5 years ago by Volker Braun

Status: positive_reviewneeds_work

Tests fail

    UnboundLocalError: local variable 'precM' referenced before assignment

comment:55 Changed 5 years ago by François Bissey

Let me add a bit of details, 6 doctests fails

sage -t --long /usr/lib64/python2.7/site-packages/sage/rings/padics/padic_lattice_element.py  # 4 doctests failed
sage -t --long /usr/lib64/python2.7/site-packages/sage/rings/padics/padic_base_leaves.py  # 2 doctests failed

and they all fail the same way

File "/usr/lib64/python2.7/site-packages/sage/rings/padics/padic_base_leaves.py", line 879, in sage.rings.padics.padic_base_leaves.pAdicRingLattice.__init__
Failed example:
    TestSuite(R).run(skip='_test_teichmuller')
Expected nothing
Got:
    Failure in _test_matrix_smith:
    Traceback (most recent call last):
      File "/usr/lib64/python2.7/site-packages/sage/misc/sage_unittest.py", line 294, in run
        test_method(tester = tester)
      File "/usr/lib64/python2.7/site-packages/sage/rings/padics/local_generic.py", line 1248, in _test_matrix_smith
        S,U,V = M.smith_form(integral=base)
      File "sage/matrix/matrix2.pyx", line 13416, in sage.matrix.matrix2.Matrix.smith_form (/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/build/cythonized/sage/matrix/matrix2.c:96167)
        return R._matrix_smith_form(self, transformation=transformation, integral=integral, exact=exact)
      File "/usr/lib64/python2.7/site-packages/sage/rings/padics/local_generic.py", line 1148, in _matrix_smith_form
        if inexact_ring and not allzero and val >= precM:
    UnboundLocalError: local variable 'precM' referenced before assignment
    ------------------------------------------------------------
    The following tests failed: _test_matrix_smith

ending in local_generic.py.

comment:56 Changed 5 years ago by git

Commit: 0d46aa51e56133ec125d90698ffb1974f186a31de6f54bb5b0849b7654d645dc63171af9001e7ae9

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

0613f84Recompute precM in the lattice precision framework
e6f54bbMerge branch 'develop' into t/23450/public/23450

comment:57 Changed 5 years ago by Xavier Caruso

Status: needs_workneeds_review

Should be fixed.

comment:58 Changed 5 years ago by David Roe

Status: needs_reviewpositive_review

The patchbots continue to be noisy, but this looks good to me.

comment:59 Changed 5 years ago by Volker Braun

Branch: public/23450e6f54bb5b0849b7654d645dc63171af9001e7ae9
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.