Use pivoting for Gaussian elimination on matrices over p-adics

[roed314]

sage: R = ZpCA(5,5,print_mode='val-unit')
sage: A = matrix(R,3,3,[250,2369,1147,106,927,362,90,398,2483])
sage: A
[5^3 * 2 + O(5^5)    2369 + O(5^5)    1147 + O(5^5)]
[    106 + O(5^5)     927 + O(5^5)     362 + O(5^5)]
[ 5 * 18 + O(5^5)     398 + O(5^5)    2483 + O(5^5)]
sage: A.det()
2634 + O(5^5)
sage: ~A
Traceback (most recent call last):
...
ZeroDivisionError: input matrix must be nonsingular

The problem is that Sage doesn't pivot when doing Gaussian elimination:

sage: K = R.fraction_field()
sage: A.change_ring(K).augment(identity_matrix(K,3))._echelon_classical()
[       1 + O(5^2)           O(5^-1)           O(5^-1)           O(5^-1)            O(5^2)   5^-1 * 7 + O(5)]
[           O(5^2)        1 + O(5^2)       13 + O(5^2)        4 + O(5^2)            O(5^5) 5^2 * 19 + O(5^4)]
[           O(5^3)            O(5^0)            O(5^0)            O(5^0)        1 + O(5^2)   5^-1 * 8 + O(5)]

Component: linear algebra

Author: Eran Assaf

Branch/Commit: 2bd0f37

Reviewer: Travis Scrimshaw

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

[assaferan]

Branch: u/assaferan/use_pivoting_for_gaussian_elimination_on_matrices_over_p_adics

[assaferan]

Commit: db5591c

[assaferan]

comment:2

Hi,
I have added partial pivoting and scaled partial pivoting to the code,
including some examples for doctesting.
For now, I set scaled partial pivoting to be the default algorithm only for discrete valuation fields. This is until we will have a better framework for general valuation rings.

Also, I have not implemented complete pivoting, as it is only rarely needed and very inefficient.

---

New commits:

db5591c

D

[assaferan]

Author: Eran Assaf

[sagetrac-git]

Changed commit from db5591c to a05823a

[sagetrac-git]

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

a380cf9	Using partial pivoting resulted in many more accurate results for p-adic modular forms
a05823a	Fixed a bug in scaled partial pivoting

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:4

Not all methods have a doctest. Also, do you want to c(p)def some of the methods? Since they are currently python methods, I don't see the point of the sig_check(). Also, there seems to be some code redundancy, is there a way you could mitigate that?

[sagetrac-git]

Changed commit from a05823a to 23e6363

[sagetrac-git]

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

23e6363

Added several doctests, cpdefined the functions and mitigated some of the code redundancy.

[assaferan]

comment:6

Hi,
I cpdef'd the functions, and mitigated the code redundancy. Also added doctests where they were none.

[tscrim]

comment:7

I did a little bit of cleanup. In particular, I factored out the classical algorithm to simplify the code to help keep it fast. If my changes are good, then you can set a positive review.

---

New commits:

0584db7	Merge branch 'u/assaferan/use_pivoting_for_gaussian_elimination_on_matrices_over_p_adics' of git://trac.sagemath.org/sage into u/tscrim/pivot_gaussian_elimination_p_adics-17272
2bd0f37	Some code cleanup.

[tscrim]

Changed branch from u/assaferan/use_pivoting_for_gaussian_elimination_on_matrices_over_p_adics to u/tscrim/pivot_gaussian_elimination_p_adics-17272

[tscrim]

Changed commit from 23e6363 to 2bd0f37

[assaferan]

comment:8

The changes seem to be in order, hence I'm setting to a positive review.

[vbraun]

Changed branch from u/tscrim/pivot_gaussian_elimination_p_adics-17272 to 2bd0f37