Accurate and Efficient Matrix Computations with Structured Matrices

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

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.