Re: Efficient backsubstitution for upper triangular matrix

[David Bateman]

Paul Roberts wrote:

> Hello,
>
> I was wondering if there is a explicit function in octave to
> efficiently compute the solution to: Ax = b when A is upper triangluar
> and non-singular.
>
> Thanks,
>
> Paul
>  
This one is on my ToDo list. I've done a poly-morphic solver for the 
sparse matrices that includes special cases for the solves of triangular 
matrices, but it is definitely worthwhile to do the same thing for full 
triangular, positive definite and perhaps even permuted triangular 
matrices... You can use the matrix_type function in 2.9.3 to flag the 
matrix type or just let octave figure it out for itself, which is fairly 
efficient. So if your matrix is sparse then in 2.9.3 there are the tools 
you need to do this.

In octave-forge there is a cholesky function that is then combined with 
a home rolled back subsitution (not dtrsm unfortunately) and a special 
triangular matix type, but has no way to flag a matrix as triangular, so 
it is quite limited and not as fast as it could be since it does profit 
from ATLAS.

In any case I intend to have the special treatment of full triangular 
matries done for version 3.0.

Regards
David

--
David Bateman                                address@hidden
Motorola Labs - Paris                        +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



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------