11-10-2019, 05:30 PM

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

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

corresponding to the LU factorization

By multiplying LU, we see that

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)

However, M.LU returns

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.]

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 ]

Code:

A =

[ 3 8 14 ]

[ 1/3 -2/3 -2/3 ]

[ 2/3 -1 3 ]

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

Code:

112

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.]