Scalable Parallel Multilevel Domain Decomposition Methods

Kent State University, Kent OH

Investigators

Abstract

Solving large linear systems of equations is often the most computationally expensive part in many scientific and engineering problems. The design of scalable parallel algorithms for solving large linear systems of equations is one of the most important problems in scientific computing. Among the most effective parallel iterative methods are parallel multigrid methods, multilevel matrix preconditioners, and domain decomposition methods. Domain decomposition methods are ideal for parallel implementation. But none of the current multilevel domain decomposition algorithms has shown convincing parallel scalable experimental results, and in practice the convergence rates often deteriorate with the increase of the number of levels. On the other hand, a uniform convergence rate has been proved, both theoretically and experimentally, for the multigrid V-cycles for solving certain symmetric positive definite problems. But the parallel performance of multigrid V-cycles is much less satisfactory. The main goals in this project are the design and analysis of scalable parallel multilevel domain decomposition methods, and the study of connections between the related parallel multilevel iterative methods. A solid theoretical foundation should be valid for these inherently related multilevel preconditioners. Such a theory will provide a practical guide for the design of scalable parallel multilevel iterative methods. Applications of the proposed algorithms to important scientific and engineering computational problems, e.g., elasticity problems, Stokes/Navier-Stokes problems, elastic structure vibration problems, and acoustic scattering problems, will be studied in this project. These problems are closely connected with many technologies such as aircraft design, sonar, radar, geophysical exploration, medical imaging and nondestructive testing.