On Wed, 25 Mar 1998, Mario Storti wrote:
> >>>>> On Wed, 25 Mar 1998 10:27:40 +0100 (MET),
> >>>>> Thomas Hoffmann <
[hidden email]> 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 matrixvector
> 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 
 S10044 Stockholm 
 Sweden 
++
 Visiting address: Lindstedtsvaegen 3 
 Phone: + (46) (8) 790 6278 
 Fax: + (46) (8) 790 0930 
 Email:
[hidden email] 

[hidden email] 
++