Post Reply 
About LU factorization
06-04-2015, 09:10 AM
Post: #1
About LU factorization
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

∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C - DM42, DM41X - WP34s Prime Soft. Lib
Visit this user's website Find all posts by this user
Quote this message in a reply
06-04-2015, 09:18 AM
Post: #2
RE: About LU factorization
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
Find all posts by this user
Quote this message in a reply
06-04-2015, 09:52 AM
Post: #3
RE: About LU factorization
(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)...

∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C - DM42, DM41X - WP34s Prime Soft. Lib
Visit this user's website Find all posts by this user
Quote this message in a reply
06-04-2015, 10:15 AM
Post: #4
RE: About LU factorization
(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?
Find all posts by this user
Quote this message in a reply
06-04-2015, 10:22 AM
Post: #5
RE: About LU factorization
Page 83 of the 15C advanced user reference: http://www.hp.com/ctg/Manual/c03308725.pdf


Pauli
Find all posts by this user
Quote this message in a reply
06-04-2015, 10:31 AM
Post: #6
RE: About LU factorization
(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-


Attached File(s) Thumbnail(s)
   
Find all posts by this user
Quote this message in a reply
06-04-2015, 10:36 AM (This post was last modified: 06-04-2015 10:37 AM by Tugdual.)
Post: #7
RE: About LU factorization
(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.
Find all posts by this user
Quote this message in a reply
06-04-2015, 10:45 AM
Post: #8
RE: About LU factorization
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 ....
Find all posts by this user
Quote this message in a reply
06-04-2015, 11:06 AM
Post: #9
RE: About LU factorization
(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 Smile

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? Smile

∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C - DM42, DM41X - WP34s Prime Soft. Lib
Visit this user's website Find all posts by this user
Quote this message in a reply
06-04-2015, 11:30 AM (This post was last modified: 06-04-2015 01:13 PM by DrD.)
Post: #10
RE: About LU factorization
(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!
Find all posts by this user
Quote this message in a reply
06-04-2015, 12:05 PM
Post: #11
RE: About LU factorization
(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

∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C - DM42, DM41X - WP34s Prime Soft. Lib
Visit this user's website Find all posts by this user
Quote this message in a reply
06-04-2015, 12:48 PM (This post was last modified: 06-04-2015 01:11 PM by salvomic.)
Post: #12
RE: About LU factorization
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)

∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C - DM42, DM41X - WP34s Prime Soft. Lib
Visit this user's website Find all posts by this user
Quote this message in a reply
06-04-2015, 01:31 PM
Post: #13
RE: About LU factorization
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?
Find all posts by this user
Quote this message in a reply
06-04-2015, 01:36 PM
Post: #14
RE: About LU factorization
(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.

∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C - DM42, DM41X - WP34s Prime Soft. Lib
Visit this user's website Find all posts by this user
Quote this message in a reply
06-04-2015, 02:12 PM
Post: #15
RE: About LU factorization
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-
Find all posts by this user
Quote this message in a reply
06-04-2015, 02:19 PM
Post: #16
RE: About LU factorization
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!
Find all posts by this user
Quote this message in a reply
06-04-2015, 02:19 PM
Post: #17
RE: About LU factorization
(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...

∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C - DM42, DM41X - WP34s Prime Soft. Lib
Visit this user's website Find all posts by this user
Quote this message in a reply
06-04-2015, 02:22 PM
Post: #18
RE: About LU factorization
(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...

∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C - DM42, DM41X - WP34s Prime Soft. Lib
Visit this user's website Find all posts by this user
Quote this message in a reply
06-04-2015, 04:57 PM
Post: #19
RE: About LU factorization
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

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
Find all posts by this user
Quote this message in a reply
06-04-2015, 05:10 PM
Post: #20
RE: About LU factorization
(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.
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 2 Guest(s)