The inhomogeneous matrix equation $\mathbf{A} x = b$ can be solve in many ways, but in this particular case, I am looking for a solution to this problem on a set of constraints.

The matrix $A$ is invertible, and sparse, however the matrix is so huge that even a approximative Pan-Reif inversion is off the table. The matrix $A$ can be brought to banded form, with a somewhat limited band-width.

Normally I would solve this for instance with a conjugated gradient method, and it works very well. But it scales like $O(Nm)$, and I need something even faster. The case is that I only need a subset of values from the solution $x$ and the rest of the values can even be incorrect as long as the required values from $x$ is correct.

I just need a pointer in what direction to look for a solution (iterative or direct) or alternative a proof that no such method exist

  • $\begingroup$ You might want to ask over at the Computational Science area as well. $\endgroup$ Commented Aug 17, 2013 at 16:06

1 Answer 1


Row action methods might be just the ticket. If so, there is a classic SIAM Review by Yair Censor from Oct 81. These methods let you work one row at a time or with blocks of rows.

  • $\begingroup$ This is a great paper -- the details are: "Row-action methods for huge and sparse systems and their applications" SIAM Rev., 23(4):444--466 $\endgroup$
    – J.J. Green
    Commented Aug 17, 2013 at 17:32
  • $\begingroup$ Row action methods are incredibly easy to code. And I have used them in the past to do "data assimilation", technically "update least squares". This allows you to update your solution using only the new equations (data). I learned about update least squares from the classic books.google.com/books/about/… by Lawson and Hanson. $\endgroup$
    – JohnS
    Commented Aug 17, 2013 at 18:35
  • $\begingroup$ I have started going through the list of the review of Censor. There might be one of the methods, but as far as I can see they will all scale like $O(Nm)$. I will have through go the rest of the methods. $\endgroup$
    – Smidstrup
    Commented Aug 18, 2013 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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