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.

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