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.