Parallel Algorithms for Incomplete Factorization Preconditions

9807172 Pothen预处理是一种改进求解大型稀疏线性方程组的迭代方法收敛性的技术。迄今为止可用的最健壮的预条件是基于计算系数矩阵的不完全因子，即因子只包括在分解过程中创建的非零元素的一小部分。本课题将设计并实现在串行和并行计算机上计算非对称和对称矩阵的不完全因子预调节器的新算法。这些算法分为两个阶段：在第一个符号分解阶段，确定不完整因子具有非零的位置，并建立不完整因子的数据结构。在第二个数值分解阶段，这些数据结构用于计算与算术运算次数成正比的预条件的数值。没有第一个符号分解阶段，第二阶段就不能有效地实现。新的符号分解算法依赖于用于识别不完全因子具有非零元素的位置的结构理论。从问题图模型的路径结构中识别不完全因子中的非零元素。采用传递约简和对称约简两种图约简技术来减少预测填充所需的数据，从而获得快速的符号分解算法。新算法可以被证明比目前使用的算法需要更少的时间，并且初步实现表明它们在高填充问题上的速度要快一个数量级或更多。求解大型、稀疏、线性方程组的方法是求解科学和工程模型中的偏微分方程的主要方法。因此，这些领域将受益于本项目开发的算法和软件。这些预调节器将专门用于解决声学中的亥姆霍兹问题和计算电磁学中的麦克斯韦方程组。该项目开发的软件将与Argonne国家实验室的PETSc（可移植、可扩展科学计算工具包）包集成，以便广泛传播。

9807172 Pothen Preconditioning is a technique for improving the convergence of iterative methods for solving large, sparse systems of linear equations. The most robust preconditioners available to date are based on computing incomplete factors of the coefficient matrix, i.e., factors that include only a small subset of the nonzero elements created during the factorization. New algorithms for computing incomplete factor preconditioners for unsymmetric and symmetric matrices on serial and parallel computers will be designed and implemented in this project. These algorithms have two phases: in the first symbolic factorization phase, the positions in which the incomplete factors have nonzeros are identified, and data structures for the incomplete factors are set up. In the second numerical factorization phase, these data structures are used to compute the numerical values of the preconditioners in time proportional to the number of arithmetic operations. Without the first symbolic factorization phase, the second phase cannot be implemented efficiently. The new symbolic factorization algorithms rely on a structure theory developed for identifying the positions in which the incomplete factors have nonzero elements. The nonzero elements in the incomplete factors are identified from the path structure of a graph model of the problem. Two graph reduction techniques, transitive reduction and symmetric reduction, are used to reduce the data needed to predict the fill, and thereby to obtain fast symbolic factorization algorithms. The new algorithms can be proven to require less time than the currently used algorithm, and preliminary implementations show that they are faster by an order of magnitude or more in problems with high fill. Methods for solving large, sparse, linear systems of equations are workhorses for solving partial differential equations from scientific and engineering models. Hence these fields will benefit from the algorithms and software developed in this pro ject. These preconditioners will be used to solve specifically the Helmholtz problem in acoustics and Maxwell's equations in computational electromagnetics. The software developed from this project will be integrated with the PETSc (Portable, Extensible Toolkit for Scientific Computing) package from Argonne National Laboratories for wide dissemination.