Possible ways to calculate X = A - inv(B) * Y * inv(B) and X = Y + A' * inv(B) * A

Question

I have two problems. I have to calculate two equations:

X = A - inv(B) * Y * inv(B)

and

X = Y + A' * inv(B) * A

where, A, B and Y are known p*p matrices (p can be small or large, depends the situation). Matrices are quite dense, without any structure (except B being non-singular of course).

Is it possible to solve X in those equations without inverting the matrix B? I have to calculate these equations n times, n being hundreds or thousands, and all the matrices change over time.

Thank you very much.

Answer 1

Memo-ize inv(B), i.e. only invert B when it changes, and keep the inverse around.

If changes to B are small, possibly you could use a delta-approximation.

Answer 2

If you can express your updates to your matrix B in the following terms:

Bnew = B + u*s*v

then you can express an update to inv(B) explicitly using the Sherman-Morrison-Woodbury formula:

inv(B + u*s*v) = inv(B) - inv(B)*u*inv(s + v*inv(B)*u)*v*inv(B)

If u and v are vectors (column and row, respectively) and s is scalar, then this expression simplifies:

inv(B + u*s*v) = inv(B) - inv(B)*u*v*inv(B)/(s + v*inv(B)*u)

You would only have to calculate inv(B) once and then update it when it changes with no additional inversions.

It may be preferable not to calculate the full inverse, just simple "matrix divisions" on y and (ynew - y) or a and (anew - a) depending on the size of "n" with respect to "p" in your problem.