Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!lll-winken!sun-barr!newstop!exodus!rbbb.Eng.Sun.COM!chased
From: chased@rbbb.Eng.Sun.COM (David Chase)
Newsgroups: comp.arch
Subject: Re: massive linpack
Message-ID: <14753@exodus.Eng.Sun.COM>
Date: 7 Jun 91 18:45:58 GMT
References: <9106070135.AA02947@ucbvax.Berkeley.EDU>
Sender: news@exodus.Eng.Sun.COM
Organization: Sun Microsystems, Mt. View, Ca.
Lines: 48

jbs@WATSON.IBM.COM writes:
>
>         Richard Lethin asks:
>At what size N for massive linpack does the accumulated numerical fuzz
>swamp the precision available in a double precision number?

>         Very large.  Typical relative error (in the vector norm sense)
>in the solution is n*c*e, where n is matrix size, c is condition number
>and e is machine epsilon (2**-52 for IEEE double).  Therefore if you
>want a solution accurate to 1 part in 1000 (10 bits) and your matrix
>has condition number less than 1000 (10 bits) your n can be 2**30 or
>10**9.  This would require 10**18 storage and 10**27 ops to solve so
>is well beyond current machines.  Note once you have any bits in your
>answer you can obtain more by iterative improvement an order N*2 pro-
>cess.

I don't have the time to prove that you're wrong here, but I think
that you are either wrong, or else being very misleading.  In general,
why should we believe you?  What do you usually do?  Goldberg and
Hough are experts, as are the people that I took numerical analysis
from too many years ago.  Are you an expert?  (I only know enough to
know when I should be suspicious, but I'm suspicious.)

First, you haven't said anything about worst case, which must be
worried about.  In addition, you haven't discussed a typical condition
number.

Second, I know that the NA people I once worked with were interested
in using exact arithmetic for error analysis. (There's a paper by
Boehm, O'Donnell, and Riggle in the 1986 Lisp & FP conference -- when
I say "exact", I mean an answer guaranteed to be within epsilon of the
true answer).  This means that double precision isn't good enough for
very accurate error analysis, though I don't know how they defined
"very accurate".  I suspect that the worst case bounds on error
estimation were not satisfactory.

Third, "LINPACK" is not a numerical analysis algorithm.  There is a
wide variety of algorithms in LINPACK, with varying stability and
cost.  If you don't specify the algorithm, how are we to know what you
are talking about?  Is it GE, GEPP, GEFP, QR, SVD, or Cholesky?  Band
matrix, or not?  The worst case on GEPP (which is what I think you
meant) is still pretty bad, though I've also heard (from an expert)
that it is almost never seen.  If (as I think you are saying) GEPP is
so good, then why do we bother with more stable algorithms like QR and
SVD?

David Chase
Sun