Interpreting output of WP34s M.LU (likely bug)

11102019, 05:30 PM
Post: #1




Interpreting output of WP34s M.LU (likely bug)
Hello all,
I am teaching linear algebra this fall, so I started playing with the 34s' matrix routines. It's a bit of an exercise in minimalism, but I don't mind. As best I can tell, the operation for LU factorization (through the MATRIX catalog function M.LU) is not reporting the row permutations applied to the input matrix correctly. Let me explain. Per the manual, M.LU takes as input, in X, the descriptor of a square matrix (let's call this matrix A) and, upon replacing A in situ with its LU factorization (strictly speaking, as a side effect of M.LU), M.LU returns (in X) a "descriptor" of the pivots used in the LU process. I have tried several examples, but here is one: Consider the matrix Code:
Code:
Code:
By multiplying LU, we see that Code:
This new matrix B is obtained from A by a simple exchange of the first two rows. I believe that M.LU should return the "descriptor" (of row exchanges) Code:
Code:
As a side note, I noticed that the LINEQS operation solves Ax = y always taking as input (the descriptor of) a "regular" square matrix A, rather than (possibly) the descriptor of a matrix that is already in LU form. A superficial look at the 34s code suggests that LINEQS actually starts by finding the LU factorization of A, then uses backward substitution to solve Ux = z, forward substitution to solve Ly = z. This is the way the 15c works as documented in section 4 of the Advanced Functions Handbook. (link.) Obviously, once the LU factorization is found, subsequently solving new systems LUx = y is much faster. However, as best I can tell, the 34s exposes no function or variant of LINEQS to accept a matrix already in LUfactored form, although this functionality seems to be implicit in the ROM. In other words, solving multiple systems Ax=y (with different y's) always starts by implicitly redoing the LU work. Oh, well. I suppose exposing one more function, or variant of extant LINEQS, would use exiguous ROM. I will appreciate your comments! SN PS: The reported behavior appears identical in my calculator with ROM 3658, and the emulator with ROM 3883. [The manual's explanation (link to manual, see p. 94) of the interpretation of the latter descriptor is not particularly clear, but it seems that, if A is an n×n matrix (with, presumably, n<10 in order for all that follows to make sense), then the descriptor is an integer whose digits, read lefttoright as usual, should be a permutation of the numbers 1, 2, …, n, and the ith leftmost digit d_i of the descriptor indicates that the ith pivot implicitly returned in A_ii (i.e., U_ii) came from the entry A_ji where j = d_i. In other words, whatever row exchanges necessary to carry out LU ended up sending row j=d_i to row i.] 

11102019, 09:50 PM
(This post was last modified: 11132019 12:42 AM by Paul Dale.)
Post: #2




RE: Interpreting output of WP34s M.LU (likely bug)
I think you'll find the pivots are zero based not one based, they are also not necessarily a permutation. An unpivoted matrix would then end up with pivots 012 > 12. Your 112 is saying to use the second row first and then the rest of the updated matrix in order (no more pivoting).
You are correct about the forward and back substitution process to solve systems of equations. Unlike the 15C, the 34S has no space to remember that a matrix is in LU form (the 15C stored pivots in the matrix descriptor I believe). Pauli 

11122019, 11:05 PM
Post: #3




RE: Interpreting output of WP34s M.LU (likely bug)
(11102019 09:50 PM)Paul Dale Wrote: I think you'll find the pivots are zero based not one based, they are also not necessarily a permutation. An unpivoted matrix would then end up with pivots 012 > 12. You 112 is saying to use the second row first and then the rest of the updated matrix in order (no more pivoting). Thanks, Pauli. This clarifies the output of LINEQS, which I was misinterpreting as a bug. I read this article that explains that 3 bits of the "sign nibble" in diagonal entries M_ii of a matrix M in LU form are used to store rowreordering information in the 15c, but that article does not explain how to interpret the bits either. (In any event, these 3 bits of the sign nibble are hidden to the user of the 15c; they can only be accessed using synthetic tricks.) SN 

« Next Oldest  Next Newest »

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