6 Factor Update

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 zT are dimensionally correct. The terminology comes from the observation that the product α\alphazT is a matrix whose rank is one.

Computationally, a rank one factor update to a dense matrix is an O( n2 ) operation. Recall that decomposing a matrix from scratch is O( n3 ).

Factor Update Topics