MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the best know algorithm for solving a large sparse system of linear equations? The system I'm working on is not symmetric, not positive definite and integer. The only benefit is being sparse. I also need to point out that the matrix is not square. The dimension is $m\times n$ and it is not generally either underestimate or overestimate.

share|cite|improve this question
This question is under defined: the "best method" depends on the sparsity structure... – Igor Rivin Jul 12 '12 at 8:11
I suggest asking on But you'll want to clarify the question. – David Ketcheson Jul 12 '12 at 10:14
In general, so-called "black-box" linear algebra techniques offer very good theoretical and practical performance for sparse or structured matrix operations. The basic idea is to treat matrix multiplication as an oracle: in the sparse or structured case, this will have subquadratic complexity and can be leveraged to accelerate more complex operations. – Steve Huntsman Jul 12 '12 at 14:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.