Applications of randomization to floating-point arithmetic and to linear systems solutions
Brad Alan Pierce · 1997
We report on two new applications of input randomization to scientific computing. The first uses preprocessing with certain randomized FFT-like transforms to reduce the solution time for large dense linear systems. The second uses randomized correction of rounded-off operands in floating-point arithmetic as the basis for a new a posteriori error analysis method. Efficient parallel computing demands regular, scalable algorithms. Moreover, such algorithms are easier to program and verify and are more likely to provide practical templates for the design of special-purpose hardware. Unfortunately, such algorithms tend to work on most problems only, rather than on all problems. The traditional approach is to tangle up intuitive algorithms with extra code that enables them to handle so-called degenerate cases. Gaussian elimination, for example, is usually augmented with partial pivoting to deal with the possibility of encountering a singular leading submatrix. Partial pivoting, however, entails numerous nonlocal data movements and is expensive on a modern high-performance computer. By preprocessing with certain randomizing FFT-like transforms, the inputs can be homogenized, yielding, with probability 1, problems which can be handled even by 'naive' algorithms. While formal roundoff error analysis is useful during the design of numerical algorithms, there is also a need for methods that can estimate the roundoff error in specific computations, that is, for a particular computer, compiled program, and input. We present a practical method for such a posteriori error analysis. The foundation of this method is a proposed enhancement of binary floating-point arithmetic that would apply randomization to rounded-off operands before they take part in an operation. Instead of treating imprecise operands as if they were precise, we would add to them a random guess of the amount lost during rounding. Our error analysis method begins by applying the program to the input several times. Because of the randomized arithmetic, slightly different answers are obtained from each recalculation. These results constitute a sample distribution, which can be analyzed statistically to yield measures of the level of uncertainty due to roundoff.