1
$\begingroup$

I have to compute the QR decomposition of a matrix A repeatedly, each time with ONLY diagonal elements changing. Is there an efficient way to accomplish this without repeatedly computing the full decomposition?

The issue here is that this whole process needs to be calculated repeatedly for a couple of thousand of times with size of A to be of the order of 512x512. Every time, A changes only in its diagonal elements.

The Numerical Recipes (by Press et al.) provides a way to do it if A changes as follows

A -> A + s x t

where s and t are vectors of dimension n with A as the n x n matrix. However, in my case the change in the matrix is

A -> A + P

where P is a diagonal matrix.

Madhurjya

$\endgroup$
4
  • 1
    $\begingroup$ Is it really the QR decomposition that needs an update? Or its application to some linear system solving? For the latter you can consider the Woodbury formula, which attains an easy form for just a diagonal matrix. $\endgroup$
    – davidhigh
    Jul 28, 2022 at 6:45
  • 1
    $\begingroup$ @davidhigh I don't think you can get any computational gain with the Woodbury formula either, if $P$ is a full diagonal (without a large amount of zeros). $\endgroup$ Jul 28, 2022 at 12:15
  • $\begingroup$ @FredericoPoloni: right, you probably get some insight, but it'll remain $O(N^3)$ in general. Another scrnario where it could be helpful, besides having many zeros on the diagonals, is if it is possible to order the diagonals such that there are only a few changes between two adjacent diagonals. $\endgroup$
    – davidhigh
    Jul 28, 2022 at 14:10
  • $\begingroup$ Is $P$ perhaps a multiple of $I$? In that case, you could use a Hessenberg or Schur factorization. $\endgroup$ Aug 8, 2022 at 15:15

1 Answer 1

7
$\begingroup$

Variants of this question get asked regularly on [scicomp.se], but unfortunately the answer is always no: one cannot update easily any matrix factorizations after a full-rank diagonal update. Some pointers to other negative answers are here.

There are only two cases in which solutions exist, as far as I know:

  • if $P$ has very few nonzeros, one can use the low-rank update procedure that you have already found.
  • if $P$ is very small, in norm, with respect to $A$, or viceversa, one can use a perturbative approach or apply an iterative method (e.g. Richardson iteration, GMRES) using it as a preconditioner.
$\endgroup$
1
  • 3
    $\begingroup$ The key piece from this answer being that a diagonal matrix is not a rank-1 matrix! $\endgroup$ Jul 28, 2022 at 15:07

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.