Error bounds from extra-precise iterative refinement

ABSTRACT

We present the design and testing of an algorithm for iterative refinement of the solution of linear equations where the residual is computed with extra precision. This algorithm was originally proposed in 1948 and analyzed in the 1960s as a means to compute very accurate solutions to all but the most ill-conditioned linear systems. However, two obstacles have until now prevented its adoption in standard subroutine libraries like LAPACK: (1) There was no standard way to access the higher precision arithmetic needed to compute residuals, and (2) it was unclear how to compute a reliable error bound for the computed solution. The completion of the new BLAS Technical Forum Standard has essentially removed the first obstacle. To overcome the second obstacle, we show how the application of iterative refinement can be used to compute an error bound in any norm at small cost and use this to compute both an error bound in the usual infinity norm, and a componentwise relative error bound.We report extensive test results on over 6.2 million matrices of dimensions 5, 10, 100, and 1000. As long as a normwise (componentwise) condition number computed by the algorithm is less than 1/_{max{10,&nsqrt;}ϵw}, the computed normwise (componentwise) error bound is at most 2 max{10, &nsqrt;} · ϵ_w, and indeed bounds the true error. Here, n is the matrix dimension and ϵ_w = 2⁻²⁴ is the working precision. Residuals were computed in double precision (53 bits of precision). In other words, the algorithm always computed a tiny error at negligible extra cost for most linear systems. For worse conditioned problems (which we can detect using condition estimation), we obtained small correct error bounds in over 90% of cases.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: ANSI/IEEE 1985. IEEE Standard for Binary Floating Point Arithmetic, Std 754-1985. ANSI/IEEE, New York, NY.
• 3: Björck, Å. 1990. Iterative refinement and reliable computing. In Reliable Numerical Computation, M. Cox and S. Hammarling, Eds. Oxford University Press, 249--266.
• 4: Jack J. Dongarra , L. S. Blackford , J. Choi , A. Cleary , E. D'Azeuedo , J. Demmel , I. Dhillon , S. Hammarling , G. Henry , A. Petitet , K. Stanley , D. Walker , R. C. Whaley, ScaLAPACK user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 5: Bowdler, H., Martin, R., Peters, G., and Wilkinson, J. 1966. Handbook series linear algebra: Solution of real and complex systems of linear equations. Numerische Mathematik 8, 217--234.
• 6: Demmel, J., Diament, B., and Malajovich, G. 2001. On the complexity of computing error bounds. Found. Comp. Math. 1, 101--125.
• 7: Demmel, J., Hida, Y., Kahan, W., Li, X. S., Mukherjee, S., and Riedy, E. J. 2004. Error bounds from extra precise iterative refinement. Tech. Rep. UCB/CSD-04/1344, Computer Science Division, University of California at Berkeley. (Also LAPACK Working Note 165).
• 8: Dongarra, J., Bunch, J. R., Moler, C. B., and Stewart, G. W. 1979. LINPACK Users' Guide. SIAM, Philadelphia, PA.
• 9: Forum, B. T. 2002a. Basic linear algebra subprograms technical (BLAST) forum standard I. Int. J. High Perform. Comput. Applic. 16, 1--111.
• 10: Forum, B. T. 2002b. Basic linear algebra subprograms technical (BLAST) forum standard II. Int. J. High Perform. Comput. Applic. 16, 115--199.
• 11: Nicholas J. Highham, A survey of condition number estimation for triangular matrices, SIAM Review, v.29 n.4, p.575-596, December 1, 1987 [doi>10.1137/1029112]
• 12: Nicholas J. Higham, FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation, ACM Transactions on Mathematical Software (TOMS), v.14 n.4, p.381-396, Dec. 1988 [doi>10.1145/50063.214386]
• 13: Nicholas J. Higham, Experience with a matrix norm estimator, SIAM Journal on Scientific and Statistical Computing, v.11 n.4, p.804-809, July 1990 [doi>10.1137/0911047]
• 14: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996
• 15: Intel Corporation 2004. IA-32 Intel#8482; Architecture Software Developer's Manual, Volume 1: Basic Architecture. Intel Corporation.
• 16: Kielbasiński, A. 1981. Iterative refinement for linear systems in variable-precision arithmetic. BIT 21, 97--103.
• 17: Xiaoye S. Li , James W. Demmel, SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Transactions on Mathematical Software (TOMS), v.29 n.2, p.110-140, June 2003 [doi>10.1145/779359.779361]
• 18: Xiaoye S. Li , James W. Demmel , David H. Bailey , Greg Henry , Yozo Hida , Jimmy Iskandar , William Kahan , Suh Y. Kang , Anil Kapur , Michael C. Martin , Brandon J. Thompson , Teresa Tung , Daniel J. Yoo, Design, implementation and testing of extended and mixed precision BLAS, ACM Transactions on Mathematical Software (TOMS), v.28 n.2, p.152-205, June 2002 [doi>10.1145/567806.567808]
• 19: Mallock, R. R. M. 1933. An electrical calculating machine. Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character 140, 841 (May) 457--483.
• 20: MathWorks, Inc. Matlab#8482
• 21: Cleve B. Moler, Iterative Refinement in Floating Point, Journal of the ACM (JACM), v.14 n.2, p.316-321, April 1967 [doi>10.1145/321386.321394]
• 22: NAG Ltd 2005. NAG Fortran Library Manual, Mark 21. NAG Ltd, Oxford, UK.
• 23: Siegfried M. Rump, Solving algebraic problems with high accuracy, Proc. of the symposium on A new approach to scientific computation, p.51-120, December 1983, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, United States
• 24: Rump, S. 1995. Verified computation of the solution of large sparse linear systems. Zeitschrift für Angewandte Mathematik und Mechanik (ZAMM) 75, S439--S442.
• 25: Siegfried M. Rump, A class of arbitrarily ill conditioned floating-point matrices, SIAM Journal on Matrix Analysis and Applications, v.12 n.4, p.645-653, Oct. 1991 [doi>10.1137/0612049]
• 26: Snyder, J. N. 1955. On the improvement of the solutions to a set of simultaneous linear equations using the ILLIAC. J. Math. Tables other Aids Comput. 9, 52, 177--184.
• 27: Stewart, G. W. 1973. Introduction to Matrix Computations. Academic Press, New York, NY.
• 28: Strassen, V. 1969. Gaussian Elimination is not optimal. Numer. Math. 13, 354--356.
• 29: Lloyd N. Trefethen , Robert S. Schreiber, Average-case stability of Gaussian elimination, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.335-360, Jul. 1990 [doi>10.1137/0611023]
• 30: Wilkinson, J. H. 1948. Progress report on the Automatic Computing Engine. Report MA/17/1024, Mathematics Division, Department of Scientific and Industrial Research, National Physical Laboratory, (April) Teddington, UK.
• 31: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Error analysis

Keywords:
BLAS, LAPACK, Linear algebra, floating-point arithmetic