Accurate and Efficient Matrix Computations with Structured Matrices

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

This project concentrates on developing a thorough theoretical and numerical analysis and designing algorithms for accurate and efficient matrix computations with structured matrices. Algorithms for computing the eigenvalues, singular values and the solution to a linear system are executed on modern computers in finite precision arithmetic. As a consequence, round-off errors can cause loss of accuracy in these computations when ill-conditioned problems are solved, usually leaving the user with the only remedy of running the same algorithm using wider precision at a much higher computational cost. The goal of this study is to identify matrix structures and understand matrix properties which make it possible to design algorithms that will perform matrix computations accurately in the face of roundoff and will succeed in computing the right answer even when the traditional structure-ignoring algorithms fail. The matrix structures that will be studied appear very often in practical applications and include: Totally positive, tridiagonal, M-matrices, (generalized) Vandermonde, Cauchy, etc. and combinations thereof. Most scientific and engineering computations compute in their core the solution of a linear system, an eigenvalue or a singular value problem. Typical examples include simulations automobile crash-testing, testing bridge and building structural designs and behavior under stress (earthquakes, explosions, etc.). Structure-exploiting accurate and efficient matrix algorithms make running such applications faster, easier, less reliant on super computers and allow for computations of more sophisticated designs and simulations than is currently possible. As a result it may become easier to design safer cars, which cost, weight and pollute less, and it may allow for an easier and faster design of bridges, buildings and other structures that are less expensive, faster to build and are also less susceptible to the forces of nature.