How to do LU factorization efficiently based on the factorized result added with a low-rank matrix?

Question

Suppose a square $n\times n$, dense matrix $A^{\text{old}}$ has been factorized into $L^{\text{old}}$ and $U^{\text{old}}$ components by performing a LU decomposition $A^{\text{old}} = L^{\text{old}}U^{\text{old}}$. Now let $A^{\text{new}}=A^{\text{old}} + PQ$, where $P$ is $n\times k$ and Q is $k\times n$ dense matrices ($k << n$). That is, $A^{\text{old}}$ is added with a low-rank matrix $PQ$.

Is there any efficient way to compute the LU factorization of $A^{\text{new}}$? Normally, a full re-factorization of $A^{\text{new}}$ is $O(n^3)$ complexity, and I am seeking a possible $O(n^2)$ algorithm with the reuse of $L^{\text{old}}$ and $U^{\text{old}}$ that have been previously computed.

I notice that Woodbury matrix identity could do similar things. But Woodbury just obtains the inverse implicitly, but could not obtain the factorized matrices $L^{\text{new}}$ and $U^{\text{new}}$.

Answer 1

Stange et al. (2007) present Bennett's (1965) algorithm [note: I have not directly seen Bennett's article], which concerns the additive rank-one modification $$ A^+ = A + u v^T. $$ The algorithm updates the factorization $A=LU$ into $A^+ = L^+U^+$ in $4nm$ operations, when $A$ has dimensions $m \times n$. The algorithm is quite simple and is presented in pseudocode.

Stange et al. also say that Bennett's algorithm "can easily be extended for higher rank modifications". Furthermore they present other algorithms, some of which involve pivoting (Bennett's algorithm does not).

Bennett, John M., Triangular factors of modified matrices, Numer. Math. 7, 217-221 (1965). ZBL0132.36204.

Stange, Peter; Griewank, Andreas; Bollhöfer, Matthias, On the efficient update of rectangular LU-factorizations subject to low rank modifications, ETNA, Electron. Trans. Numer. Anal. 26, 161-177 (2007). ZBL1171.15309.