# QR decomposition with only diagonal elements changing

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.

• 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. Jul 28, 2022 at 6:45
• @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). Jul 28, 2022 at 12:15
• @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. Jul 28, 2022 at 14:10
• Is $P$ perhaps a multiple of $I$? In that case, you could use a Hessenberg or Schur factorization. Aug 8, 2022 at 15:15

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