search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.47k stars 488 forks source link

LU decomposition for matrices with exact base rings #11259

Closed 1d7ec08f-60ae-4512-91a6-8324c06eab9f closed 13 years ago

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

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. attachment: trac_11259-exact-LU-decomposition-v3.patch
  2. attachment: trac_11259-exact-LU-decomposition-caching.patch

Component: linear algebra

Keywords: sd32

Author: Rob Beezer

Reviewer: Martin Raum

Merged: sage-4.7.2.alpha3

Issue created by migration from https://trac.sagemath.org/ticket/11259

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Author: Rob Beezer

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Description changed:

--- 
+++ 
@@ -1 +1,5 @@
 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. [attachment: trac_11259-exact-LU-decomposition.patch](https://github.com/sagemath/sage-prod/files/10652738/trac_11259-exact-LU-decomposition.patch.gz)
+
1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago
comment:1

Attachment: trac_11259-exact-LU-decomposition.patch.gz

Patchbot:

Apply trac_11259-exact-LU-decomposition.patch

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago
comment:2

Attachment: trac_11259-exact-LU-decomposition-v2.patch.gz

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

Patchbot:

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

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,5 @@
 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. [attachment: trac_11259-exact-LU-decomposition.patch](https://github.com/sagemath/sage-prod/files/10652738/trac_11259-exact-LU-decomposition.patch.gz)
+1. [attachment: trac_11259-exact-LU-decomposition-v2.patch](https://github.com/sagemath/sage-prod/files/10652739/trac_11259-exact-LU-decomposition-v2.patch.gz)
1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,5 @@
 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. [attachment: trac_11259-exact-LU-decomposition-v2.patch](https://github.com/sagemath/sage-prod/files/10652739/trac_11259-exact-LU-decomposition-v2.patch.gz)
+1. [attachment: trac_11259-exact-LU-decomposition-v3.patch](https://github.com/sagemath/sage-prod/files/10652740/trac_11259-exact-LU-decomposition-v3.patch.gz)
1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago
comment:3

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

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Attachment: trac_11259-exact-LU-decomposition-v3.patch.gz

fchapoton commented 13 years ago
comment:4

Let us (try to) wake up the patch buildbot

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

18d65770-dc1e-4813-89a9-4828e4aae4a9 commented 13 years ago
comment:5

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.

18d65770-dc1e-4813-89a9-4828e4aae4a9 commented 13 years ago
comment:6

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

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago
comment:7

Thanks for making that clear. Have not looked at caching yet, but will soon.

Rob

Replying to @sagetrac-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 ...

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago
comment:8

Replying to @sagetrac-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.

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Attachment: trac_11259-exact-LU-decomposition-caching.patch.gz

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago
comment:9

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

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Description changed:

--- 
+++ 
@@ -2,4 +2,5 @@

 **Apply:**
 1. [attachment: trac_11259-exact-LU-decomposition-v3.patch](https://github.com/sagemath/sage-prod/files/10652740/trac_11259-exact-LU-decomposition-v3.patch.gz)
+2. [attachment: trac_11259-exact-LU-decomposition-caching.patch](https://github.com/sagemath/sage-prod/files/10652741/trac_11259-exact-LU-decomposition-caching.patch.gz)
18d65770-dc1e-4813-89a9-4828e4aae4a9 commented 13 years ago

Reviewer: Martin Raum

18d65770-dc1e-4813-89a9-4828e4aae4a9 commented 13 years ago
comment:10

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

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 13 years ago

Changed keywords from none to sd32

83660e46-0051-498b-a8c1-f7a7bd232b5a commented 13 years ago

Merged: sage-4.7.2.alpha3