Inversion[note]

MATLAB solves Ax=b by using x=A\b,  thus what is behind ‘\’ operator really interests me.

When ‘\’ command is invoked, the utilized algorithm  depends on the structure of input matrix A.

1. When A is sparse and banded, then  banded solver is used. [like Thomas algorithm for tridiagonal matrix].

2. When A is upper or lower triangular matrix, then forward or backward solver will be invoked. And it will take a quick test to check the triangularity at first.

3. When A is symmetric and with positive diagonal elements, MATLAB will use Cholesky factorization algorithm(chol), no matter if the matrix is positive definite or not.

4. When the first three cases do not fit our problem, Gauss Elimination with pivoting will be applied.

5. If A is sparse, UMFPACK will be used.[Here to see more:http://www.cise.ufl.edu/research/sparse/umfpack/].

6. If A is not squared, then QR will be used.

One thing that I want to mention is UMFPACK: Unsymmetric MultiFrontal sparse LU Factorization. It is fast since it re-orders the elements of L and U to make them as sparse as possible, however, iterative methods(Krylov subspace) such as GMRES, MINRES, CG, PCG, QMR, CGS, BI-CGSTAB compared to built-in method ‘\’ are relatively slow, and converges very slowly when problem is ill-conditioned and other slow algorithms like Jacobi , Gauss Seidel, SOR,SSOR will not be mentioned any more……

About YiMin

This is just a nerd PhD student of Math@UT Austin.

2 thoughts on “Inversion[note]

  1. YiMin says:

    Benchmarks will be posted later, I suppose.

  2. Juan says:

    过来问候 Yimin !谢谢留言!
    😀

Comments are closed.