2
$\begingroup$

I have got an input series of matrices

$A_1, A_2, A_3, \dots $

and the difference between $A_i$ and $A_{i+1}$ is the replacement of one single column. Before i get to know $A_{i+1}$, I have to compute $A_i^{-1} b$ for some fixed vector $b$, so I also have a series of vectors

$A_1^{-1}b, A_2^{-1}b, A_3^{-1}b, \dots $

to compute. For your interest, this appears in implementations of the simplex method, but I prefer to approach with the point of view of numerical linear algebra. Questions:

  1. Where can I find a reference on updating the QR decomposition after replacing one column?
  2. Since I am only interested in the QR decomposition in order to solve a sequence of linear problems, can this be exploited in the algorithms,too?

I use the QR decomposition only because this is a standard method - in the case that you have a better recommendation for the above setting, feel free to provide your advice.

$\endgroup$

1 Answer 1

8
$\begingroup$

There is an extensive literature on numerical aspects of the implementation of the simplex method including methods for updating the factorization of the basis as well as techniques that maintain the inverse of the basis in product form. Replacing a column of the basis matrix is a "rank-one update" since it can be written in terms of adding a matrix to the basis that has only one nonzero column and is thus of rank one.

The QR factorization is not typically used in implementations of the simplex method, since it is very slow in comparison with alternative approaches. In practice an initial LU factorization of the basis is typically combined with rank one updates to the factorization for each iteration. Because too many rank one updates can lead to numerical problems, the basis is typically refactored every so often (e.g. once every 50 iterations.)

There are efficient algorithms for rank one updates to the QR factorization. A classic reference is:

J. W. Daniel, W. B. Gragg, L. Kaufman, and G. Stewart, Reorthogonalization and Stable Algorithms for Updating the Gram-Schmidt QR Factorization. Mathematics of Computation 30:

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.