The paper describes an equivalence between two methods, called FETI-DP and BDDC, for the solution of very large systems of equations on parallel computers. These methods belong to two classes of methods, called FETI and BDD, which have attracted considerable attention over the last decade. Some connection had been anticipated, but it was not formulated accurately and proved before. The paper also includes new analysis techniques that provide insight into the methods and have already helped to spawn new practical and theoretical developments.

“The paper describes an equivalence between two methods, called FETI-DP and BDDC, for the solution of very large systems of equations on parallel computers.”

The results in the paper were timely: they answered an important question in the theory of iterative substructuring methods, they have attracted attention at conferences, and they were quickly followed by a number of simplifications and extensions by a number of other mathematicians.

The paper describes a synthesis of knowledge that has followed two decades of intense development in the iterative substructuring area by a number of scientists, including the authors.

Iterative substructuring methods solve very large problems, for example, from computational mechanics, by dividing the problem into independent parts (called substructures) and alternating between the solution of local problems on substructures and exchanging information between them. The purpose of iterative substructuring is to take advantage of massively parallel computers to solve bigger problems with higher resolution faster by spreading the work across a number of processors, and thus enable more accurate and faster physical simulations. A better understanding of the different techniques and connections between them shall lead to newer and even more efficient methods in the future.

In the 1990s, one of us, Mandel, proposed a method called BDD, and with Tezaur, then his graduate student, published the first papers on the mathematical analysis of FETI methods. In the early 2000s, the most advanced and sophisticated method of the FETI class, the FETI-DP method, was being used at Sandia National Laboratories for massively parallel simulations.

Dohrmann, an engineer at Sandia, developed a simpler method based on similar ideas. This method performed remarkably well, and he gave a lecture about it at Sandia during Mandel’s visit. Mandel recognized the parallels between Dohrmann’s new method and BDD, coined the new method BDDC (which is the commonly used name today), and started working with Dohrmann on the theory and a formulation of the BDDC method in terms that would be easily understandable to mathematicians in the substructuring community.

This paper started as an attempt to provide a common theory for the FETI-DP and BDDC methods and to get a fair comparison of their practical performance. For this reason, we have built codes for both methods from completely identical basic components. This resulted in tantalizingly almost identical iteration counts for a wide range of problems.

To see what was going on, we have tried to compute the spectra of the methods numerically—and we have found that they were exactly the same. It took one more year to prove that, with computer testing of various hypotheses guiding every step of the way. The proof in this paper, the first of this kind, was very complicated. It has now been simplified in several important papers by others to almost a textbook level.

Efficient algorithms for physical simulations on massively parallel computers are of strategic importance. Computational modeling is augmenting and to a large part 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. Mathematical understanding of massively parallel algorithms 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.