Re: Matrices and "type tags"

[Michael Hanke]

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:                       address@hidden               |
|                               address@hidden       |
+---------------------------------------------------------------+



-----------------------------------------------------------------------
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
-----------------------------------------------------------------------