Woodbury Block Update Solve

Worked Example

Let A = 2I_3, U = [[1, 0], [0, 1], [1, 1]], b = [1, 2, -1]^T. Let the update weight be z = 1. We want to solve the system (A + zUU^T)x = b. The Woodbury identity tells us that the inverse of the updated matrix is A⁻¹ - z A⁻¹ U C⁻¹ U^T A⁻¹, where C = (I + z U^T A⁻¹ U) is the smaller 2x2 core matrix.

A = [[2, 0, 0], [0, 2, 0], [0, 0, 2]]
A⁻¹ = [[0.5, 0, 0], [0, 0.5, 0], [0, 0, 0.5]]
U = [[1, 0], [0, 1], [1, 1]]
b = [1, 2, -1]^T
z = 1

U^T A⁻¹ U = 0.5 * [[2, 1], [1, 2]] = [[1, 0.5], [0.5, 1]]
C = I + z U^T A⁻¹ U = [[2, 0.5], [0.5, 2]]
det(C) = 2*2 - 0.5*0.5 = 3.75

C⁻¹ = (1/3.75) * [[2, -0.5], [-0.5, 2]]
    = [[0.5333..., -0.1333...], [-0.1333..., 0.5333...]]

A⁻¹ b = [0.5, 1, -0.5]^T
U^T (A⁻¹ b) = [0, 0.5]^T
C⁻¹ U^T (A⁻¹ b) = [-0.0666..., 0.2666...]^T
U C⁻¹ U^T (A⁻¹ b) = [-0.0666..., 0.2666..., 0.2]^T
z A⁻¹ U C⁻¹ U^T A⁻¹ b = [-0.0333..., 0.1333..., 0.1]^T

x = A⁻¹ b - z A⁻¹ U C⁻¹ U^T A⁻¹ b
  = [0.5 - (-0.0333...), 1 - 0.1333..., -0.5 - 0.1]^T
  = [0.5333..., 0.8666..., -0.6]^T

Experiment

Using the module Woodbury Block Update Solve, we can adjust the update weight z and observe the changes in the core determinant and solution vector.

1. Set the native select control "Update weight" to 1.
2. Observe the invertible status and the small core determinant of 3.75.
3. Verify the 3D solution vector output is approximately [0.5333, 0.8666, -0.6].
4. Set the update weight to -2 and observe that the core determinant becomes 0, making the updated matrix singular and the solution unavailable.

Limitations

The Woodbury method requires the base matrix A to be invertible. If the small core determinant det(C) becomes exactly zero (e.g., when z = -2), the Woodbury formula cannot be evaluated because the updated matrix is singular. The module checks for this exact singularity but may be subject to floating point representation limits in more complex numerical cases.

References

The Sherman-Morrison-Woodbury formula is a classic identity for computing the inverse of a matrix after a low-rank update, widely used in numerical linear algebra to avoid full re-inversion. See What Is the Sherman-Morrison-Woodbury Formula? (Nicholas J. Higham) for an overview.