Our paper concerns domain decomposition algorithms. These algorithms, which are designed for solving the very large linear or nonlinear systems of algebraic equations that, e.g., arise in advanced, large-scale finite element (FE) applications, are designed specifically for the parallel and distributed computing systems, with a substantial number of fast processors, each with relatively large memory.

“The FETI-DP methods are now making inroads in the software packages used on a daily basis by many industrial designers.”

A very desirable feature of iterative substructuring and other domain decomposition algorithms is that they respect the memory hierarchy of modern parallel and distributed computing systems, which is essential for approaching peak floating-point performance.

Of these algorithms, the FETI-DP and BDDC families have proven to be excellent and there is now considerable experience in using them for very difficult and very large finite element simulations. The FETI family of methods have been developed over a long period of time by Charbel Farhat and his associates. Professor Farhat, now at Stanford, is a very prominent computational mechanics scientist with a lot of contacts in industry. The FETI-DP methods are now making inroads in the software packages used on a daily basis by many industrial designers.

The BDDC methods, of more recent vintage, were first developed by Clark Dohrmann of Sandia-Albuquerque. There are very interesting and far from obvious connections between the two families. Essentially, as established by Dohrmann in joint work with Jan Mandel and Radek Tezaur, pairs of algorithms of these kinds have the same spectra; the spectra determines the convergence rates of these algorithms.

One of our contributions in this paper is a greatly simplified proof of this result. We also provide a framework for the analysis of these methods, which already has helped us and others in extending the theory to new problem areas. Our intention in writing this paper was primarily to provide as simple as possible an exposition of these algorithms by basing it on Cholesky factorizations of certain system matrices. We believe that this approach is new and very useful in explaining the basics.

Our approach, using Cholesky factorizations in our description, appears to be new, while most of the results, in fact, were already known. The principal contribution is a new framework for the description of the algorithms and their analysis.

We believe it to be more accessible to a wider community of computational mechanists and applied and computational scientists in general than are most theoretical papers on domain decomposition algorithms.

The second author, Olof B. Widlund, has done research on domain decomposition methods for over 20 years and has had more than a dozen doctoral students, who are working or have worked in the field. A 2005 monograph—"Domain Decomposition Methods," Springer—coauthored with Andrea Toselli, summarizes much of what was known a few years ago.

The first author, Jing Li, is one of these former students. Concerning the work on FETI and BDDC algorithms, these initially posed very serious challenges for numerical analysts. Work on the theory of these algorithms, which began almost ten years ago, has helped reshape the field and has led to the development of a number of new analytic tools.

It is hard to be specific. However, we do believe that work in this research area has had some impact on industrial practice and also contributes to an increase in the productivity of computational engineers and scientists.

Olof B. Widlund
Professor of Mathematics and Computer Science
Courant Institute of Mathematical Sciences
New York University
New York, NY, USA

Jing Li
Assistant Professor
Department of Mathematical Sciences
Kent State University
Kent, OH, USA