Re: LU decomposition: backsubstitution available?

[Michael Hanke]

On Wed, 25 Mar 1998, Mario Storti wrote:

> >>>>> On Wed, 25 Mar 1998 10:27:40 +0100 (MET), 
> >>>>>      Thomas Hoffmann <address@hidden> said:
> 
> > It is a known procedure for the solution of a sequence of
> > systems of linear equations Ax=b with only varying rhs to
> > make once a LU decompostion of A (function lu() of octave)
> > and then backsubstitute for the several b's, e.g.
> >   x=backsubs(l,u,b)
> > As e.g. RLaB has such an mechanism, I thought of similar
> > functionality in Octave, but did not find any.
> 
> > Can anybody shed some light on this?
> 
> > Thomas.
> 
> I faced this same problem  before. It would be   nice to have  someone
> writing a 'backsubs' routine. It seems to me that it should be written
> in fortran in order to be efficient (do to the triangular structure of
> l and u). 
> 
> Meanwhile, I think  that you make a  significant save in computational
> effort if compute the inverse of A, say
> 
> > invA=inv(A);
> > x1=invA*b1;
> > x2=invA*b2;
> > x3=invA*b3;
> > .
> > .
> 
> since  computing the  inverse requires  O(N^3) ops. and  matrix-vector
> multiplication requires only O(N^2). Of course, if you know all the
> rhs's at once, then you can put them incolumns in a matrix B and then
> make a:
> 
> X= A \ B;
> 
> and solve all the systems at once. 
> 
In a matlab paper, I found a better solution as a side remark for
sparse matrices: The matrix division routine checks before trying any
LU decomposition if the matrix to be "inverted" is triangular (or a
permuted triangular matrix). If so,
the simple forward/backward substitution takes place. The amount for
checking this property for full matrices is O(n^2). Maybe it is a
better idea to carry a tag for every matrix??

Michael

+---------------------------------------------------------------+
|  Michael Hanke                Royal Institute of Technology   |
|                               NADA                            |
|                               S-10044 Stockholm               |
|                               Sweden                          |
+---------------------------------------------------------------+
|  Visiting address:            Lindstedtsvaegen 3              |
|  Phone:                       + (46) (8) 790 6278             |
|  Fax:                         + (46) (8) 790 0930             |
|  Email:                       address@hidden               |
|                               address@hidden       |
+---------------------------------------------------------------+