Smith form of p-adic matrices

[xcaruso]

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

CC: @roed314 @saraedum @sagetrac-TristanVaccon @kedlaya

Component: padics

Keywords: sd87

Author: Xavier Caruso, Julian Rüth, David Roe

Branch/Commit: e6f54bb

Reviewer: Julian Rüth, David Roe

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

[xcaruso]

Branch: u/caruso/padic_smith

[saraedum]

comment:2

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

[saraedum]

Commit: 879f4eb

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

595bc11

Code moved into the category

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 879f4eb to 595bc11

[xcaruso]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 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), together with a new implementation of the method `determinant` making use of Smith normal form and improving this way its behaviour regarding precision.
+This ticket provides a (currently unoptimized) implementation of Smith normal form over complete discrete valuation rings/fields (e.g. p-adic rings/fields).

[xcaruso]

comment:5

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 595bc11 to e2cdd99

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1832757	Factorisation of code
e2cdd99	Small fix

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e2cdd99 to 1fd67fe

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1fd67fe to 1f07da5

[xcaruso]

comment:9

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

[saraedum]

comment:10

I'll try to review this tomorrow.

[saraedum]

Reviewer: Julian Rüth

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

55b99df

Small fix in lift_to_maximal_precision

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1f07da5 to 55b99df

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1ea48ac

Two small bugs fixed

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 55b99df to 1ea48ac

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1ea48ac to f27820a

[saraedum]

Work Issues: drop lift_to_maximal_precision

[saraedum]

Changed work issues from drop lift_to_maximal_precision to none

[saraedum]

comment:15

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

[saraedum]

Changed branch from u/caruso/padic_smith to u/saraedum/padic_smith

[saraedum]

Changed branch from u/saraedum/padic_smith to u/caruso/padic_smith

[saraedum]

comment:17

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

[saraedum]

Changed branch from u/caruso/padic_smith to u/saraedum/padic_smith

[saraedum]

Changed commit from f27820a to e635699

[saraedum]

Work Issues: failing unit tests

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

comment:20

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

39665f0

S is not square

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e635699 to 39665f0

[saraedum]

comment:22

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]

comment:23

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

[xcaruso]

comment:24

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 39665f0 to 554dffc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

554dffc

Update documentation of smith_form

[saraedum]

comment:26

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9cc114e

clarify diagonal entries

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 554dffc to 9cc114e

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e4a9ad7

Implement integral for smith normal form over local rings

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9cc114e to e4a9ad7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e4a9ad7 to 502c887

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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]

comment:30

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

[saraedum]

Changed author from Xavier Caruso to Xavier Caruso, Julian Rüth

[xcaruso]

comment:31

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.