Stability of Methods for Matrix Inversion

Inversion of a triangular matrix can be accomplished in several ways. The standard methods are characterised by the loop ordering, whether matrix-vector multiplication, solution of a triangular system, or a rank-1 update is done inside the outer loop, and whether the method is blocked or unblocked. The numerical stability properties of these methods are investigated. It is shown that unblocked methods satisfy pleasing bounds on the left or right residual. However, for one of the block methods it is necessary to convert a matrix multiplication into the solution of a multiple right-hand side triangular system in order to have an acceptable residual bound. The inversion of a full matrix given a factorization PA = LU is also considered, including the special cases of symmetric inde nite and symmetric positive de nite matrices. Three popular methods are shown to possess satisfactory residual bounds, subject to a certain requirement on the implementation, and an attractive new method is described. This work was motivated by the question of what inversion methods should be used in LAPACK.