🚀 go-pugleaf

James Shearer caught a mistake in my previous posting about the Linpack
benchmark.  The point of my posting was that the benchmark input data
was taken from a uniform random distribution, and so the problem was very
well conditioned, and practically any algorithm - and any kind of arithmetic - 
would produce satisfactory results.  

Shearer noticed that I had overstated the case somewhat, since an algorithm
that intentionally sought minimal rather than maximal pivot divisors was apt
to do rather poorly, so I had to correct my statement to practically any
algorithm that was probably going to be implemented.  I was curious to see
how the details worked out in practice.

I modified ISAMAX in the standard Linpack benchmark code to optionally
choose the minimum-magnitude pivot rather than the normal maximum-magnitude,
or to choose the first candidate pivot which is equivalent to doing no
pivoting.  A 100x100 single-precision or double-precision
matrix was enough to confirm that the
minimum-magnitude algorithm produces garbage results.

However the NOPIVOT option didn't do badly and produced results that might
be acceptable for some uses:

dimension	method	minimum normalized	error
			pivot	residual	x-1		

100 single	normal	2	1.6		1e-5
100 single	nopivot	.13	70		3e-4
1000 single	normal	2	11		2e-4
1000 single	nopivot	7e-2	2600		8e-2
1000 double	normal	2	10		5e-13
1000 double	nopivot	6e-2	3900		6e-11

The Linpack benchmark is intended to solve an equation A x = b
where the elements of A are chosen from a uniform random distribution
and b is computed so that the correct solution x is close to a vector
of 1's.  So looking at the size of components of x-1's is supposed to 
indicate how accurate the solution is, although
the residual b - A x is a more reliable measure of quality.

The foregoing results came from a SPARCstation.  The bottom line is
that even with no pivoting, Gaussian elimination 
on a 1000x1000 matrix of uniform random numbers will lose only 2 or 3
digits in the result compared to partial pivoting.   Any consortium-
derived benchmark suite that used such a program probably wouldn't
even notice - for instance,
SPEC supplies special tools for validating results that ignore
the least significant digits.
-- 

David Hough

dgh@validgh.com		uunet!validgh!dgh	na.hough@na-net.ornl.gov