From help-octave-request at bevo dot che dot wisc dot edu  Thu Dec  9 04:06:37 1999
Subject: Re: Matrices and "type tags"
From: Michael Hanke <hanke at nada dot kth dot se>
To: Thomas Hoffmann <hoffmann at ehmgs2 dot et dot tu-dresden dot de>
Cc: help-octave at bevo dot che dot wisc dot edu
Date: Thu, 9 Dec 1999 10:24:33 +0100

On Thu, 09 Dec 1999, Thomas Hoffmann wrote:
>In the recent talk about a "backsub" function the idea of automatically recognizing 
>tridiagonal matrices surfaced.
>
>If a matrix has not a special type "tridiagonal", then it has to have a "tag", which says 
>that the matrix has this property (RLaB uses such "tags", matrices are lists there) or 
>one has to check the matrix for this property (which takes a lot of time).
[snip]
>Any opinions?
I was thinking about that subject a little bit. I do not think that it is
necessary to introduce a special tag for tridiagonal matrices. I even do not
like the idea of having a special backsub function. Instead, it would be better
to overload the backslash operator. If this is done on the fortran level, it
does not seem to be expensive.

The lu decomposition is an order n^3 process, using a tridiagonal matrix
(backsubstitution) is an order n^2 process. Testing for tridiagonality (even
permuted tridiagonality as obtained after [L,U]=lu(A)) has exactly the same
complexity. If the rows of L must be permuted first, an O(n log n) sorting
process is additionally involved. So the loss in efficiency is probably less
than a factor of 2. I think that this is tolerable.

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:                       hanke at nada dot kth dot se|                              |
|                               na dot mhanke at na-net dot ornl dot gov|              |
+---------------------------------------------------------------+



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

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