MODULAR ARITHMETIC FOR LINEAR ALGEBRA COMPUTATIONS IN THE REAL FIELD

The aim of this work is to decrease the bit precision required in comp utations without affecting the precision of the answer, whether this i s computed exactly or within some tolerance. By precision we understan d the number of bits in the binary representation of the values involv ed in the computation, hence a smaller precision requirement leads to a smaller complexity. We achieve this by combining the customary numer ical techniques of rounding the least significant bits with the algebr aic technique of reduction module an integer, which we extend to the r eduction module a positive number. In particular, we show that, if the sum of several numbers has small magnitude, relative to the magnitude of the summands, then the precision used in the computation of this s um can be decreased without affecting the precision of the answer. Fur thermore, if the magnitude of the inner product of two vectors is smal l and if one of them is filled with ''short'' binary numbers, then aga in ive may decrease the precision of the computation. The method is ap plied to the iterative improvement algorithm for a linear system of eq uations whose coefficients are represented by ''short'' binary numbers , as well as to the solution of PDEs by means of multigrid methods. So me results of numerical experiments are presented to demonstrate the p ower of the method. (C) 1998 Academic Press.