2
$\begingroup$

Linear systems of equations can be either solved with direct methods as the LU-decomposition or with iterative methods. These iterative methods are the Gauss-Seidel method, successive over-relaxation, the Jacobi method, and others.

Iterative methods are computationally less demanding as they only require matrix-vector multiplications. However, using an iterative approach may not work when the chosen method does not converge, or the convergence may be slow.

On the other hand, the direct approach is easy as one gets the exact solution without taking care of convergence and precision.

So, what are the applications for which we prefer iterative methods over direct methods?

Edit: As noted in the comments, iterative methods may be used for large systems of equations where the precision of the solution is not that important. However, I still wonder in which applications do we have these conditions.

$\endgroup$
  • 2
    $\begingroup$ Sometimes your system of equations is too large to be solved by a direct method in a reasonable amount of time. In this case, you can try using an iterative method. You will only get an approximate solution, but often an approximate solution is good enough (and sometimes the approximation is very good). $\endgroup$ – littleO Apr 2 at 21:03
  • $\begingroup$ Thank you for your comment. In which applications do we have these large systems of equations where precission is no that important? $\endgroup$ – The Pheromone Kid Apr 3 at 8:16
  • 1
    $\begingroup$ Large (sparse) systems of equations where precise solutions aren't required come up frequently in numerical optimization. One example off the top of my head is in sequential quadratic programming approaches for nonlinear programming. These techniques require the solution of lots of linear systems. At each step, we really only need to make "enough" improvement--exactly solving the required systems doesn't typically "buy us much". $\endgroup$ – David M. Apr 7 at 19:27
  • 1
    $\begingroup$ A rather sensational example of an iterative vs. direct solver is found in this publication : On solving a Cosmic Ray equation , where you should start reading at page 11. The end result has been 10 minutes instead of 10 hours (: page 18). Where it should be noticed that we're talking about 1996 hardware. $\endgroup$ – Han de Bruijn Apr 9 at 15:50
0
+50
$\begingroup$

Let us consider large sparse systems of linear equations (let say with 1 million unknowns and more).

In general, direct methods need more memory than iterative methods. Iterative methods can be fully parallelized, whereas direct methods only partially. And, with iterative methods you can always have problem with divergence or slow convegence. Iterative methods need good preconditioning to work well, which is however different from problem to problem. If the preconditioning matrix is badly chosen, convergence can be terribly slow. As a rule of thumb, I recommend to use direct methods always, because you do not need to worry about any setting (at least in the framework of finite elements, which I work with).

In the past, the direct method were used for smaller linear systems (smaller means that all allocations needed for the calculation were able to made in RAM, without swapping to a hardrive), larger systems were solved iteratively. However, nowadays the standard RAM memory can be so high, that you can solve linear systems with up to circa 20 million unknowns on a standard PC.

However, it is needed to have a really efficient implementation. You can forget to implement your own invertor, which would beat the best solvers available nowadays. (If of course you do not want to spend many years on it. It is not an easy task.) I personally recommend to use the Pardiso library made by Olaf Schlenk, which is one of the best direct sparse linear solver available. There is even a free version called Intel Pardiso, which can be downloaded from the Intel website (it is actually an older version of the Pardiso library from 2006). It is a sparse Cholesky invertor with METIS reordering algorithm, solves symmetric and non-symmetric sparse matrices. Another good possibility is to use the MUMPS library.

$\endgroup$
0
$\begingroup$

To answer my question, I made a short literature review on recent publications on iterative matrix inversion methods.

Gauss-Seidel-Method (GS)

  • In https://arxiv.org/pdf/1411.2791.pdf, signal detection in wireless communication systems with many antennas and many users is considered. There, solving a linear equation system is required to compute a minimum mean square error solution. The number of variables could be around 2000. This does not seem dramatically high, however, the computation must be very fast.

  • In https://dl.acm.org/citation.cfm?id=2982437, GS is used for the physically-based animation of a soft body, that might be used in video games. The challenge here is the hard requirement on the computation time that must be below a few milliseconds. "Linear iterative methods are preferred in these cases since they provide approximate solutions within a given error tolerance and in a short amount of time." In this publication, the GS is applied in a parallel fashion. Note that parallelization is a powerful advantage of GS over other iterative methods.

  • https://www.researchgate.net/profile/Matthias_Mueller14/publication/274479082_Unified_Particle_Physics_for_Real-Time_Applications/links/5538d62a0cf247b8587d5a6f.pdf treats the simulation of visual effects in real-time applications. In the latter work, objects are modeled as an accumulation of particles. These particles interact with each other through, for example, collisions. To simulate the movement of objects, optimization problems are solved to find the minimum change in kinetic energy. These optimization problems require to solve sets of linear equations. The GS is particularly suitable due to parallelization. Moreover, the GS allows obtaining a trade-off between the accuracy of a simulation and the computation time that is regulated by the number of iterations.

Successive Overrelaxation (SOR)

  • https://arxiv.org/pdf/1507.04588.pdf treats also signal detection in wireless communication systems.

  • In http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.8725&rep=rep1&type=pdf SOR is applied for support vector machine algorithms that are used for classification. The rough idea of support vector machines is to distinguish between two classes of elements based on their features. The goal is to divide the multidimensional feature space by a plane such that elements of one class lie on one side and the other elements on the other side. The computation of this plan requires to solve an optimization problem including matrix inversion. There the number of elements can high if the number of elements is high, for example, more 100000.

    To be continued...

$\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.