Accurate and Efficient Matrix Computations with Structured Matrices

使用结构化矩阵进行准确高效的矩阵计算

• 批准号: 0314286
• 负责人: Alan Edelman
• 金额: $ 12.64万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-07-15 至 2006-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0314286&HistoricalAwards=false
• 关键词: Accurate; Efficient; Matrix; Computations; Structured

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.

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