Opened 7 years ago
Closed 3 years ago
#17272 closed defect (fixed)
Use pivoting for Gaussian elimination on matrices over padics
Reported by:  roed  Owned by:  

Priority:  critical  Milestone:  sage8.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: 
Description
sage: R = ZpCA(5,5,print_mode='valunit') 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 3 years ago by
 Branch set to u/assaferan/use_pivoting_for_gaussian_elimination_on_matrices_over_p_adics
comment:2 Changed 3 years ago by
 Commit set to db5591c9682b05640339bc7425f8691a8841ac23
 Status changed from new to needs_review
comment:3 Changed 3 years ago by
 Commit changed from db5591c9682b05640339bc7425f8691a8841ac23 to a05823af07e37f4399e994894943b8fbe76db1f2
comment:4 Changed 3 years ago by
 Milestone changed from sage6.4 to sage8.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
 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
 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
 Branch changed from u/assaferan/use_pivoting_for_gaussian_elimination_on_matrices_over_p_adics to u/tscrim/pivot_gaussian_elimination_p_adics17272
 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_adics17272

2bd0f37  Some code cleanup.

comment:8 Changed 3 years ago by
 Status changed from needs_review to positive_review
The changes seem to be in order, hence I'm setting to a positive review.
comment:9 Changed 3 years ago by
 Branch changed from u/tscrim/pivot_gaussian_elimination_p_adics17272 to 2bd0f378e045561afe429f5aea849979838a335b
 Resolution set to fixed
 Status changed from positive_review to closed
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:
D