Opened 7 years ago

Closed 4 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:2 Changed 4 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:

 ​db5591c `D`

### comment:3 Changed 4 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 4 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 4 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 4 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 4 years ago by tscrim

• 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 4 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 4 years ago by assaferan (previous) (diff)

### comment:9 Changed 4 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.