06-04-2015, 09:10 AM
Post: #1
 salvomic Senior Member Posts: 1,394 Joined: Jan 2015
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
06-04-2015, 09:18 AM
Post: #2
 Paul Dale Senior Member Posts: 1,761 Joined: Dec 2013
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
06-04-2015, 09:52 AM
Post: #3
 salvomic Senior Member Posts: 1,394 Joined: Jan 2015
(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
06-04-2015, 10:15 AM
Post: #4
 Tugdual Senior Member Posts: 756 Joined: Dec 2013
(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?
06-04-2015, 10:22 AM
Post: #5
 Paul Dale Senior Member Posts: 1,761 Joined: Dec 2013
Page 83 of the 15C advanced user reference: http://www.hp.com/ctg/Manual/c03308725.pdf

Pauli
06-04-2015, 10:31 AM
Post: #6
 DrD Senior Member Posts: 1,132 Joined: Feb 2014
(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)

06-04-2015, 10:36 AM (This post was last modified: 06-04-2015 10:37 AM by Tugdual.)
Post: #7
 Tugdual Senior Member Posts: 756 Joined: Dec 2013
(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.
06-04-2015, 10:45 AM
Post: #8
 DrD Senior Member Posts: 1,132 Joined: Feb 2014
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 ....
06-04-2015, 11:06 AM
Post: #9
 salvomic Senior Member Posts: 1,394 Joined: Jan 2015
(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?

∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C - DM42, DM41X - WP34s Prime Soft. Lib
06-04-2015, 11:30 AM (This post was last modified: 06-04-2015 01:13 PM by DrD.)
Post: #10
 DrD Senior Member Posts: 1,132 Joined: Feb 2014
(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!
06-04-2015, 12:05 PM
Post: #11
 salvomic Senior Member Posts: 1,394 Joined: Jan 2015
(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
06-04-2015, 12:48 PM (This post was last modified: 06-04-2015 01:11 PM by salvomic.)
Post: #12
 salvomic Senior Member Posts: 1,394 Joined: Jan 2015
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
06-04-2015, 01:31 PM
Post: #13
 DrD Senior Member Posts: 1,132 Joined: Feb 2014
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?
06-04-2015, 01:36 PM
Post: #14
 salvomic Senior Member Posts: 1,394 Joined: Jan 2015
(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
06-04-2015, 02:12 PM
Post: #15
 DrD Senior Member Posts: 1,132 Joined: Feb 2014
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-
06-04-2015, 02:19 PM
Post: #16
 DrD Senior Member Posts: 1,132 Joined: Feb 2014
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!
06-04-2015, 02:19 PM
Post: #17
 salvomic Senior Member Posts: 1,394 Joined: Jan 2015
(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
06-04-2015, 02:22 PM
Post: #18
 salvomic Senior Member Posts: 1,394 Joined: Jan 2015
(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
06-04-2015, 04:57 PM
Post: #19
 Werner Senior Member Posts: 714 Joined: Dec 2013
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
06-04-2015, 05:10 PM
Post: #20
 Gerald H Senior Member Posts: 1,522 Joined: May 2014