From maintainers-request at octave dot org Wed Dec 8 04:34:54 2004 Subject: permutations of matrix to triangular form? From: David Bateman To: maintainers at octave dot org Date: Wed, 8 Dec 2004 11:32:17 +0100 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 David dot Bateman at motorola dot com 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