If the LU decomposition of the matrix A exists and the factorization of a related matrix
$\mathbf{A^{\prime}=A+\Delta A}$ | (48) |
is needed, it is sometimes advantageous to compute the factorization of A${}^{\prime}$ by modifying the factors of A rather than explicitly decomposing 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}}$ | (49) |
where $\alpha$ is a scalar and the vectors y and z^{T} are dimensionally correct. The terminology comes from the observation that the product $\alpha$z^{T} is a matrix whose rank is one.
Computationally, a rank one factor update to a dense matrix is an O( n^{2} ) operation. Recall that decomposing a matrix from scratch is O( n^{3} ).