dgh@validgh.com (David G. Hough on validgh) (06/13/91)
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