This project will investigate efficient multigrid (MG) and domain decomposition (DD) algorithms for elliptic and non-elliptic problems on arbitrary unstructured meshes, which are suitable for distributed and shared memory parallel computing architectures. Three aspects of DD and MG will be emphasized in this work: (1) Performance of various DD and MG algorithms on parallel computers with particular attention paid to communication and cache memory latency. (2) Design of optimized DD and MG "gray box" libraries for elliptic and advection dominated problems, which exploit optional information supplied by the user. (3) Theoretical analysis and practical design of DD and MG algorithm appropriate for advection dominated problems. Particular emphasis will be placed on DD and MG algorithms for solving the discretization matrices arising from a variety of large scale scientific computing problems, such as computational fluid dynamics (CFD) for advection dominated problems, image processing, photolithography, and the modeling of microchip performance and fabrication. The non-elliptic behavior of these practical problems renders the known multigrid and decomposition theory inadequate and serves to motivate a balanced effort consisting of algorithmic development, theoretical analysis, and practical application.
