6 Factor Update

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)$.

Factor Update Topics