LU decomposition for matrices with exact base rings

[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​

[rbeezer]

Patchbot:

Apply trac_11259-exact-LU-decomposition.patch

[rbeezer]

v2 patch just adds in a few bits and pieces to the documentation.

Patchbot:

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

[rbeezer]

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

[chapoton]

Let us (try to) wake up the patch buildbot

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

[mraum]

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.

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

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

[rbeezer]

Replying to mraum:

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.

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.

[rbeezer]

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

[mraum]

That is what I think is optimal, too. Concerning the add_multiple_of_row: Interesting, I really would have expected the contrary.