About LU factorization

[salvomic]

hi,
is seems that for LU in help there isn't anything.
LU gives permutation vector, Lower and Upper decomposition.

Having the matrix [[2,1,1], [4,-6,0], [-2,7,2]], after Linear Algebra books I should get L=[[1,0,0], [2,1,0], [-1,-1,1]] and U=[[2,1,1], [0,-8,-2], [0,0,1]]
in L under diagonal there are the "multipliers" (2, -1, -1: subtract 2 time row 1st from 2nd and so on), in U the diagonal items (2,-8,1) are the pivots.

In the Prime I get [1,3,2] (vector for permutation) and then
L=[[1,0,0], [-1,1,0], [2,-1,1]] and U=[[2,1,1], [0,8,3], [0,0,1]] (as the pivots would be 0, +8, 1, but the second should be -8).

I would like to understand why that difference showing the results...

thank you,
Salvo

[Paul Dale]

Have you tried reversing the decomposition to see if you get the original matrix back?

Looks like the prime swapped the second and third rows during the factorisation which changes the later results.

Earlier HP calculators use the Doolittle decomposition with partial pivots, I'd be surprised if the prime didn't do something similar.


- Pauli

[salvomic]

(06-04-2015 09:18 AM)Paul Dale Wrote:  Have you tried reversing the decomposition to see if you get the original matrix back?

Looks like the prime swapped the second and third rows during the factorisation which changes the later results.

Earlier HP calculators use the Doolittle decomposition with partial pivots, I'd be surprised if the prime didn't do something similar.

- Pauli

hi Pauli,
swapping 2nd and 3rd row LU give same L and U and (obviously) [1,2,3] for the permutation matrix...

Prime has pivot() but this function returns only a column "pivoted", i.e.
pivot(,[[2,1,1], [4,-6,0], [-2,7,2]],1,1) returns
[[2,1,1], [0,-16,-4], [0,16,6,28]]
so then we must do a loop: divide by the nth pivot, take the minor (delete 1st row, 1st column), use pivot() again...
(In another post about pivots I'm trying to do a program, but I've still troubles)...

[Tugdual]

(06-04-2015 09:18 AM)Paul Dale Wrote:  Earlier HP calculators use the Doolittle decomposition with partial pivots, I'd be surprised if the prime didn't do something similar.

I thought it was Crout?

[Paul Dale]

Page 83 of the 15C advanced user reference: http://www.hp.com/ctg/Manual/c03308725.pdf


Pauli

[DrD]

(06-04-2015 09:10 AM)salvomic Wrote:  hi,
is seems that for LU in help there isn't anything.
LU gives permutation vector, Lower and Upper decomposition.

Salvo

Hi Salvo,

In LU() help, I see the screen capture attached. Is this missing in your version?

For square matrices, LU returns a list: {Lower Triangular, Upper Triangular, and Permutation}. Using the factors from the list, returns your original matrix.

-Dale-

[Tugdual]

(06-04-2015 10:22 AM)Paul Dale Wrote:  Page 83 of the 15C advanced user reference: http://www.hp.com/ctg/Manual/c03308725.pdf


Pauli

I mean on the prime. I did a Crout on the 50g and get the exact same results as the prime.

[DrD]

Found on the internet:

"LU factorization (when it exists) is not unique. If L has 1's on it's diagonal, then it is called a Doolittle factorization. If U has 1's on its diagonal, then it is called a Crout factorization. When L=Ut or U=Lt, it is called a Cholesky decomposition. "

-Dale-
So much to learn, so little time ....

[salvomic]

(06-04-2015 10:45 AM)DrD Wrote:  Found on the internet:

"LU factorization (when it exists) is not unique. If L has 1's on it's diagonal, then it is called a Doolittle factorization. If U has 1's on its diagonal, then it is called a Crout factorization. When L=Ut or U=Lt, it is called a Cholesky decomposition. "

-Dale-
So much to learn, so little time ....

right

so, is the Prime using Doolittle? Please, could it use *both* methods, to choose one? ;-)

However, I would like to use LU to get pivots (diagonal U), then to get LDU (LDV) factorization and at the end also LDLt factorization.
(I'm following Gilbert Strang's books, for now)...
Having the diagonal with d (pivots), L and U (with all 1 in diagonal), it's simple to get LDU (with U items, except diagonal, u12/d1, u13/d1... u21/d2...)
And if A is a symmetric matrix, using D we get L and Lt (L transpose) to have LDLt...

Doesn't the Prime return a list of pivot in a simple way?

[DrD]

(06-04-2015 11:06 AM)salvomic Wrote:  so, is the Prime using Doolittle? Please, could it use *both* methods, to choose one? ;-)

For your matrix M1:=[[2,1,1],[4,−6,0],[−2,7,2]], I get:

L1:=LU(M1) = {[[1,0,0],[0.5,1,0],[−0.5,1,1]],[[4,−6,0],[0,4,1],[0,0,1]],[[0,1,0],[1,0,0],[0,0,1]]}

