From: "Chip Eastham" <eastham@bellsouth.net>
Subject: Re: Determinant of big matrices
Date: Sun, 31 Dec 2000 16:42:49 GMT
Newsgroups: sci.math,sci.math.num-analysis
Summary: [missing]

"Chip Eastham" <eastham@bellsouth.net> wrote in message
news:dmN26.4519$Gc5.146039@news1.atl...
>
> "Glynne" <glynnec1.spam@spam.home.com> wrote in message
> news:gNJ26.86481$x6.40141487@news2.rdc2.tx.home.com...
> > In article <92crdf$7qg$1@nnrp1.deja.com>,  <stelian24@my-deja.com> wrote:
> > :Hi!
> > :
> > :I'm trying to calculate the determinant for some
> > :very big matrices (up to 1000x1000) with standard
> > :methods, but it doesn't seem to work very well
> > :(because of roundoff errors?). Is there some less
> > :sensible method for calculating determinants of
> > :big matrices (using logarithms perhaps)?
> >
> > Hmmm......I suppose you could use the formula:
> >   det(M) = exp(trace(log(M)))
> >
> > Where log(M) is calculated via some method suitable for your particular
> > matrix,
> > e.g. a Krylov method for a large sparse M.
> >
> > ~Glynne
> >
>
> An elegant suggestion, esp. if restated:
>
>  log det(M) = trace log(M)
>
> but this requires M be positive definite.
> Even then, if M is nearly singular, log(M)
> blows up.
>
> -- Chip
>

Glynne and Dave Rusin each dropped me a friendly note to
"ask" about some shortcomings in my logic!

I misstated what I was trying to get at in my original post,
that the eigenvalues of M should be positive in order for
log(M) to exist.  Instead of saying "positive definite", I should
have said "positive spectrum" (or better yet, spectrum with
positive real part).  The notions are not equivalent unless
one speaks of symmetric matrices, which I did not mean to
assume.

But in fact as D. Rusin pointed out to me, the exponential
function is surjective in the ring of complex matrices, except
for singular matrices.  So, provided one is willing to hassle
with an appropriate branch cut in the complex plane, the
formula given by Glynne will work for any nonsingular M,
albeit at the price of veering off into complex arithmetic.

If one sticks to real matrices with eigenvalues having postive
real part, then a power series expansion for log(M) can be
made to converge (and give a real result).  If the eigenvalues
are contained in some disk of the complex plane that does
not include the origin, then a power series expansion of log(x)
about the center of that disk will do the trick (and in the real
part positive case one can choose the center on the positive
real axis).  If the smallest disk enclosing the eigenvalues also
includes the origin, though, a power series expansion won't
converge and we would need to turn to rational functions in
M, based on continued fraction approximations to log(x).

I strongly suspect that one can avoid complex arithmetic for
real matrices with the rational approximations.  But having
to square M or (shudder) invert M or a related matrix is in
practical terms a lot of work, O(n^3), unless M has sparse
or other special structure.

Regrets,
Chip