Accurate and Efficient Matrix Computations with Structured Matrices

本项目专注于发展一个全面的理论和数值分析和设计算法，以准确和有效的矩阵计算与结构化矩阵。计算线性系统的特征值、奇异值和解的算法在现代计算机上以有限精度算法执行。因此，在解决病态问题时，舍入误差可能导致这些计算中的准确性损失，通常留给用户的唯一补救办法是以更高的计算成本使用更大的精度运行相同的算法。本研究的目标是识别矩阵结构并理解矩阵性质，从而使设计算法成为可能，这些算法将在面对舍入时准确地执行矩阵计算，并且即使在传统的忽略结构的算法失败时也能成功地计算出正确的答案。我们将研究的矩阵结构在实际应用中经常出现，包括：全正、三对角、m矩阵、（广义）Vandermonde、Cauchy等及其组合。大多数科学和工程计算的核心是计算线性系统、特征值或奇异值问题的解。典型的例子包括模拟汽车碰撞测试，测试桥梁和建筑结构设计和在压力下的行为（地震，爆炸等）。利用结构的精确和高效的矩阵算法使运行这样的应用程序更快，更容易，更少依赖于超级计算机，并允许比目前可能的更复杂的设计和模拟的计算。因此，设计更安全的汽车可能会变得更容易，这些汽车成本、重量和污染都更少，并且可以更容易、更快地设计桥梁、建筑物和其他结构，这些结构更便宜、建造速度更快，也更不容易受到自然力量的影响。

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.