Opened 5 years ago
Closed 5 years ago
#23450 closed enhancement (fixed)
Smith form of padic matrices
Reported by:  Xavier Caruso  Owned by:  

Priority:  major  Milestone:  sage8.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: 
Description (last modified by )
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. padic rings/fields).
Change History (59)
comment:1 Changed 5 years ago by
Branch:  → u/caruso/padic_smith 

comment:2 Changed 5 years ago by
Commit:  → 879f4eb46b700d0d3c4a0779b8293158ea4af298 

comment:3 Changed 5 years ago by
Component:  PLEASE CHANGE → padics 

comment:4 Changed 5 years ago by
Commit:  879f4eb46b700d0d3c4a0779b8293158ea4af298 → 595bc117c7becc12c9e6afcefcc372b46320384e 

Branch pushed to git repo; I updated commit sha1. New commits:
595bc11  Code moved into the category

comment:5 Changed 5 years ago by
Description:  modified (diff) 

Status:  new → needs_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
Commit:  595bc117c7becc12c9e6afcefcc372b46320384e → e2cdd995a80e859027ffd5685f1d96cc480d4277 

comment:7 Changed 5 years ago by
Commit:  e2cdd995a80e859027ffd5685f1d96cc480d4277 → 1fd67fe26e5c1afb90f68127fdbd8a40bd01c75e 

comment:8 Changed 5 years ago by
Commit:  1fd67fe26e5c1afb90f68127fdbd8a40bd01c75e → 1f07da52c7769205e3549df079699202afbd4195 

comment:9 Changed 5 years ago by
I think (hope) that this ticket is now *really* ready for review :)
comment:11 Changed 5 years ago by
Commit:  1f07da52c7769205e3549df079699202afbd4195 → 55b99df7b752c66cf6256b1adf7a7f0951f71808 

Branch pushed to git repo; I updated commit sha1. New commits:
55b99df  Small fix in lift_to_maximal_precision

comment:12 Changed 5 years ago by
Commit:  55b99df7b752c66cf6256b1adf7a7f0951f71808 → 1ea48acfe280981d969970384e10309a9c8211db 

Branch pushed to git repo; I updated commit sha1. New commits:
1ea48ac  Two small bugs fixed

comment:13 Changed 5 years ago by
Commit:  1ea48acfe280981d969970384e10309a9c8211db → f27820a66d4de7f972f4b59df5b5d53f31463ae1 

comment:14 Changed 5 years ago by
Work issues:  → drop lift_to_maximal_precision 

comment:15 Changed 5 years ago by
Status:  needs_review → needs_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
Branch:  u/caruso/padic_smith → u/saraedum/padic_smith 

comment:17 Changed 5 years ago by
Branch:  u/saraedum/padic_smith → u/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
Branch:  u/caruso/padic_smith → u/saraedum/padic_smith 

comment:19 Changed 5 years ago by
Commit:  f27820a66d4de7f972f4b59df5b5d53f31463ae1 → e635699dfab09b4ba86ee3f83eb95d0d5f8463dc 

Work issues:  → failing unit tests 
New commits:
8e00041  Replace lift_to_maximal_precision() with lift_to_precision(None)

5802a8c  Move Smith Normal Form Code

2713b74  Remove CDV matrix classes

ad1632c  Implement tracks_precision() on base classes

2771757  prettify documentation

922ea39  remove lift_to_maximal_precision

e04b26f  remove lift_to_maximal_precision

ea1f480  fix doctests

7198f2b  rebase _matrix_smith_form

e635699  implement Smith form tests

comment:20 Changed 5 years ago by
sage t warnlong 61.6 src/sage/rings/padics/padic_base_leaves.py # 3 doctests failed sage t warnlong 61.6 src/sage/rings/padics/padic_extension_leaves.py # 2 doctests failed
comment:21 Changed 5 years ago by
Commit:  e635699dfab09b4ba86ee3f83eb95d0d5f8463dc → 39665f03bbcf456a592a86af5b8c55c8d114ef29 

Branch pushed to git repo; I updated commit sha1. New commits:
39665f0  S is not square

comment:22 Changed 5 years ago by
The problem is always:
Failure in _test_matrix_smith: Traceback (most recent call last): File "/projects/da1818ed996d4de6acc6361415b7725d/Src/sagesaraedum/local/lib/python2.7/sitepackages/sage/misc/sage_unittest.py", line 293, in run test_method(tester = tester) File "/projects/da1818ed996d4de6acc6361415b7725d/Src/sagesaraedum/local/lib/python2.7/sitepackages/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/da1818ed996d4de6acc6361415b7725d/Src/sagesaraedum/src/build/cythonized/sage/matrix/matrix2.c:94870) return R._matrix_smith_form(self,transformation=transformation) File "/projects/da1818ed996d4de6acc6361415b7725d/Src/sagesaraedum/local/lib/python2.7/sitepackages/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
Xavier: I am a bit confused. Is integral_smith_form
the same as change_ring(integer_ring).smith_form
?
comment:24 Changed 5 years ago by
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
Commit:  39665f03bbcf456a592a86af5b8c55c8d114ef29 → 554dffcb26886add95f3260cc21a607ba5e46706 

Branch pushed to git repo; I updated commit sha1. New commits:
554dffc  Update documentation of smith_form

comment:26 Changed 5 years ago by
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:
554dffc  Update documentation of smith_form

comment:27 Changed 5 years ago by
Commit:  554dffcb26886add95f3260cc21a607ba5e46706 → 9cc114e999d46f5f710d631e1f4ebd48036213d8 

Branch pushed to git repo; I updated commit sha1. New commits:
9cc114e  clarify diagonal entries

comment:28 Changed 5 years ago by
Commit:  9cc114e999d46f5f710d631e1f4ebd48036213d8 → e4a9ad729e31ca6edbe94e68a8b85134eaa0e468 

Branch pushed to git repo; I updated commit sha1. New commits:
e4a9ad7  Implement integral for smith normal form over local rings

comment:29 Changed 5 years ago by
Commit:  e4a9ad729e31ca6edbe94e68a8b85134eaa0e468 → 502c8872f4db9c738b36947dca442e875b4cd70a 

comment:30 Changed 5 years ago by
Authors:  Xavier Caruso → Xavier Caruso, Julian Rüth 

Status:  needs_work → needs_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
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.
comment:32 Changed 5 years ago by
Work issues:  failing unit tests → failing 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
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.
The issue is in the INPUT field there.
comment:34 Changed 5 years ago by
Branch:  u/saraedum/padic_smith → u/aly.deines/padic_smith 

comment:35 Changed 5 years ago by
Commit:  502c8872f4db9c738b36947dca442e875b4cd70a → 89ec3ab13eb92d68c4ad2f12b10151041d31aefe 

Status:  needs_review → needs_work 
comment:37 Changed 5 years ago by
*ping*  I could really use this padic smith form. (over ZZp
)
Need help? (not an expert though)
comment:38 Changed 5 years ago by
Cc:  Kiran Kedlaya added 

comment:39 Changed 5 years ago by
Branch:  u/aly.deines/padic_smith → public/23450 

Commit:  89ec3ab13eb92d68c4ad2f12b10151041d31aefe → 8b239f40ab22a1e524073e1a8765d034c86254da 
Status:  needs_work → needs_review 
comment:40 Changed 5 years ago by
Status:  needs_review → needs_work 

comment:41 Changed 5 years ago by
Commit:  8b239f40ab22a1e524073e1a8765d034c86254da → 14f591c94af65b88673f0c295f3c00c093468755 

comment:42 Changed 5 years ago by
Commit:  14f591c94af65b88673f0c295f3c00c093468755 → cf85a341259e09416413bd7b29ec99e8e0597c62 

Branch pushed to git repo; I updated commit sha1. New commits:
cf85a34  Merge branch 'public/23450' of ssh://trac.sagemath.org/sage into t/23450/padic_smith

