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:

GitHub link to the corresponding issue

Description (last modified by rbeezer)

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:

  1. trac_11259-exact-LU-decomposition-v3.patch
  2. trac_11259-exact-LU-decomposition-caching.patch

Attachments (4)

trac_11259-exact-LU-decomposition.patch (16.2 KB) - added by rbeezer 12 years ago.
trac_11259-exact-LU-decomposition-v2.patch (17.5 KB) - added by rbeezer 12 years ago.
trac_11259-exact-LU-decomposition-v3.patch (18.7 KB) - added by rbeezer 12 years ago.
trac_11259-exact-LU-decomposition-caching.patch (7.7 KB) - added by rbeezer 11 years ago.

Download all attachments as: .zip

Change History (16)

Changed 12 years ago by rbeezer

comment:1 Changed 12 years ago by rbeezer

Authors: Rob Beezer
Description: modified (diff)
Status: newneeds_review

Patchbot:

Apply trac_11259-exact-LU-decomposition.patch

Changed 12 years ago by rbeezer

comment:2 Changed 12 years ago by rbeezer

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 rbeezer

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 rbeezer

comment:4 Changed 12 years ago by chapoton

Let us (try to) wake up the patch buildbot

Apply trac_11259-exact-LU-decomposition-v3.patch

comment:5 Changed 11 years ago by mraum

Status: needs_reviewneeds_work

I haven't yet tested this, but from looking at the code I find two things that I would ask you to change:

  1. the import statements should not go into the method, but rather to the header of the file
  2. 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 Changed 11 years ago by 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:7 in reply to:  6 Changed 11 years ago by rbeezer

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 in reply to:  5 Changed 11 years ago by rbeezer

Replying to mraum:

  1. 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.

comment:9 Changed 11 years ago by rbeezer

Description: modified (diff)
Status: needs_workneeds_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 mraum

Reviewers: Martin Raum
Status: needs_reviewpositive_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 rbeezer

Keywords: sd32 added

comment:12 Changed 11 years ago by leif

Merged in: sage-4.7.2.alpha3
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.