Presidential Young Investigator Award: Research in Sparse Matrix Methods

解稀疏线性方程组的方法， 特别是由离散椭圆和 抛物型偏微分方程，将研究。 的 这种系统的解决方案往往是最昂贵的计算， 科学密码 将强调三个一般领域。 稀疏线性方程组的迭代解， 包括并行技术和非对称系统： 不完全因式分解预条件子的“多色”变体 显示比标准预处理器更慢的收敛 串行架构，但理论和计算研究 与模型的问题表明，他们是上级并行 机械. 这些方法将在以下方面出现的问题上得到检验： 科学应用程序代码，其中不确定它们是否 将是强大的。 替代方法，如块排序方法 其具有效率较低的并行实现，但显示 更快的收敛二维问题，将被检查。 此外，新的分析和实验结果表明， 非对称线性方程组的迭代方法 部分消除和“行”预条件是非常有效的 来解对流扩散方程。 进一步研究 这些技术将被提出，包括实施 并行架构 三维问题的数值方法：线性系统 由三维椭圆问题引起的问题无法解决 以合理的成本，目前。 成功发展 并行和/或更快的收敛方法将扩展 域的可解决的问题，但必须特别注意 与三维相关的具体问题。 两 想法将被检查：三维的可重构方案， 和“平面”预条件子（将线 方法）。 后一个想法建立在有效的平行两个- 维度求解器 有限元方法的并行实现：Finite 单元法包括广泛使用的求解技术， 椭圆问题，目前特别困难的并行 计算，包括不规则网格的存在和三个- 尺寸问题 出现了高阶有限元方法 为二维问题的并行求解提供了一些优势 均匀网格上的问题。 从这个初步的 观察，有限元模型的并行解决方案， 将研究不规则网格和三维空间。 两 将考虑的方法是以下方面的组合 局部直接解与全局迭代解方法，以及 使用分层基函数的并行解决方案。

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.