In an elliptic partial differential equation, the solution is non-local: its value at any point depends on the right-hand-side at any other point. Such equations arise in fluid and solid mechanics. In addition, real problems have often irregular (quickly varying) geometry or material properties in some places, and, after discretization, result in very large problems, particularly in 3D; hundreds of millions of degrees of freedom are not so unusual any more. Because of the size of the problem, the use of distributed massively parallel computers is mandatory, both for processor power and for the memory space. Iterative substructuring methods are a class of domain decomposition methods devised to use massively parallel computers for such problems in spite of the non-locality of the solution. This project will start from one of the most advanced methods of this class, the BDDC method, which requires algebraic information only (the matrices of the substructures). Substructuring method are scalable with the number of processors up to some point; after that, the complexity of direct solution of the coarse problem, needed to coordinate the solution between the processors, will dominate. In this project, the method itself is applied recursively and results in a multilevel method much like in multigrid, except naturally adapted to parallel processing from the outset. Robust treatment of irregular problems will be made possible by the use of adaptive techniques, which focus computational work in the places where it is needed.
Efficient algorithms for physical simulations on massively parallel computers are of strategic importance. Computational modeling is augmenting and to a large extent substituting expensive and possibly dangerous or infeasible physical experiments in engineering. Significant growth of computational power is now achieved by using more processors in parallel. This project will develop new methods to use a large number of processors efficiently. It will also contribute to the mathematical understanding of massively parallel algorithms, which is essential because it allows one to guarantee that they will work on more processors and on other problems than they can currently be tested on.
