About LU factorization - Printable Version +- HP Forums ( https://www.hpmuseum.org/forum)+-- Forum: HP Calculators (and very old HP Computers) ( /forum-3.html)+--- Forum: HP Prime ( /forum-5.html)+--- Thread: About LU factorization ( /thread-4071.html)Pages: 1 2 |

About LU factorization - salvomic - 06-04-2015 09:10 AM
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 RE: About LU factorization - Paul Dale - 06-04-2015 09:18 AM
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 RE: About LU factorization - salvomic - 06-04-2015 09:52 AM
(06-04-2015 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)... RE: About LU factorization - Tugdual - 06-04-2015 10:15 AM
(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? RE: About LU factorization - Paul Dale - 06-04-2015 10:22 AM
Page 83 of the 15C advanced user reference: http://www.hp.com/ctg/Manual/c03308725.pdf Pauli RE: About LU factorization - DrD - 06-04-2015 10:31 AM
(06-04-2015 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- RE: About LU factorization - Tugdual - 06-04-2015 10:36 AM
(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 I mean on the prime. I did a Crout on the 50g and get the exact same results as the prime. RE: About LU factorization - DrD - 06-04-2015 10:45 AM
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 .... RE: About LU factorization - salvomic - 06-04-2015 11:06 AM
(06-04-2015 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? RE: About LU factorization - DrD - 06-04-2015 11:30 AM
(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! RE: About LU factorization - salvomic - 06-04-2015 12:05 PM
(06-04-2015 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 RE: About LU factorization - salvomic - 06-04-2015 12:48 PM
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) RE: About LU factorization - DrD - 06-04-2015 01:31 PM
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? RE: About LU factorization - salvomic - 06-04-2015 01:36 PM
(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: yes, it helps! I'm also investigating on probably different settings... In the meantime I'll make some confronts with Wolfram. RE: About LU factorization - DrD - 06-04-2015 02:12 PM
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- RE: About LU factorization - DrD - 06-04-2015 02:19 PM
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! RE: About LU factorization - salvomic - 06-04-2015 02:19 PM
(06-04-2015 02:12 PM)DrD Wrote: I get: ok, but, are you using firmware 7820 also? If yes, I don't understand the difference... RE: About LU factorization - salvomic - 06-04-2015 02:22 PM
(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... RE: About LU factorization - Werner - 06-04-2015 04:57 PM
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 RE: About LU factorization - Gerald H - 06-04-2015 05:10 PM
(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. |