Using Interval Analysis to Bound Numerical Errors in Scientific Computing

In scientific computing, the approximation of continuous physical phenomena by floating-point numbers gives rise to rounding error. The behaviour of rounding errors is difficult to predict, and most scientific applications ignore it. For applications in which the accuracy of the result is critical, this is not an acceptable choice. Interval analysis is an alternative to conventional floating-point computation that offers guaranteed error bounds. Despite this advantage, interval methods have rarely been applied in high performance scientific computing. In part, this is because of the additional cost associatedwith performing interval operations over the corresponding floating-point operations. Another issue is the lack of example applications of interval analysis; many scientific users simply do not know that an alternative to floating-point computation exists. This thesis develops and demonstrates techniques by which interval analysis can be feasibly applied to scientific computing. Methods are shown by which the performance of interval codes may be significantly improved on the UltraSPARC platform: hand-optimised codes for vector functions are developed that are around 60% faster than the Sun interval implementation, and an alternative method of interval multiplication is developed that is around 30% faster than the method used by other implementations. The benefits of interval analysis are demonstrated through application to an example scientific problem: the evaluation of electrostatic potentials. Alternative methods of evaluation are analysed: two new accurate methods of summation are proposed and proven to reduce rounding error in this application. This demonstration includes what is believed to be the first interval implementation of the fast multipole method. The implementation is used to explore the balance between rounding and truncation errors in the method, which has previously been ignored. The results suggest that rounding error may affect the accuracy that can be practically achieved using the method. The results also provide guidance in choosing parameters to minimise error.