Working to Solve Large-Scale Linear Systems
June 17, 2000Robert D. Falgout and Jinchao Xu
Researchers have been actively investigating the multigrid method for many years but are still faced with an important question: How can it be made more practical in applications? This question was discussed in detail at a workshop sponsored by CASC, the Center for Applied Scientific Computing at Lawrence Livermore National Laboratory.
The three-day (June 23-25, 1999) Oberwolfach-style workshop was held in the beautiful Wente Vineyards of Livermore, California. The informal setting, just a few minutes' drive from CASC's office, was ideal for the size and format of the workshop. The approximately 40 invited participants (mostly from the United States, with a few from Europe) joined in lively discussions during and after the workshop sessions.
This workshop was one of many research outreach activities sponsored by CASC and the Institute for Scientific Computing Research, both part of LLNL.
Under the leadership of Steven Ashby, CASC has grown from 12 scientists in 1996 to more than 80 at present. CASC conducts collaborative scientific investigations that require the power of high-performance computers and the efficiency of modern computational methods. Its research and development activities are applications-driven, with the focus on LLNL programmatic objectives that require advanced computational technologies. CASC's core competencies include high-performance computing, computational physics, numerical mathematics, and computer science.
The workshop was organized by participants in CASC's Scalable Linear Solvers project. The aim of the project is the development of scalable algorithms and software for solving large, sparse linear systems of equations on parallel computers. A major research focus is multigrid, one of the most powerful methodologies for solving large-scale systems. Ashby and his colleagues at CASC have placed the multigrid method at the center of their algorithmic research. Their work, by accelerating and broadening the application of the multigrid method, can be expected to have a substantial impact on scientific simulation capabilities.
The multigrid method has been shown to be extremely efficient, both in theory and in practice. Traditionally, however, it has been somewhat problem-dependent and difficult to use, particularly in a software library setting. The desire in recent years to make the method more accessible to general users has led to a resurgence---algebraic multigrid methods. Like classical multigrid methods, algebraic multigrid methods have optimal computational complexities for many applications; they are, however, much easier to use (as are other algebraic algorithms, such as Gaussian elimination). These algorithms, the current focus for a large group of CASC researchers (including Andy Cleary, Robert Falgout, Van Henson, Jim Jones, Barry Lee, Beth Ong, Charles Tong, Panayot Vassilevski, and Ulrike Yang), were also the major topic of the workshop. The group at CASC is involved in several collaborations, including a close partnership with three researchers at the University of Colorado, Boulder---Tom Manteuffel, Steve McCormick, and John Ruge---who attended the workshop. As most of the participants are very active researchers in the subject, the atmosphere of the workshop was lively and down to earth.
Each morning and afternoon session was devoted to a special topic. The sessions opened with a few short presentations to enumerate the issues; lively discussions followed. Domain decomposition techniques, with the emphasis on methods for non-matching grids, were the topic of the first session, which was organized by Raytcho Lazarov of Texas A&M. Of the three sessions devoted to algebraic multigrid methods, two (organized by Jim Jones and Panayot Vassilevski, both of LLNL) considered recent algorithmic advances for improving robustness; the session organized by Van Henson (also of LLNL) covered the important and difficult problem of developing parallel algebraic multigrid algorithms.
A session organized by Robert Falgout discussed issues related to the implementation and design of multigrid methods for today's high-performance computers, where parallelism and cache performance play a dominant role. Finally, Edmond Chow of LLNL organized a session on multilevel incomplete factorization (ILU), which has much in common with algebraic multigrid but brings a different algorithmic perspective to the table.
After-lunch group discussions were another major workshop activity. During the lunch breaks, participants had the choice of staying together in small work groups or joining an organized discussion. Most participants chose to join the organized sessions, which, as intended, turned out to be informal and provocative.
Jinchao Xu, of Penn State, organized the first such discussion. The question considered---Which problems can and cannot be solved with multigrid, and why is multigrid not commonly used in practice?---generated much controversy. The debate began with the question itself, as some participants agreed that multigrid is not commonly used in practice and others disagreed. Using his laptop, Xu constructed a Web page with a list of important problems, and solicited input on those for which multigrid is an effective solver. Again, much debate ensued. Although agreement was not quite reached on the details, an overall consensus emerged that multigrid methods can be effective solvers for a remarkably wide range of problems. This discussion carried over to the next lunch.
Participants in the second after-lunch discussion, which was organized by Tom Manteuffel, considered the similarities and differences between multigrid, domain decomposition, and aggregation methods. The question for this session was, Is it possible to establish a common framework into which all these methods fit? Manteuffel outlined a framework in which methods are viewed as "approximate" Schur complement methods. This idea also generated some healthy discussion, and a relevant early framework based on space decomposition and subspace correction emerged.
On the basis of the productivity of the workshop and the enthusiasm of the participants, CASC plans to sponsor three or four workshops a year on subjects related to its core mission. Topics planned for 2000 include scalable nonlinear solvers, transport methods, and mining of large scientific data sets.
Acknowledgment
This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract W-7405-Eng-48.
Robert Falgout is a researcher at CASC, and the former project leader for the Scalable Linear Solver's Project. He is currently head of the numerical algorithms section, which encompasses work on methods for solving linear, nonlinear, and differential equations. Jinchao Xu is professor of mathematics and co-director of the Center for Computational Mathematics and Applications at Pennsylvania State University. He works on numerical methods for partial differential equations and especially on multigrid methods.
