Opened 12 years ago
Closed 11 years ago
#11259 closed enhancement (fixed)
LU decomposition for matrices with exact base rings
Reported by: | rbeezer | Owned by: | jason, was |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.7.2 |
Component: | linear algebra | Keywords: | sd32 |
Cc: | Merged in: | sage-4.7.2.alpha3 | |
Authors: | Rob Beezer | Reviewers: | Martin Raum |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This is an optimized implementation of the LU decomposition. It runs at about twice the speed of the generic echelon form routine (as theory predicts), so with backsubstitution it might be the basis for a faster solver for systems of linear equations over certain fields.
Apply:
Attachments (4)
Change History (16)
Changed 12 years ago by
Attachment: | trac_11259-exact-LU-decomposition.patch added |
---|
comment:1 Changed 12 years ago by
Authors: | → Rob Beezer |
---|---|
Description: | modified (diff) |
Status: | new → needs_review |
Changed 12 years ago by
Attachment: | trac_11259-exact-LU-decomposition-v2.patch added |
---|
comment:2 Changed 12 years ago by
Description: | modified (diff) |
---|
v2 patch just adds in a few bits and pieces to the documentation.
Patchbot:
Apply trac_11259-exact-LU-decomposition-v2.patch
comment:3 Changed 12 years ago by
Description: | modified (diff) |
---|
Calling this from another routine suggests an "auto" option on the pivoting strategy to allow for a variety of base rings. v3 patch adds that in.
Patchbot:
Apply trac_11259-exact-LU-decomposition-v3.patch
Changed 12 years ago by
Attachment: | trac_11259-exact-LU-decomposition-v3.patch added |
---|
comment:4 Changed 12 years ago by
Let us (try to) wake up the patch buildbot
Apply trac_11259-exact-LU-decomposition-v3.patch
comment:5 follow-up: 8 Changed 11 years ago by
Status: | needs_review → needs_work |
---|
I haven't yet tested this, but from looking at the code I find two things that I would ask you to change:
- the import statements should not go into the method, but rather to the header of the file
- the caching is utterly inefficient, when it comes to 'auto'. In case you deal with 'auto' pivots, would you mind to first convert it to either of the two normal values and than call fetch()? This won't cost much time, but it can save space and also prevents you from computing the same thing twice.
You also might want to try to use add_multiple_of_row to make the implementation either faster or more readable. Not sure whether you have already considered this, but it could be worth a try.
comment:6 follow-up: 7 Changed 11 years ago by
In the light of what we have said about imports in another ticket, I think the comment on imports is void. Just to mention it ...
comment:7 Changed 11 years ago by
Thanks for making that clear. Have not looked at caching yet, but will soon.
Rob
Replying to mraum:
In the light of what we have said about imports in another ticket, I think the comment on imports is void. Just to mention it ...
comment:8 Changed 11 years ago by
Replying to mraum:
- the caching is utterly inefficient, when it comes to 'auto'. In case you deal with 'auto' pivots, would you mind to first convert it to either of the two normal values and than call fetch()? This won't cost much time, but it can save space and also prevents you from computing the same thing twice.
OK, I see now. Pretty bad. ;-) I am thinking to replace 'auto' by None, and early on decide which strategy to employ, then check the cache. Thanks for catching this one.
Changed 11 years ago by
Attachment: | trac_11259-exact-LU-decomposition-caching.patch added |
---|
comment:9 Changed 11 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_work → needs_review |
"caching" patch rearranges the code to do (what I think is) the minimum possible to determine the pivoting strategy, and then goes to check the cache. It fixes the problems with the old 'auto' strategy parameter.
Original version of this code used things like "add_multiple_of_row()". It proved faster to use the "unsafe" methods down in the heart of the nested loops.
comment:10 Changed 11 years ago by
Reviewers: | → Martin Raum |
---|---|
Status: | needs_review → positive_review |
That is what I think is optimal, too. Concerning the add_multiple_of_row: Interesting, I really would have expected the contrary.
comment:11 Changed 11 years ago by
Keywords: | sd32 added |
---|
comment:12 Changed 11 years ago by
Merged in: | → sage-4.7.2.alpha3 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Patchbot:
Apply trac_11259-exact-LU-decomposition.patch