Implementation of Matrix Division in Matalb

Hi, I am trying to solve a sparse linear system of more than 3 million equations(obtained from a Laplacian matrix). I tried iterative solvers like cgs, bicg, etc but matlab's matrix division takes less time then iterative solvers. Does anybody knows how matrix division is implemented in Matlab? Can you suggest me any fast solvers for my problem. I tried CUDA based libraries like CUSP, OpenNL, etc.

Answer 1

[Ivan van der Kroon]

Sleijpen and Van der Vorst 1996 estimate the computation costs of direct methods as N^2.3 with memory costs N^1.7, while iterative methods yield N^1.2 and N^1 respectively for N by N systems (tested for three-dimensional elliptic boundary-value problems).

Now direct methods always have some black-box and are generally not suited for large sparse matrices. I really cannot answer why your system gives you better division costs. However, I saved the following flowchart from one of my courses. It is on the last page of http://www.netlib.org/templates/templates.pdf .

For instance, cgs is for non symmetric matrices where the transpose is not available and you have little memory. If division is still faster and you find out why, let me know; strangely I find it really interesting.

Answer 2

[Andrew Newell]

I think most of MATLAB's linear algebra is based on LAPACK (see MATLAB incorporates LAPACK ).

EDIT: But not general sparse systems, according to James. Maybe you could try ScaLAPACK.

[James Tursa]

Not the sparse solvers.