Opened 7 years ago

Closed 4 years ago

#17272 closed defect (fixed)

Use pivoting for Gaussian elimination on matrices over p-adics

Reported by: roed Owned by:
Priority: critical Milestone: sage-8.3
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Eran Assaf Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 2bd0f37 (Commits, GitHub, GitLab) Commit: 2bd0f378e045561afe429f5aea849979838a335b
Dependencies: Stopgaps:

Status badges

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

Change History (9)

comment:1 Changed 4 years ago by assaferan

  • Branch set to u/assaferan/use_pivoting_for_gaussian_elimination_on_matrices_over_p_adics

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:

db5591cD

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:

a380cf9Using partial pivoting resulted in many more accurate results for p-adic modular forms
a05823aFixed 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:

23e6363Added 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

  • 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:

0584db7Merge 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
2bd0f37Some 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.