Accuracy and Stability of Numerical Algorithms

by Nicholas J. Higham, SIAM, January 1996.

What is the most accurate way to sum floating point numbers? What are the advantages of IEEE arithmetic? How accurate is Gaussian elimination, and what were the key breakthroughs in the development of error analysis for the method? The answers to these and many related questions are included here.

This book gives a thorough, up-to-date treatment of the behavior of numerical algorithms in finite precision arithmetic. It combines algorithmic derivations, perturbation theory, and rounding error analysis. Software practicalities are emphasized throughout, with particular reference to LAPACK and MATLAB. The best available error bounds, some of them new, are presented in a unified format with a minimum of jargon. Because of its central role in revealing problem sensitivity and providing error bounds, perturbation theory is treated in detail.

Historical perspective and insight are given, with particular reference to the fundamental work of Wilkinson and Turing, and the many quotations provide further information in an accessible format.

The book is unique in that algorithmic developments and motivations are given succinctly and implementation details minimized, so that attention can be concentrated on accuracy and stability results. Here, in one place and in a unified notation, is error analysis for most of the standard algorithms in matrix computations. Not since Wilkinson's Rounding Errors in Algebraic Processes (1963) and The Algebraic Eigenvalue Problem (1965) has any volume treated this subject in such depth. A number of topics are treated that are not usually covered in numerical analysis textbooks, including floating point summation, block LU factorization, condition number estimation, the Sylvester equation, powers of matrices, finite precision behavior of stationary iterative methods, Vandermonde systems, and fast matrix multiplication.

Although not designed specifically as a textbook, this volume is a suitable reference for an advanced course, and could be used by instructors at all levels. It is designed to be a comprehensive reference and its bibliography contains more than 1100 references from the research literature.

Audience
Specialists in numerical analysis as well as computational scientists and engineers concerned about the accuracy of their results will benefit from this book. Much of the book can be understood with only a basic grounding in numerical analysis and linear algebra.

About the Author
Nicholas J. Higham is a Professor of Applied Mathematics at the University of Manchester, England. He is the author of more than 50 publications and is a member of the editorial boards of the SIAM Journal on Matrix Analysis and Applications, the IMA Journal of Numerical Analysis, and Linear Algebra and Its Applications. He is the author of Handbook of Writing for the Mathematical Sciences (SIAM, 1993).

Contents
Preface; About the Dedication; Chapter 1: Principles of Finite Precision Computation; Chapter 2: Floating Point Arithmetic; Chapter 3: Basics; Chapter 4: Summation; Chapter 5: Polynomials; Chapter 6: Norms; Chapter 7: Perturbation Theory for Linear Systems; Chapter 8: Triangular Systems; Chapter 9: LU Factorization and Linear Equations; Chapter 10: Cholesky Factorization; Chapter 11: Iterative Refinement; Chapter 12: Block LU Factorization; Chapter 13: Matrix Inversion; Chapter 14: Condition Number Estimation; Chapter 15: The Sylvester Equation; Chapter 16: Stationary Iterative Methods; Chapter 17: Matrix Powers; Chapter 18: QR Factorization; Chapter 19: The Least Squares Problem; Chapter 20: Underdetermined Systems; Chapter 21: Vandermonde Systems; Chapter 22: Fast Matrix Multiplication; Chapter 23: The Fast Fourier Transform and Applications; Chapter 24: Automatic Error Analysis; Chapter 25: Software Issues in Floating Point Arithmetic; Chapter 26: A Gallery of Test Matrices; Appendix A: Solutions to Problems; Appendix B: Singular Value Decomposition, M-Matrices; Appendix C: Acquiring Software; Appendix D: Program Libraries; Appendix E: The Test Matrix Toolbox; Bibliography; Name Index; Subject Index.

January 1996 / xxviii+688 pp. / Softcover ISBN 0-89871-355-2
List Price $39.00/SIAM Member Price $31.20 / Order Code OT48

To Order:
Use your credit card (AMEX, MasterCard, and VISA): Call toll free in USA: 800-447-SIAM; Outside USA call: 215-382-9800 Fax: 215-386-7999; E-mail: service@siam.org

Or send check or money order to: SIAM, Dept. BKFP95, P.O. Box 7260, Philadelphia, PA 19101-7260 Payments may be made by wire transfer to SIAM's bank: PNC Bank, 3535 Market Street, Philadelphia, PA 19104; ABA Routing #031000053; Account Name: Society for Industrial and Applied Mathematics; Account #8550970454

Shipping and Handling: USA: Add $2.75 for the first book and $.50 for each additional book. Canada: Add $4.50 for the first book and $1.50 for each additional book. Outside USA/Canada: Add $4.50 per book. All overseas delivery is via airmail.

Click here to order.