Interpreting output of WP34s M.LU (likely bug)

[supernumero]

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:


A =
[ 1 2  4 ]
[ 3 8 14 ]
[ 2 6 13 ]

stored in R10–R18, with descriptor 10.03 in X. Upon calling M.LU, the matrix A is modified in situ to:

Code:


A =
[   3    8   14 ]
[ 1/3 -2/3 -2/3 ]
[ 2/3   -1    3 ]

corresponding to the LU factorization

Code:


L =
[   1  0 0 ]
[ 1/3  1 0 ]
[ 2/3 -1 1 ]

U =
[ 3    8   14 ]
[ 0 -2/3 -2/3 ]
[ 0    0    3 ]

By multiplying LU, we see that

Code:


LU = B =
[ 3 8 14 ]
[ 1 2  4 ]
[ 2 6 13 ]

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:


213

However, M.LU returns

Code:


112

I have no idea what the latter number means, and I can only think this is a bug in M.LU. As I mentioned, I worked several examples out, and not once did I get the expected descriptor of row exchanges in X. I get a descriptors with repeated digits, or even descriptors with fewer than n digits!

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 LU-factored 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 re-doing 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 left-to-right as usual, should be a permutation of the numbers 1, 2, …, n, and the i-th leftmost digit d_i of the descriptor indicates that the i-th 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.]

[Paul Dale]

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

[supernumero]

(11-10-2019 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).

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

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 row-reordering 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