4
$\begingroup$

This question was original posted on SO but it was suggested that I post it here.

I'm working on a program in which I have a banded matrix M and a vector b, and I want to maintain an approximate solution vector x such that Mxb. Is there a speedy algorithm or way of modeling this so that I can change individual elements of M and correspondingly update x, without having to do a full matrix inversion?

One thing I'm considering is maintaining an approximate inverse of M, using the Sherman Morrison Algorithm in combination with a fast approximate matrix multiplication algorithm like this.

$\endgroup$
2
$\begingroup$

Apologies for what will probably be a comment-answer hybrid (and a comment probably too long to fit in the comment box).

One thing you say in your question is that you want an approximate solution vector. Have you considered iterative methods? There, the approximate inverse of $M$ could be used as a preconditioner in concert with some iterative method (GMRES, BiCGStab, etc.) to maintain approximate solution vectors, and the approximate solution for one linear system could then be used as an initial guess for the solution of a perturbed linear system.

To update the preconditioner in response to single-element (or low-rank) perturbations, you could use Sherman-Morrison(-Woodbury). Depending on the perturbation, the approximate inverse may still be an effective preconditioner even without updating.

I don't know how fast approximate matrix multiplication might degrade the solution of an iterative linear system; I would guess that it would be more forgiving in forming the preconditioner, since that can be approximate. After forming the preconditioner, I would stick to standard matrix-vector products for the solver iterations (for GMRES iterations, or whatever iterative method you consider using).

Of course, this entire discussion might be moot, depending on the size of $M$. If it's sufficiently small, it might be worth just solving every time; I assume it's relatively large, or we wouldn't be having this discussion.

$\endgroup$
  • $\begingroup$ Yes, M is very big. Could you by chance link to some descriptions of these iterative methods? I'm a scientific computation newbie. $\endgroup$ – Chris Conlon Feb 23 '14 at 21:51
  • $\begingroup$ Saad's textbook, Iterative Methods for Sparse Linear Systems is available online. A quicker introduction to some of these methods is The Idea Behind Krylov Methods. $\endgroup$ – Geoff Oxberry Feb 23 '14 at 21:58
  • $\begingroup$ These methods works only for sparse matrices? $\endgroup$ – mrgloom Sep 29 '14 at 9:24
  • $\begingroup$ @mrgloom: Iterative methods can also work for dense matrices, but direct methods are typically used, except in cases where you have a good preconditioner for iterative methods, or there is some exploitable special structure. $\endgroup$ – Geoff Oxberry Sep 29 '14 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.