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