Smith form of p-adic matrices

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

[saraedum]

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:

​879f4eb

Smith form of a p-adic matrix

[git]

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

​595bc11

Code moved into the category

[caruso]

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.

[git]

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

​1832757	Factorisation of code
​e2cdd99	Small fix

[git]

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

​7ae1018	Move relevant code to sage.matrix.matrix_cdv_dense
​7e73fd2	Fix import
​1fd67fe	Add method tracks_precision()

[git]

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

​1f731ee	Check correctly (hopefully) that precision on input is enough
​1f07da5	Small fixes

[caruso]

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

[saraedum]

I'll try to review this tomorrow.

[git]

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

​55b99df

Small fix in lift_to_maximal_precision

[git]

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

​1ea48ac

Two small bugs fixed

[git]

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

​65ffbc6	Use the name "integral_smith_form" for matrices over CDVF
​f27820a	Small fixes

[saraedum]

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

[saraedum]

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

[saraedum]

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

[saraedum]

sage -t --warn-long 61.6 src/sage/rings/padics/local_generic.py  # 3 doctests failed
sage -t --warn-long 61.6 src/sage/rings/padics/padic_base_leaves.py  # 17 doctests failed
sage -t --warn-long 61.6 src/sage/rings/padics/padic_extension_leaves.py  # 2 doctests failed

[git]

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

​39665f0

S is not square

[saraedum]

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.

[saraedum]

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

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

[git]

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

​554dffc

Update documentation of smith_form

[saraedum]

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

[git]

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

​9cc114e

clarify diagonal entries

[git]

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

​e4a9ad7

Implement integral for smith normal form over local rings

[git]

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

​2a519ab	add itegral handling for Smith form over local rings
​502c887	Add integral keyword to smith_form implementations

[saraedum]

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

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

[saraedum]

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.

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

The issue is in the INPUT field there.

[aly.deines]

New commits:

​1fd5309	Merge branch 'u/saraedum/padic_smith' of git://trac.sagemath.org/sage into t/23450/padic_smith
​89ec3ab	Removed trailing whitespace.

[aly.deines]

Changed to needs work because of above issues.

[sbrandhorst]

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

[chapoton]

New commits:

​d92d3e9	Merge branch 'u/aly.deines/padic_smith' in 8.1.rc4
​8b239f4	trac 23450 details of doc

[git]

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

​93d4e32	Merge branch 'public/23450' in 8.1
​14f591c	fixing 2 doctests

[git]

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

[git]

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

​7ad838a

Remove _get_matrix_class that was inadvertently added in a merge

[git]

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

​b5863a1

Add newline back in from fix to matrix_space.py

[git]

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

​777f494

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

[git]

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 non-padic matrices

[roed]

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

[git]

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

​f7d4e38

lift_to_precision() was missing at some point

[git]

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

​0d46aa5

Add a test: Smith form of the zero matrix

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

[roed]

Patchbot is green, so positive review.

[vbraun]

Tests fail

    UnboundLocalError: local variable 'precM' referenced before assignment

[fbissey]

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.

[git]

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

​0613f84	Recompute precM in the lattice precision framework
​e6f54bb	Merge branch 'develop' into t/23450/public/23450

[caruso]

Should be fixed.

[roed]

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