From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Re: 2 smallest eigenvalues of dense matrix
Date: 29 Apr 1999 11:45:44 GMT
Newsgroups: sci.math.num-analysis
Keywords: bunch-parlett matrix decomposition

In article <37282038.A7F036E0@ruc.dk>,
 gnalle <gnalle@ruc.dk> writes:
|> Is there a way of finding the two smallest (most negative) eigenvalues
|> og a large dense symmetric matrix. 
|> 
|> I am doing differential geometry, so I have a very big dense matrix. I
|> have a function
|> f and I have found the critical points where 
|> 
|> grad f=0. 
|> 
|> Now I would like to know if those points are saddlepoints, so I would
|> like to know if the Hesse matrix has exactly 1 negative eigenvalue. Is
|> there a way of dicovering that, without having to calculate all the
|> eigenvalues. Unfortunately I do not know if the absolute value of the
|> negative eigenvalue is especially large or small.
since your matrix is dense, the problem of computing the two (or some)
smallest eigenvalues is expensive anyway. ARPACK is a package which 
allows you this quite efficiently, as far as possible. 
http://ftp.caam.rice.edu/pub/software/ARPACK
but since you are only interested whether there are some negative eigenvalues,
the bunch-parlett-decomposition is a much more adequate tool for you. 
it provides a decomposition
   P^TAP = L D L^T
where P is a permutation matrix, L lower triangular with diagonal 1,,,,,1
and D is block diagonal consisting of 1 by 1 and 2 by 2 blocks.
from  sylvesters theorem of inertia it follows that A has as many eigenvalues
>0, =0, <0 as D has, and the latter is easily counted. software for the
bunch parlett decomposition is e.g. in meschach in netlib.
http://www.netlib.org.
(I could mail you a f77-version for dense matrix, if necessary)
hope this helps
peter