What Is the Quickest Method to Solve $ A x = b $ for $ A $ Being Sparse Semi Definite Positive Matrix?

Question

A is a huge scale of sparse symmetric semi-positive matrix. In MATLAB, the solution can be solved by

    b=A\b;

But it is very slow. Are there any quicker methods to solve this kind of problem?

Answer 1

The answer depends on properties of the matrix $ A $.

For large matrices sometimes iterative methods are faster than direct methods (Which is what behind \).
Try MATLAB pcg() (Preconditioned Conjugate Gradients Iterative Method) for instance.

Moreover, other properties also count.
For example, if the Matrix is Circulant Matrix, you better solve the system in the Fourier Domain.

If the matrix is Toeplitz, you better use Levinson Recursion (See my Levinson Recursion Implementation).

So the best solver is the one which matches your matrix properties.

If the matrix is arbitrary and small to medium in its size, this operator is probably the fastest out there.
MATLAB uses Intel MKL behind the scene for solving those system.
Intel MKL is the fastest BLAS / LAPACK library out there.