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.