Sometimes, it is required to solve the following problem: having matrix A which we have already inverted (and got A ^-1). Then, we have changed some elements of A, and we need to invert the matrix modified as follows.

Of course, this problem can generally be solved by inverting the modified matrix. However, there is a more effective way which takes into account the fact that we already have A ^-1 and the input matrix was modified slightly.

Inverse matrix update algorithm

The Sherman-Morrison formula serves as the basis of an algorithm:

Here A is a square NxN matrix whose inverse matrix we know, u and v are the columns of height N defining the matrix modification, (u_i v_j  is added to a_i,j ). We can see that the inverse matrix update with this formula requires N ² operations with real numbers, which is N times better than the inversion by using a general algorithm.

Depending on u and v, there are different types of matrix A modifications and matrix A ^-1 update with different time complexity. Let's consider the main cases:

• If only u_i  and v_j  are non-zero, u_i v_j  is added to a_i,j .
• If u_i  = 1 and other components of the vector equal 0, vector v is added to the row number i in matrix A.
• If v_j  = 1 and other components of the vector equal 0, vector u is added to the column number j in matrix A.
• If u and v are arbitrary vectors, row v (column u) is added to different rows (columns) with different multipliers.

These cases have a different computational complexity. The fastest is an inverse matrix update where only one element of the source matrix is changed. We'll take it as a unit. The inverse matrix update by row or column is only 2 times slower (thus, if three or more elements of one row or column were modified, it would better to use this algorithm than the previous one). The inverse matrix update with arbitrary vectors u and v is three times slower than the simple update.

Note #1
The algorithm stability is in question. At least, one step is stable enough if A and B are well-conditioned.

Program description

The module contains several subroutines which update A ^-1 both in the general case and in the special cases described above.

The RMatrixInvUpdateSimple subroutine updates A ^-1 when adding UpdVal to the matrix element located in row UpdRow and column UpdColumn.

The subroutines RMatrixInvUpdateRow and RMatrixInvUpdateColumn update the matrix when adding a vector to the matrix row or column.

The subroutine RMatrixInvUpdateUV updates an inverse matrix in the general case which is defined by vectors U and V.

Report a bug

C#

C# 1.0 source.
inverseupdate.csharp.zip - Update of the inverse matrix by the Sherman-Morrison formula

C++

C++ source.
inverseupdate.cpp.zip - Update of the inverse matrix by the Sherman-Morrison formula
ablas.zip - optimized basic linear algebra subroutines with SSE2 support (for C++ sources only)

C++, multiple precision arithmetic

C++ source. MPFR/GMP is used.
GMP source is available from gmplib.org. MPFR source is available from www.mpfr.org.
inverseupdate.mpfr.zip - Update of the inverse matrix by the Sherman-Morrison formula
mpfr.zip - precompiled Win32 MPFR/GMP binaries

Delphi

Delphi source.
Can be compiled under FPC (in Delphi compatibility mode).
inverseupdate.delphi.zip - Update of the inverse matrix by the Sherman-Morrison formula

Visual Basic 6

Visual Basic 6 source.
inverseupdate.vb6.zip - Update of the inverse matrix by the Sherman-Morrison formula

Zonnon ^beta

Zonnon source.
Zonnon is an experimental language developed at ETH Zurich.
See www.zonnon.ethz.ch for more information.
inverseupdate.zonnon.zip - Update of the inverse matrix by the Sherman-Morrison formula