permutations of matrix to triangular form?

[David Bateman]

Thinking yet again about implementing the triangular/banded solvers,
I re-examined what matlab did as described at

http://www.mathworks.com/access/helpdesk/help/techdoc/ref/mldivide.html

Where it seems to test the type of the matrix (and presumably caches
it) before solving with the "\" and "/" operators. Presumably
something similar is done in a few other places like eig, etc.  Doing
it matlabs way has the advantage that the banded and triangular types
are not explicitly needed.

Last night I was investigating how to do something similar with the
sparse class, and basically just wrote a small piece of code to recognize
the type of a matrix (I attach it here if you are interested, though it
needs to be used with the sparse class I've been writing). The interest
of this was to take Andy's back substitution code from his sparse inverse
and use it directly in the "\" and "/" operations, and at the same time
treat banded with LAPACK and diagonal matrices.

In any case, it seems that I can recognize all of the matrix types I
programmed for. But the permuted triangular form is not so clear-cut.
The permutation vector is not explicitly passed and so must be
reconstructed. As this is a test to check which solver will be used,
the means of creating this permutation, or at least checking that it
is possible must be low cost. Frankly, I can't see what matlab is doing.

What I think might be happening is that they are performing an LU
factorization of the matrix and is either L or U of the factorization
is diagonal, then only a single back substitution is needed.  Though
in this case I don't see why matlab makes a distinction between case 6
and case 7 in the docs for mldivide, as there won't be all that much
difference in the computation time.

Does anyone know of a simple, low-cost means of attempting to convert
find where a permutation of a matrix to triangular form exists? Does
anyone have any more understanding of what matlab is doing in this 
case?

Regards
David

-- 
David Bateman                                address@hidden
Motorola CRM                                 +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 1 69 35 77 01 (Fax) 
91193 Gif-Sur-Yvette FRANCE

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary