About LU factorization

06042015, 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 

06042015, 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 

06042015, 09:52 AM
Post: #3




RE: About LU factorization
(06042015 09:18 AM)Paul Dale Wrote: Have you tried reversing the decomposition to see if you get the original matrix back? 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 

06042015, 10:15 AM
Post: #4




RE: About LU factorization  
06042015, 10:22 AM
Post: #5




RE: About LU factorization  
06042015, 10:31 AM
Post: #6




RE: About LU factorization
(06042015 09:10 AM)salvomic Wrote: hi, 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 

06042015, 10:36 AM
(This post was last modified: 06042015 10:37 AM by Tugdual.)
Post: #7




RE: About LU factorization
(06042015 10:22 AM)Paul Dale Wrote: Page 83 of the 15C advanced user reference: http://www.hp.com/ctg/Manual/c03308725.pdf I mean on the prime. I did a Crout on the 50g and get the exact same results as the prime. 

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

06042015, 11:06 AM
Post: #9




RE: About LU factorization
(06042015 10:45 AM)DrD Wrote: Found on the internet: 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? ∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C  DM42, DM41X  WP34s Prime Soft. Lib 

06042015, 11:30 AM
(This post was last modified: 06042015 01:13 PM by DrD.)
Post: #10




RE: About LU factorization
(06042015 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! 

06042015, 12:05 PM
Post: #11




RE: About LU factorization
(06042015 11:30 AM)DrD Wrote: For your matrix M1:=!([[2,1,1],[4,−6,0],[−2,7,2]], I get: 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 

06042015, 12:48 PM
(This post was last modified: 06042015 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 

06042015, 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? 

06042015, 01:36 PM
Post: #14




RE: About LU factorization
(06042015 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: 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 

06042015, 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 

06042015, 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!


06042015, 02:19 PM
Post: #17




RE: About LU factorization
(06042015 02:12 PM)DrD Wrote: I get: 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 

06042015, 02:22 PM
Post: #18




RE: About LU factorization
(06042015 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 

06042015, 04:57 PM
Post: #19




RE: About LU factorization
In my time (admittedly a while ago..), Crout LUfactorisation reordered the operations so that each element (in L or U) was computed using a dot product. Using floating2 (showing my age) or, in the 42S/48S world, 15digit 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 15digit 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 

06042015, 05:10 PM
Post: #20




RE: About LU factorization  
« Next Oldest  Next Newest »

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