5
$\begingroup$

This is such a basic topic but there are so many different methods proposed for solving a linear system of equations. I recently found a very good source but couldn't really make sense of all the stuff it contains.

If I had to pick only 5 methods that I should understand thoroughly for solving big systems of linear equations which would they be? And what would be the most important reason for each choice?

I.e. direct methods?gauss-siedel?conjugate gradient?...

Thanks in advance for the help.

$\endgroup$
5
$\begingroup$

While it is easy to reach a suboptimal solution for your problem it is usually much harder (and problem-dependent) to come up with an optimal/robust strategy. In this sense your question is quite broad and to give good advice it is crucial to know about the problem you want to solve.

In the following I will assume you speak of sparse systems and you have the assembled matrix to start with. For large dense systems, I don't really know if you have any choice if you cannot make very strong assumptions on the nature of your problem.

For sparse systems it pretty much depends on the size, sparsity and structure of your system. For banded systems or moderate sizes up to a few ten thousand unknowns a sparse-direct solver will often be hard to beat. For much larger systems Krylov-subspace solvers are a standard choice. Here you may categorize into symmetric positive definite (-> CG) or just symmetric (MINRES etc.) or not symmetric at all. If you cannot assume symmetry, then GMRES is a widely-used solver. However, since its memory requirements grow with each iteration, you have to restart it after a couple of iterations (this is usually a parameter which you can tune). While this theoretically brings you back to square one, in practice it works quite well most of the time. In terms of memory-requirements another popular choice is BiCGStab, which is often reported to cause difficulties if not preconditioned well. Speaking of nonsymmetric systems it is not easy to say which method is best. In fact there are examples in the literature where certain methods clearly outperform others.

There are many more methods than SparseLU, CG, MINRES, GMRES and BiCGStab, but if you can at least decide whether you can use CG or MINRES on your problem or not, you are probably better off than many others.

For iterative methods it is also important to choose a suitable preconditioner for your problem. There are some choices (diagonal, incomplete LU/Cholesky, AMG variants, etc.) which are implemented or interfaced in almost every toolbox, but preconditioning is most effective when it is done in a meaningful (or physics-aware) way. This is clearly nothing which is easy to answer in general.

The bottom line is: if you cannot spend much time to read about good solvers/preconditioners for your problem, you have some generic choices to choose from. Many people just try out a couple of solvers built into the package they use and stick with the choice that gives the best results. If you follow this trial and error strategy, you should be prepared to wait unnecessarily long for your solutions to be computed. There are many excellent questions and answers on this site which provide you with further reading in case you decide that learning about optimal strategies for your specific problem will pay off after some time.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Just to let you know I didn't say I only had 5 mins ;P... Can I ask you to provide a brief dichotomy of how these algorithms are different in theoretical terms? $\endgroup$ – Matteo Apr 10 '14 at 17:12
  • $\begingroup$ Oh, I see... you're right, I accidentally read '5 minutes' instead of '5 methods'. I'll edit my answer and try to give more detail on the theoretical stuff when I find some time. Roughly speaking there are a couple of standard methods which can be chosen according to the structure of your problems. For some there is theory, while for others there is not much more than advice from practical experience. The former should be easy to find by fast-forwarding through standard textbooks (like the one you found), the latter is largely problem-dependent and scattered across the literature. $\endgroup$ – Christian Waluga Apr 10 '14 at 17:42
  • $\begingroup$ Thanks a lot, that would be greatly appreciated. It's very difficult when you see the arguments for the first time to get a feeling of what is important and why. I'll put a bounty on the question as soon as i can so you can be rewarded for the time you spent on this!Thanks again $\endgroup$ – Matteo Apr 10 '14 at 17:57
3
$\begingroup$

Direct vs. iterative is certainly one of the key questions in linear solvers for sparse matrices as you have already observed. There are many misconceptions and lots of misinformation on this topic. So I encourage you to approach the issue from this point of view rather than looking for "5 methods."

Here is a nice introduction from one of the major contributors to direct methods:

Matrix methods, Duff I.S.

You refer to Professor Saad's classic book on iterative methods for sparse systems. In the course he teaches at U. of Minnesota, he spends about equal time on direct and iterative methods. His notes are a gold mine of information.

Sparse Matrix Computations

$\endgroup$
0
$\begingroup$

I did some research on the topic a few years ago and my conclusion was that iterative methods have a more promising future if the technology keeps drifting towards decentralized computation (as it is doing). Apart from direct and iterative methods, there has been some advances in solving very large matrices with Monte Carlo methods, but in my opinion the best bet is to go to Hadoop implementations. Below is a link I found to a github project:

https://github.com/JingenXiang/MatrixInversion

And here you can find more details on how it is done:

https://cs.uwaterloo.ca/~ashraf/pubs/hpdc14matrix.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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