2

I am a math major and I am taking a class on numerical linear algebra. It has been a little while since my numerical analysis class where we had a couple of algorithms for this problem, the most prominent was the LU-algorithm I think (we called it like this, because it used the LU decomposition).

Now I my NLA class we have a lot! of these algorithms: arnoldi-iteration, lanczos-algorithm, CG method, GIMRES, MINRES, unsymetric lanczos,... (I actually thought we were done with this topic in my numerical analysis class, I didn't expect there to be so much more)

Do all of the algorithms have their purposes? Why is the LU-algorithm not enough?

Sen90
  • 351
  • I'm not familiar with all of these algorithms, but it seems to me that not all of them handle the case of solving a system of equations – Stephen Donovan Jun 28 '22 at 21:40
  • 1
    Various algorithms exploit various types of structure that your matrix might have. For small and medium sized matrices, it’s hard to beat a direct method (most often Gaussian elimination a.k.a LU decomposition). For large matrices, the $O(n^3)$ cost of LU factorization becomes prohibitive, so we resort to iterative methods (especially if $A$ is sparse). CG is an excellent iterative method but it assumes that your matrix is symmetric positive definite. If your matrix is symmetric but not positive definite, MINRES can be applied. If your matrix is not even symmetric, then GMRES can be applied. – littleO Jun 29 '22 at 01:50

1 Answers1

4

The LU factorization can be extremely slow or intractable for very large matrices, especially large sparse matrices. The other methods you mention are all iterative methods, which are applicable to large sparse systems of equations, which cannot be solved directly in any reasonable amount of computational time.

Sparse means that a lot (i.e., a vast majority) of the entries in the matrix are zero. The zero entries do not need to be stored or used in computations, which drastically decreases memory requirements and accelerates computations. In sparse settings, you normally cannot even afford to store the whole dense matrix in memory, due to its sheer size, so the LU factorization (which is not sparse) is not tractable.

The field of iterative methods for solving linear systems is huge, simply because the method should be adapted to the type of linear system you are solving. For solving $Ax=b$ where $A$ is symmetric and positive definite, the conjugate gradient method (with preconditioning) is one of the best iterative methods. When $A$ is not symmetric, the GMRES (not GIMRES) method is very good. The Arnoldi iterations are used for sparse eigenvector solvers (as is the Lanczos algorithm). There are many other methods as well (e.g., Jacobi iteration).

Simply put, solving linear systems, especially very large ones, is extremely hard to do efficiently, and it is extremely important to use a method that is adapted to the properties of the particular linear system you are solving. This is why there are so many different methods.

Jeff
  • 5,617