The Balancing Domain Decomposition by Constraints (BDDC) method by Dohrmann (2003) is the most advanced method from the Balancing family of iterative substructuring methods by Mandel (1993) for the solution of large systems of linear algebraic equations arising from discretizations of elliptic boundary value problems. The method is closely related to FETI-DP by Farhat et al. (2001), and it is the same as other two methods proposed independently by Fragakis and Papadrakakis (2003) and by Cros (2003).

Because these are two-level methods, solving the coarse problem exactly becomes a bottleneck when the number of substructures becomes large. The coarse problem in BDDC has the same structure as the original problem, so it is straightforward to apply the BDDC method recursively to solve the coarse problem only approximately. In the first part we formulate a new family of abstract Multispace BDDC methods and give a condition number bound from the abstract additive Schwarz preconditioning theory. The Multilevel BDDC is then treated as a special case of the Multispace BDDC, and it is also shown that the original, two-level, BDDC can be written as a multispace method.

In the second part we propose a method for adaptive selection of the coarse space for the original two-level BDDC method. The method works by adding coarse degrees of freedom constructed from eigenvectors associated with intersections of selected pairs of adjacent substructures. It is assumed that the starting coarse degrees of freedom are already sufficient to prevent relative rigid body motions in any selected pair of adjacent substructures. A heuristic indicator of the condition number is developed and a minimal number of coarse degrees of freedom is added to decrease the indicator under a given threshold.

In the third part we combine the advantages of both approaches to propose a new method called Adaptive - Multilevel BDDC that preserves both parallel scalability with increasing number of subdomains and very good convergence properties. Performance of the method is illustrated by several numerical examples in two and three spatial dimensions.