Fast Sparse LU substitution

A dedicated mex-file for use with UMFPACK to complete the forward and back substitution quickly

Description

This is a dedicated mex-file for use with UMFPACK to efficiently complete the permuted forward/back substitution to solve linear systems, A*x = b when A is sparse and b is a dense vector.

UMFPACK is used when the MATLAB function "lu" is called with 4 outputs:

[L,U,P,Q] = lu(A, tol);

The mex-file provides the solution:

x = LUsubs(L,U,P,Q,b);

and generally results in a CPU time saving of a factor of 3-4 (On my machine).

Type "LUdemo" and "help LUsubs" for more information.

A pre-compiled version is included. If you have the MATLAB compiler you can re-compile the file via:

mex -O LUsubs.c

You will need either windows or the compiler to use this function.

See Tim Davis's website (UMFPACK's author) for some great linear algebra routines:

http://www.cise.ufl.edu/~davis/

P.S This sort of thing is important when solving PDE's numerically.

NOTE: The zip file should now work (03/04/2006), but I have removed the demo...

See also my fast sparse-matrix-vector-product function:

http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=10556&objectType=file

• MATLAB release: MATLAB 6.5 (R13)

[Shelley Lee]

It's really faster. Unfortunately, it does
not support complex matrices.

[Donghua Xu]

It appears to work in the x32 but not the x64 version of Matlab. In the latter, it is actually slower than the built-in method, particularly for large sparse matrices. I recommend the cs_lu or klu methods by TA Davis which are very efficient in the x64 version.