3
$\begingroup$

In an application I have to solve a series of positive definite linear systems of the form $A^TA x = A^Tb$ (i.e. normal equations). The next system is obtained from the previous one by adding and/or removing a small number of columns to $A$ (usually one or two). The vector $b$ stays the same throughout. It seems clear that some kind of up-/downdating strategy should be applied, however, my questions are:

What kind of up-/downdating shall I choose (QR, Cholesky, Matrix-Inversion-Lemma,others?,...)?

On what conditions and requirements shall I make my choice (high precision needed, ill-conditioned matrices, well-conditioned ones, speed,...)?

P.S.: You may assume that $A$ and $A^T$ can be applied fast.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ So you have $\mathbf A$ itself available and not just $\mathbf A^\top \mathbf A$? Updating a QR decomposition seems to be a good choice if the condition number of $\mathbf A$ is reasonable (there are also updating algorithms for SVD, but I've found them a bit unwieldy). As a matter of fact, the Cholesky and QR updating methods are essentially equivalent... $\endgroup$ – J. M. Jan 13 '12 at 10:40
  • 1
    $\begingroup$ I should make the reminder, however, that downdating can be an unstable process. You'd want to check the condition of your newly-derived system after performing the downdate. $\endgroup$ – J. M. Jan 13 '12 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.