Mathematical Sciences: Sparse Matrix Problems: Data Structures, Algorithms, and Applications

数学科学：稀疏矩阵问题：数据结构、算法和应用

• 批准号: 9504974
• 负责人: Timothy Davis
• 金额: $ 25.05万
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-08-01 至 1999-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9504974&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Sparse; Matrix; Problems

Davis This project addresses a range of sparse matrix problems, from data structures, to algorithms, to applications. The unifying theme is the unsymmetric-pattern multifrontal method: its implementation, data structures, and applicability to difficult sparse matrix problems in semiconductor device and process simulation. The unsymmetric-pattern multifrontal method encompasses both the multifrontal technique and an approximate degree update algorithm that is much faster (asymptotically and in practice) than computing the true degrees. Although this method uses upper bounds, the ordering quality for both the unsymmetric (Markowitz cost) and symmetric (minimum degree) algorithms does not suffer. The investigator and his colleagues develop parallel factorization and ordering algorithms based on these approaches. They also develop parallel memory allocators (a fast-fits algorithm), a dynamic task graph (dynamic, since the pivot ordering determines the task dag), the development of both pessimistic and optimistic synchronization methods for frontal matrix ``collision'' in the combined uni/multifrontal approach, and other distributed data structures (such as a distributed priority queue for finding pivots of low approximate degree) required for these algorithms. The algorithms and data structures they develop are applied to semiconductor device and process simulation. This is a challenging application, placing a burden not only on the numerical factorization, but on the symbolic ``overhead'' as well. The problems in this domain are based on irregular, adaptive grids (both 2D and 3D). Both direct methods and iterative methods are used. The iterative method used is a preconditioned biconjugate gradient algorithm, with an incomplete LU factorization as the preconditioner. The investigators develop and employ an incomplete multifrontal factorization algorithm, and a multifrontal-based approach for computing the sparse inverse for use as a prec onditioner. The parallel methods the investigators develop are widely applicable to many computationally intensive problems, in particular the modeling of complex physical phenomena: structural stress and fluid-flow in and around the space shuttle, thunderstorms and tornados, circuits and semiconductor devices, the mixing and combustion of complex turbulent reacting flows, the flow of oil in a reservoir, the optimal distillation of gas and petroleum products, and so on. Parallel sparse matrix algorithms and the data structures they require can help to solve these problems. Where will a tornado hit? How fast can you make a CPU chip run? How can automobile emissions be reduced and gas efficiency be increased at the same time? How do we get more gas out of the same amount of crude oil, and how do we get more crude oil out of an oil reservoir? Answering these questions accurately requires a great deal of computation - and much of that computation involves large, sparse matrices. High-speed computation is required - it does no good to predict where a tornado will hit after it has already passed by and done its destruction. Thus the need for parallel algorithms and data structures. The methods the investigators develop are made widely available to researchers in these and other areas. To ensure that the methods are in fact useful for ``real world'' problems, they are incorporated into a widely-used semiconductor simulation package, the Florida Object-Oriented Device/Process Simulator (FLOODS/FLOOPS). FLOODS/FLOOPS is in use in dozens of companies and universities, and its methods form the basis of many commercial semiconductor simulation packages.

戴维斯 这个项目解决了一系列稀疏矩阵问题，从数据结构到算法，再到应用程序。 统一的主题是非对称模式多波前方法：它的实现，数据结构，并适用于困难的稀疏矩阵问题，在半导体器件和工艺模拟。 非对称模式多波前方法包括多波前技术和近似度更新算法，该算法比计算真实度快得多（渐近和实际）。 尽管这种方法使用上界，但非对称（马科维茨成本）和对称（最小度）算法的排序质量都不会受到影响。 研究人员和他的同事们开发了基于这些方法的并行因式分解和排序算法。 他们还开发了并行内存分配器（快速匹配算法），动态任务图（动态的，因为枢轴排序决定了任务DAG），在组合的单/多波前方法中用于波前矩阵“碰撞”的悲观和乐观同步方法的开发，以及这些算法所需的其他分布式数据结构（例如用于寻找低近似度枢轴的分布式优先级队列）。 他们开发的算法和数据结构被应用于半导体器件和工艺模拟。 这是一个具有挑战性的应用程序，不仅对数值分解造成负担，而且对符号“开销”也造成负担。 该领域的问题基于不规则的自适应网格（2D和3D）。 采用直接法和迭代法。 所用的迭代方法是一个预条件双共轭梯度算法，与不完全LU分解作为预条件。 研究人员开发并采用了一种不完整的多波前分解算法，以及一种基于多波前的方法来计算稀疏逆，用作预测器。 研究人员开发的并行方法广泛适用于许多计算密集型问题，特别是复杂物理现象的建模：航天飞机内部和周围的结构应力和流体流动，雷暴和龙卷风，电路和半导体器件，复杂湍流反应流的混合和燃烧，油藏中的油流，并行稀疏矩阵算法及其所需的数据结构可以帮助解决这些问题。 龙卷风会袭击哪里？ 你能让CPU芯片运行多快？ 如何在减少汽车排放的同时提高燃气效率？ 我们如何从同样数量的原油中获得更多的天然气，我们如何从油藏中获得更多的原油？ 准确地解决这些问题需要大量的计算--而且大部分计算都涉及到大型稀疏矩阵。 高速计算是必需的--在龙卷风已经经过并造成破坏之后，预测它将袭击哪里是没有好处的。 因此需要并行算法和数据结构。 研究人员开发的方法被广泛提供给这些和其他领域的研究人员。 为了确保这些方法实际上对“真实的世界”问题有用，它们被纳入一个广泛使用的半导体仿真软件包，佛罗里达面向对象的设备/过程模拟器（FLOODS/FLOOPS）。 FLOODS/FLOOPS在数十家公司和大学中使用，其方法构成了许多商业半导体仿真软件包的基础。