Presidential Young Investigator Award: Research in Sparse Matrix Methods

将研究稀疏线性方程组的求解方法，特别是由离散化的椭圆型和抛物型偏微分方程解的方法。这类系统的解决方案通常是科学代码中最昂贵的计算。我们将重点介绍三个主要方面。稀疏线性方程组的迭代解，包括并行技术和非对称系统：不完全因式分解预处理器的“多色”变体在串联结构上表现出比标准预处理器更慢的收敛速度，但通过模型问题的理论和计算研究表明，它们在并行机上更优越。这些方法将在科学应用程序代码中出现的问题上进行测试，在这些应用程序代码中，不确定它们是否可靠。我们将研究替代方法，如块排序方法，这种方法的并行实现效率较低，但在二维问题上表现出更快的收敛速度。此外，新的分析和实验结果表明，基于部分消元和“线”预条件的非对称线性方程组的迭代方法对于求解对流扩散方程是非常有效的。将对这些技术进行进一步研究，包括在并行体系结构上的实现。三维问题的数值方法：由三维椭圆问题产生的线性系统目前还不能以合理的成本求解。并行和/或更快收敛方法的成功开发将扩大可解问题的领域，但必须特别注意与三维相关的具体问题。我们将考察两个想法：三维多色方案和“平面”预处理器(这将推广直线方法)。后一种想法建立在有效的并行二维解算器的基础上。有限元方法的并行实现：有限元方法包括一种广泛使用的椭圆问题的求解技术，该技术为并行计算带来了特殊的困难，包括不规则网格和三维问题的存在。高阶有限元方法在均匀网格上并行求解二维问题具有一定的优势。从这一初步观察出发，我们将研究不规则网格和三维有限元模型的并行求解问题。将考虑的两种方法是局部直接求解和全局迭代求解相结合的方法，以及使用分层基函数的并行求解方法。

Methods for solving sparse linear systems of equations, especially of the type arising from discretized elliptic and parabolic partial differential equations, will be studied. The solution of such systems is often the most costly computation in scientific codes. Three general areas will be emphasized. Iterative solution of sparse linear systems of equations, including parallel techniques and nonsymmetric systems: "Multicolor" variants of incomplete factorization preconditioners display slower convergence than standard preconditioners on serial architectures, but theoretical and computational studies with model problems show them to be superior on parallel machines. These methods will be tested on problems arising in scientific application codes, where it is not certain that they will be robust. Alternatives, such as block ordering methods which have less efficient parallel implementations but display faster convergence on two-dimensional problems, will be examined. In addition, new analytic and experimental results suggest that iterative methods for nonsymmetric linear systems based on partial elimination and "line" preconditioners are very effective for solving the convection-diffusion equation. Further studies of these techniques will be made, including implementation on parallel architectures. Numerical methods for three-dimensional problems: Linear systems arising from three-dimensional elliptic problems cannot be solved at reasonable cost at the present time. Successful development of parallel and/or faster converging methods will expand the domain of solvable problems, but special attention must be paid to the specific issues associated with three-dimensionality. Two ideas will be examined: three-dimensional multicolor schemes, and "plane" preconditioners (which would generalize line methods). The latter idea build upon effective parallel two- dimensional solvers. Parallel implementation of finite element methods: Finite element methods comprise a widely used solution technique for elliptic problems that present special difficulties for parallel computing, including the presence of irregular grids and three- dimensional problems. High order finite element methods appear to offer some advantages for parallel solution of two-dimensional problems on uniform grids. Starting from this preliminary observation, the parallel solution of finite element models on irregular grids and in three dimensions will be studied. Two methodologies that will be considered are the combination of local direct solution with global iterative solution methods, and parallel solution using hierarchical basis functions.