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

点击翻译按钮获取中文摘要

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.