comment:43 Changed 5 years ago by
Commit:  cf85a341259e09416413bd7b29ec99e8e0597c62 → 7ad838a41517a89f6906ec1fda018e3029db7436 

Branch pushed to git repo; I updated commit sha1. New commits:
7ad838a  Remove _get_matrix_class that was inadvertently added in a merge

comment:44 Changed 5 years ago by
Commit:  7ad838a41517a89f6906ec1fda018e3029db7436 → b5863a1757c05e36e832fd1f743d31127edbe7a0 

Branch pushed to git repo; I updated commit sha1. New commits:
b5863a1  Add newline back in from fix to matrix_space.py

comment:45 Changed 5 years ago by
Commit:  b5863a1757c05e36e832fd1f743d31127edbe7a0 → 777f494e5c8a9924c740c55f636b1e9f10454cb4 

Branch pushed to git repo; I updated commit sha1. New commits:
777f494  Remove the tracks_precision method and update the padic smith form to be able to deal with lattice elements

comment:46 Changed 5 years ago by
Commit:  777f494e5c8a9924c740c55f636b1e9f10454cb4 → d78a1d58857c0a635f6a0f451ccac57e29df28c3 

Branch pushed to git repo; I updated commit sha1. New commits:
d78a1d5  Add exact parameter to _matrix_smith_form, fix precision behavior and allow integral=True for nonpadic matrices

comment:47 Changed 5 years ago by
Authors:  Xavier Caruso, Julian Rüth → Xavier Caruso, Julian Rüth, David Roe 

Reviewers:  Julian Rüth → Julian Rüth, David Roe 
Status:  needs_work → needs_review 
If Xavier is happy with my changes, I'm happy to give this positive review.
comment:48 Changed 5 years ago by
Commit:  d78a1d58857c0a635f6a0f451ccac57e29df28c3 → f7d4e3833eee9ef8138d2d01bb3ffbce400ba9d0 

Branch pushed to git repo; I updated commit sha1. New commits:
f7d4e38  lift_to_precision() was missing at some point

comment:49 Changed 5 years ago by
Commit:  f7d4e3833eee9ef8138d2d01bb3ffbce400ba9d0 → 0d46aa51e56133ec125d90698ffb1974f186a31d 

Branch pushed to git repo; I updated commit sha1. New commits:
0d46aa5  Add a test: Smith form of the zero matrix

comment:50 Changed 5 years ago by
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
Milestone:  sage8.1 

Status:  needs_review → positive_review 
Patchbot is green, so positive review.
comment:52 Changed 5 years ago by
Milestone:  → sage8.2 

comment:53 Changed 5 years ago by
Work issues:  failing unit tests, clarify meaning of integral, talk about precision 

comment:54 Changed 5 years ago by
Status:  positive_review → needs_work 

Tests fail
UnboundLocalError: local variable 'precM' referenced before assignment
comment:55 Changed 5 years ago by
Let me add a bit of details, 6 doctests fails
sage t long /usr/lib64/python2.7/sitepackages/sage/rings/padics/padic_lattice_element.py # 4 doctests failed sage t long /usr/lib64/python2.7/sitepackages/sage/rings/padics/padic_base_leaves.py # 2 doctests failed
and they all fail the same way
File "/usr/lib64/python2.7/sitepackages/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/sitepackages/sage/misc/sage_unittest.py", line 294, in run test_method(tester = tester) File "/usr/lib64/python2.7/sitepackages/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/scimathematics/sage9999/work/sage9999/srcpython2_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/sitepackages/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
Commit:  0d46aa51e56133ec125d90698ffb1974f186a31d → e6f54bb5b0849b7654d645dc63171af9001e7ae9 

comment:58 Changed 5 years ago by
Status:  needs_review → positive_review 

The patchbots continue to be noisy, but this looks good to me.
comment:59 Changed 5 years ago by
Branch:  public/23450 → e6f54bb5b0849b7654d645dc63171af9001e7ae9 

Resolution:  → fixed 
Status:  positive_review → closed 
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:
Smith form of a padic matrix