Since L1(1)=[[1,0,0],[0.5,1,0],[−0.5,1,1]] (Lower triangular, has one's in diagonal) it would be the Doolittle method.

By the way, I went through Gil Strang's MIT online classes. I really enjoyed them!

[salvomic]

(06-04-2015 11:30 AM)DrD Wrote:  For your matrix M1:=!([[2,1,1],[4,−6,0],[−2,7,2]], I get:

L1:=LU(M1) = {[[1,0,0],[0.5,1,0],[−0.5,1,1]],[[4,−6,0],[0,4,1],[0,0,1]],[[0,1,0],[1,0,0],[0,0,1]]}

Since L1(1)=[[1,0,0],[0.5,1,0],[−0.5,1,1]] (Lower triangular, has one's in diagonal) it would be the Doolittle method.

By the way, I went through Gil Strang's MIT online classes. I really enjoyed them!

Gil Strang books are also amazing, not only good to learn, yes.

Maybe you've transcript different numbers for matrix or LU, or we are using different LU() or...
I get {[1,3,2], [[1,0,0], [-1,1,0], [2,-1,1]], [[2,1,1], [0,8,3], [0,0,1]]}, I'm curious...

Salvo

[salvomic]

Dale,
I found this:
if I reorder a matrix like the "permutation" vector given by LU() (i.e. [1,3,2] for our matrix) LU() gives the same pivots like my (much imperfect try to write a program to calculate pivots: see here: GaussJordan() ).

In our example (first LU gave [1,3,2]...) I get:
M1:= [[2,1,1], [-2,7,2], [4,-6,0]]
LU(M1) -> {[1,2,3], [[1,0,0], [-1,1,0], [2,-1,1]], [[2,1,1], [0,8,3], [0,0,1]]} (Doolittle; pivots in U: 2,8,1)
my program gives: gaussJordan([[2,1,1], [-2,7,2], [4,-6,0]]) -> [[2,8,1], [[2,1,1], [0,8,3], [0,0,1]]] (by the way REF(M1) -> [[1,0.5,0.5], [0,1,0.25], [0,0,1]])

I would like to understand how to get the result presented by Strange (pivots: 2, -8, 1 and so on)...
(EDIT: The example of Gil Strange is intended for LU factorization without swapping of rows)

[DrD]

I don't know why my results are different, maybe a setting. I'll investigate. In the meantime, Wolfram Alpha gives this:

LU Decomposition

Any help?

[salvomic]

(06-04-2015 01:31 PM)DrD Wrote:  I don't know why my results are different, maybe a setting. I'll investigate. In the meantime, Wolfram Alpha gives this:

LU Decomposition

Any help?

yes, it helps!
I'm also investigating on probably different settings...
In the meantime I'll make some confronts with Wolfram.

[DrD]

I get:

M1:=[[2,1,1],[−2,7,2],[4,−6,0]]; // Your matrix input ...
L1:=LU(M1); // --> {[[1,0,0],[−0.5,1,0],[0.5,1,1]],[[4,−6,0],[0,4,2],[0,0,−1]],[[0,0,1],[0,1,0],[1,0,0]]}

L1(1)*L1(2)/L1(3); // --> [[2,1,1],[−2,7,2],[4,−6,0]] ...Your matrix back again

My list (L1) is simply the Lower Triangular, Upper Triangular, and Permutation matrices, which is what the help description states.

You get:

M1:= [[2,1,1], [-2,7,2], [4,-6,0]]; // Same matrix as above
LU(M1); // -> {[1,2,3], [[1,0,0], [-1,1,0], [2,-1,1]], [[2,1,1], [0,8,3], [0,0,1]]}

If you set L1 to your list, then L1(2)*L1(3) returns your original matrix.

There's a different format in our list results, you get a vector and the Lower and Upper triangular matrices. Something seems to have changed in the versions, but both results seem to be okay.

-Dale-

[DrD]

From my very foggy memory, I think I may recall Gil mentioning an error in his book, and it may be in those pivots [2, 8, 1] versus [2, -8, 1]. It was during one of his class sessions. Since I don't have his book, I didn't make note of that detail. I do remember SOMETHING like that, though!

[salvomic]

(06-04-2015 02:12 PM)DrD Wrote:  I get:

...
There's a different format in our list results, you get a vector and the Lower and Upper triangular matrices. Something seems to have changed in the versions, but both results seem to be okay.

-Dale-

ok, but, are you using firmware 7820 also?
If yes, I don't understand the difference...

[salvomic]

(06-04-2015 02:19 PM)DrD Wrote:  From my very foggy memory, I think I may recall Gil mentioning an error in his book, and it may be in those pivots [2, 8, 1] versus [2, -8, 1]. It was during one of his class sessions. Since I don't have his book, I didn't make note of that detail. I do remember SOMETHING like that, though!

maybe!
this example is explained in many parts of his book "Linear algebra and its applications" (4th edition) and I've here the Italian translation...

[Werner]

In my time (admittedly a while ago..), Crout LU-factorisation reordered the operations so that each element (in L or U) was computed using a dot product. Using floating-2 (showing my age) or, in the 42S/48S world, 15-digit intermediate results, one could obtain far better results at almost no cost.
Crout factorisation alternatingly computes a row and a column. In that sense, the 42S/48S algorithms (while being 'Doolittle factorisations') are also Crout factorisation as they do use 15-digit dot products. Don't know what the Prime does, however.
The 48G and onwards (up till, and including, the 50g) use 15 digits for all their matrix computations (the matrix is first converted to 15 digits, then all operations are performed, then it is rounded back to 12 digits).
Cheers, Werner

[Gerald H]

(06-04-2015 04:57 PM)Werner Wrote:  In that sense, the 42S/48S algorithms (while being 'Doolittle factorisations') are also Crout factorisation as they do use 15-digit dot products. Don't know what the Prime does, however.

I can't see that the 42S does any matrix factorisation.