This question borders between a programming and math question (more math). I have a little matrix knowledge but this is past my ability, so any help is very much appreciated.

## Question

I have a very large sparse matrix (say one million rows square). I'd like to solve this for many different sets of constant values (to clarify, by constant values, I mean the 1xn matrix 'b' in Ax = b). Performance is absolutely crucial - so it would make sense to do whatever simplification I can in advance of introducing each set of constants.

## Goal

I'd like to get the time complexity for solving each constant set down to O(n)... I may be dreaming however.

## Other Info

- The matrix really is a million (maybe even 100 million) rows
- It's
*very*sparse - It has a bandwidth ranging between 2 and as much as a few hundred
- Even for larger bandwidths, each row has max. 7 or 8 non zero entries
- It takes an (extremely rough) diagonal form
- Each matrix 'b' in Ax = b is actually very sparse itself
- Due to the nature of the problem, a solution should always be available
- All nonzero values are real, floating point numbers. They can be negative however.

3more comments