Testing linear algebra software

摘要

How can we test the correctness of a computer implementation of an algorithm such as Gaussian elimination, or the QR algorithm for the eigenproblem? This is an important question for program libraries such as LAPACK, that are designed to run on a wide range of systems. We discuss testing based on verifying known backward or forward error properties of the algorithms, with particular reference to the test software in LAPACK. Issues considered include the choice of bound to verify, computation of the backward error, and choice of test matrices. Some examples of bugs in widely used linear algebra software are described.