1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ You might want to ask over at the Computational Science area as well. $\endgroup$
    – Tom Dickens
    Commented Aug 17, 2013 at 16:06

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .