Opened 7 years ago

Closed 3 years ago

# Use pivoting for Gaussian elimination on matrices over p-adics

Reported by: Owned by: roed critical sage-8.3 linear algebra Eran Assaf Travis Scrimshaw N/A 2bd0f37 2bd0f378e045561afe429f5aea849979838a335b

### Description

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

### comment:1 Changed 3 years ago by assaferan

• Branch set to u/assaferan/use_pivoting_for_gaussian_elimination_on_matrices_over_p_adics

### comment:2 Changed 3 years ago by assaferan

• Authors set to Eran Assaf
• Commit set to db5591c9682b05640339bc7425f8691a8841ac23
• Status changed from new to needs_review

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:

### comment:3 Changed 3 years ago by git

• Commit changed from db5591c9682b05640339bc7425f8691a8841ac23 to a05823af07e37f4399e994894943b8fbe76db1f2

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

### comment:4 Changed 3 years ago by tscrim

• Milestone changed from sage-6.4 to sage-8.3
• Reviewers set to Travis Scrimshaw
• Status changed from needs_review to needs_work

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?

### comment:5 Changed 3 years ago by git

• Commit changed from a05823af07e37f4399e994894943b8fbe76db1f2 to 23e636373f08fb92a3216c6663c8ebb67bf66880

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.

### comment:6 Changed 3 years ago by assaferan

• Status changed from needs_work to needs_review

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

### comment:7 Changed 3 years ago by tscrim

• Branch changed from u/assaferan/use_pivoting_for_gaussian_elimination_on_matrices_over_p_adics to u/tscrim/pivot_gaussian_elimination_p_adics-17272
• Commit changed from 23e636373f08fb92a3216c6663c8ebb67bf66880 to 2bd0f378e045561afe429f5aea849979838a335b

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.

### comment:8 Changed 3 years ago by assaferan

• Status changed from needs_review to positive_review

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

Last edited 3 years ago by assaferan (previous) (diff)

### comment:9 Changed 3 years ago by vbraun

• Branch changed from u/tscrim/pivot_gaussian_elimination_p_adics-17272 to 2bd0f378e045561afe429f5aea849979838a335b
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.