6.3 Additional Considerations

The algorithms presented in Section 6.1 and Section 6.2 are based on the work of Bennett [1]. The nomenclature is similar to that of Gill et al. [7]. These citations describe procedures for updating the factors of an LDU decomposition.

The procedure described by Bennett [1] is more general than the algorithms described in this section in that it applies to rank m changes to A. However, decomposing a rank m change into m rank one changes and applying the current algorithms has the same complexity as Bennett’s process and saves a little array space. Gill et al. [7] state that Bennett’s algorithm is theoretically unstable unless L = U^T and y = z. In practice, Bennett’s algorithm has proven to be stable for many physical problems with reasonable values of $\alpha$, y, and z. The algorithm rarely exhibits instability when it is applied to diagonally dominant matrices where pivoting is not required. Gill et al. [7] describe alternate algorithms for situations where stability problems arise.

Hager [12] provides a good overview of approaches to the problem of updating the inverse of a matrix and describes practical areas in which the problem arises. Chan and Brandwajn [2] examine applications in network analysis.