Opened 10 years ago

Closed 10 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:

Status badges

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 10 years ago.
trac_11259-exact-LU-decomposition-v2.patch (17.5 KB) - added by rbeezer 10 years ago.
trac_11259-exact-LU-decomposition-v3.patch (18.7 KB) - added by rbeezer 10 years ago.
trac_11259-exact-LU-decomposition-caching.patch (7.7 KB) - added by rbeezer 10 years ago.

Download all attachments as: .zip

Change History (16)

Changed 10 years ago by rbeezer

comment:1 Changed 10 years ago by rbeezer

  • Authors set to Rob Beezer
  • Description modified (diff)
  • Status changed from new to needs_review

Patchbot:

Apply trac_11259-exact-LU-decomposition.patch

Changed 10 years ago by rbeezer

comment:2 Changed 10 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 10 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 10 years ago by rbeezer

comment:4 Changed 10 years ago by chapoton

Let us (try to) wake up the patch buildbot

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

comment:5 follow-up: Changed 10 years ago by mraum

  • Status changed from needs_review to 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:

  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 follow-up: Changed 10 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 10 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 10 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 10 years ago by rbeezer

  • Description modified (diff)
  • Status changed from needs_work to 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 10 years ago by mraum

  • Reviewers set to Martin Raum
  • Status changed from needs_review to 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 10 years ago by rbeezer

  • Keywords sd32 added

comment:12 Changed 10 years ago by leif

  • Merged in set to sage-4.7.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.