Language Reference

CALL RDODT (def, rup, bup, sup, r, z <, b> <, y> <, ssq> ) ;

CALL RUPDT (rup, bup, sup, r, z <, b> <, y> <, ssq> ) ;

This subroutine is supported by the IML procedure and the iml action.

If is the QR decomposition of the matrix , the RUPDT subroutine enables you to efficiently recompute the matrix when a new row is added to A. This is called an update. Similarly, the RDODT subroutine enables you to efficiently recompute the matrix when an existing row is deleted from A. This is called a downdate. You can also use the RDODT and RUPDT subroutines to downdate and update Cholesky decompositions.

The RDODT and RUPDT subroutines return the values:

The input arguments to the RDODT and RUPDT subroutines are as follows:

The upper triangular matrix of the QR decomposition of an matrix ,

is recomputed efficiently in two cases:

Computing the whole QR decomposition of matrix by Householder transformations requires floating-point operations, whereas updating or downdating the QR decomposition (by Givens rotations) of one row vector z requires only floating-point operations.

If the QR decomposition is used to solve the full-rank linear least squares problem

by solving the nonsingular upper triangular system

then the RUPDT and RDODT subroutines can be used to update or downdate the p-transformed right-hand sides and the residual sum-of-squares p vector ssq provided that for each n vector z added to or deleted from there is also a p vector y added to or deleted from the right-hand-side matrix .

If the arguments z and y of the subroutines RUPDT and RDODT contain row vectors for which (and , and eventually ssq) is to be updated or downdated, the process is performed stepwise by processing the rows z (and y), , in the order in which they are stored.

The QR decomposition of an matrix , , rank,

corresponds to the Cholesky factorization

of the positive definite crossproduct matrix . In the case where and rank, the upper triangular matrix computed by the QR decomposition (with positive diagonal elements) is the same as the one computed by Cholesky factorization except for numerical error,

Adding a row vector z to matrix corresponds to the rank-1 modification of the crossproduct matrix

and the matrix contains all rows of with the row z added.

Deleting a row vector z from matrix corresponds to the rank-1 modification

and the matrix contains all rows of with the row z deleted. Thus, you can also use the subroutines RUPDT and RDODT to update or downdate the Cholesky factor of a positive definite crossproduct matrix of .

The process of downdating an upper triangular matrix (and eventually a residual sum-of-squares vector ssq) is not always successful. First of all, the downdated matrix could be rank-deficient. Even if the downdated matrix is of full rank, the process of downdating can be ill-conditioned and does not work well if the downdated matrix is close (by rounding errors) to a rank-deficient one. In these cases, the downdated matrix is not unique and cannot be computed by subroutine RDODT. If cannot be computed, def returns 2, and the results rup, bup, and sup return missing values.

The downdating of the residual sum-of-squares vector ssq can be a problem, too. In practice, the downdate formula

cannot always be computed because, due to rounding errors, the radicand can be negative. In this case, the result vector sup returns missing values, and def returns 1.

You can use various methods to compute the p columns of the matrix that minimize the p linear least squares problems with an coefficient matrix , , rank, and p right-hand-side vectors b (stored columnwise in the matrix ).

The methods in this section use the following simple example:

 a = { 1 3 ,
       2 2 ,
       3 1 };
 b = { 1, 1, 1};
 m = nrow(a);
 n = ncol(a);
 p = ncol(b);

For the preceding example matrix a, each method obtains the unique LS estimator:

ss = ssq(a * x - b);
print ss x;

To compute the (transposed) matrix , you can use the following technique:

r = repeat(0,n,n);
y = i(m);
qt = repeat(0,n,m);
call rupdt(rup, qtup, sup, r, a, qt, y);
print qtup;