BDDC Deluxe Domain Decomposition Algorithms

Olof B. Widlund
Courant Institute of Mathematical Sciences
251 Mercer Street
New York, NY 10012, USA


When designing domain decomposition algorithms, approximate inverses, also known as preconditioners, are constructed for very large matrices by using solvers for many smaller linear systems often obtained from much smaller instances of the given problem. The problems considered often arise in continuum mechanics, e.g., in linear elasticity or electro-magnetics. The preconditioners are used in Krylov space iterations. In addition, for fast convergence with a rate of convergence independent of the number of local problems, a coarse component of the preconditioner will be needed.

The BDDC algorithms, first developed by Clark Dohrmann, have proven to be very successful domain decomposition algorithms for a variety of elliptic problems. For any particular application, the success of such an algorithm depends on the choice of a set of primal constraints and the choice of an averaging operator, which is used to restore the continuity of certain intermediate vectors in each iteration.

In the deluxe version, a new averaging procedure is used; it was first developed in joint work with Dohrmann on H(curl) problems. A theory will be outlined and a variety of successful applications will be discussed in particular to problems formulated in H(div) and H(curl). This work has been developed jointly with Clark Dohrmann, Duk-Soon Oh, and Stefano Zampini. Lately, there has been an important development of adaptive algorithms for the choice of the primal constraints.

In recent joint work with Stefano Zampini, PETSc programs have been developed for massively parallel computing systems. This work involves the adaptive selection of the primal constraints and exploring three-level BDDC algorithms for problems with more than a billion degrees of freedom.