Linear and Nonlinear Multigrid Methods on Cache Based Parallel and Serial Computers with Applications

道格拉斯9707040 调查员开始研究多重网格方法的计算机的性能是高度依赖于该高速缓存利用率。 该项目包括算法开发和代码实现。 对于二维结构化问题，可以设计有效的新算法。 对于二维或三维的一般非结构化问题，这要困难得多，需要完全不同的方法。 计划采取两种办法。 一种是基于局部化图连接的稀疏矩阵与网格为基础的问题。 第二种是基于一个软件工具，它在运行时重新排序计算，以有效地使用该高速缓存。 此外，研究人员开发新的非线性多重网格算法，可以鲁棒地解决真实的应用。 一种新的方法是开发粗化自适应细化网格的问题，目前的算法无法收敛。 复杂科学和工程问题的真实的世界模拟，如气候，海洋，石油储层和污染物跟踪建模，需要大量的计算机时间。 今天的计算机有独立的内存模块，运行速度相差很大。 通常，程序以计算机中最慢的内存的速度运行。 研究人员研究如何使用更快的内存模块，而不是最慢的内存，以使求解器更快地运行复杂的问题。

Douglas 9707040 The investigator begins a study of multigrid methods for computers whose performance is highly dependent on the cache utilization. The project includes both algorithm development and realizations in code. For structured problems in two dimensions, effective new algorithms can be devised. For general, unstructured problems in either two or three dimensions, this is much harder and requires a completely different approach. Two approaches are planned. One is based on localizing graph connections of a sparse matrix associated with the grid based problem. A second is based on a software tool that re-orders the computation at run time to use the cache efficiently. In addition, the investigator develops new nonlinear multigrid algorithms that can robustly solve real applications. A new methodology is developed to coarsen adaptively refined grids for problems in which current algorithms fail to converge. Real world simulations of complex science and engineering problems like climate, ocean, petroleum reservoir, and pollutant tracking modeling require enormous amounts of computer time. Computers today have separate memory modules that run at vastly different speeds. Normally, programs run at the speed of the slowest memory in a computer. The investigator examines how to use the faster memory modules instead of the slowest memory for the solvers needed to run complex problems much faster.