If the LU decomposition of the matrix $\mathbf{A}$ exists and the factorization of a related matrix
| $$\mathbf{A^{\prime}=A+\Delta A}$$ | (64) |
is needed, it is sometimes advantageous to compute the factorization of $\mathbf{A^{\prime}}$ by modifying the factors of $\mathbf{A}$ rather than explicitly decomposing $\mathbf{A^{\prime}}$. Implementations of this factor update operation should have the following properties:
Arithmetic is minimized,
Numerical stability is maintained, and
Sparsity is preserved.
The current discussion outlines procedures for updating the factors of A following a rank one modification. A rank one modification of A is defined as
| $$\mathbf{A^{\prime}=A}+\alpha\mathbf{y{z}^{T}}$$ | (65) |
where $\alpha$ is a scalar and the vectors $\mathbf{y}$ and $\mathbf{z^T}$ are dimensionally correct. The terminology comes from the observation that the product $\alpha\mathbf{z^T}$ is a matrix whose rank is one.
Computationally, a rank one factor update to adense matrix is an $O(n^2)$ operation. Recall that decomposing a matrix from scratch is $O(n^3)$.