Solution Methods for Large-scale Nonlinear Problems: An Evolving Research Area

April 9, 2001


Workshop organizing committee chair Carol Woodward (LLNL) and Dmitri Mavriplis (ICASE). (Photographs produced at the University of California Lawrence Livermore National Laboratory, for the U.S. Department of Energy.)
Homer Walker and Carol S. Woodward

The ability to solve large-scale, fully coupled multiphysics models is vital to progress in computational science. Efficient computation of solutions to the mathematical equations underlying these models requires effective numerical algorithms for solving very large systems of coupled nonlinear equations. Particularly needed are scalable algorithms that can exploit the power of massively parallel computers. Several successful approaches to the construction of such algorithms have emerged in recent years, but the need to treat more complex models and more problematic physics continues to drive research.

The Workshop on Solution Methods for Large-Scale Nonlinear Problems, held July 26-28, 2000, at the Four Points Hotel in Pleasanton, California, brought together many of the most active researchers on both the algorithmic and the applications sides. The workshop was hosted by the Center for Applied Scientific Computing and the Institute for Tera-scale Simulation at Lawrence Livermore National Laboratory. Major themes included Newton-Krylov methods, nonlinear multigrid methods, preconditioning techniques, operator-split and fully implicit schemes, and large-scale sensitivity analysis and optimization. Major application areas included general fluid dynamics, combustion and other reacting flows, porous media flows, radiation diffusion problems, and design optimization.

The workshop was a distant follow-on to similar workshops on large-scale nonlinear problems held at Utah State University in 1989 and 1995. In the spirit of the earlier workshops, liberal break times in the schedule of talks and discussion sessions encouraged informal interactions among participants. Workshop attendees came from academia (25), government laboratories (21), and industry (1) and were mainly from the United States. Each of the three workshop days emphasized particular subject areas, with several talks followed by a moderated discussion of selected issues.

Raytcho Lazarov (Texas A&M), with Zhiqiang Cai (Purdue) and SIAM president Tom Manteuffel (University of Colorado).

Day 1: Newton-Krylov methods and nonlinear multigrid. The day began with two talks on techniques for enhancing the convergence of Newton-Krylov methods---a novel nonlinear preconditioning method based on Schwarz domain decomposition, and approaches based on the singular value decomposition. Later speakers considered applications of Newton-Krylov and nonlinear multigrid methods to combustion, groundwater flow, and radiation diffusion problems. The final speaker addressed the benefits of automatic differentiation over finite differ-ences in computing matrix-vector products used in Newton-Krylov methods.

Concluding the day, Van Henson and Jim Jones moderated a discussion of the differences in performance between Newton's method and nonlinear multigrid (also called the full approximation scheme, or FAS) on various problems. The basic iteration scheme of FAS and the full multigrid version were considered, as was the use of multigrid to solve Jacobian systems for each Newton iteration (Newton-multigrid). The consensus among experienced users of FAS: FAS requires less memory and has a larger basin of attraction than Newton-multigrid methods, but it is harder to get FAS to work on new problems.

Day 2: Applications and problem formulation. Participants heard talks on nonlinear solvers for reacting flows, multiphase groundwater flow, chemical reactions, radiation diffusion problems, powder consolidation, and Einstein's equations of general relativity. Solution approaches included operator-splitting techniques and fully implicit formulations, domain decomposition, and pseudotransient continuation.

Peter Brown and Carol Woodward moderated the afternoon discussion on the pros and cons of operator-splitting for coupled systems of nonlinear equations. Participants generally agreed that the holy grail is a fully implicit solve of all problem physics, although simulation technology has not evolved enough to handle all the necessary complexity. Significant progress has been made, however, in the development of solvers and methods for these fully implicit formulations.

Day 3: Algorithmic issues, sensitivity analysis, and optimization. Speakers described nonlinear elimination methods, performance "stress points" of parallel implicit solvers, techniques for finding solution sensitivities to problem parameters, and formulation and solution techniques for nonlinear PDE-constrained optimization. Applications included aerodynamic analysis and design optimization as well as optimal control of Navier-Stokes flows.

Steven Lee and David Keyes moderated the afternoon discussion of the role of sensitivity analysis and optimization in scientific computing. Participants identified aerodynamic and automotive design as fields in which sensitivity analysis and optimization are now used routinely; with effective automatic differentiation tools now being developed, more fields can be expected to use these techniques in the future.

Workshop discussion sessions included sensitivity analysis and optimization in scientific computing, moderated by Steven Lee (left) and David Keyes, and a performance comparison of Newton's method and nonlinear multigrid, moderated by Jim Jones (right) and Van Henson.

From the discussion and presentations, it became clear that the field of solution methods for large-scale nonlinear problems has evolved considerably in the five years since the last workshop. Newton-Krylov and Newton-Krylov-Schwarz methods, already important topics at the 1995 meeting, were much more prominent at the recent workshop. This change reflects improvements in the Newton-Krylov family of methods and the current widespread acceptance of these techniques as the methods of choice in many difficult applications. Similarly, fully implicit and fully coupled problem formulations were much more in evidence, as a result of advances in solution technology that have made fully coupled formulations feasible in previously intractable applications. Such advances have also made possible more effective treatment of difficult PDE-related optimization problems, such as design optimization. Accordingly, the optimization talks focused more on PDE-related applications and less on general optimization algorithms.

A notable new feature of the workshop was the emphasis on nonlinear multigrid, which did not appear at all in the previous workshop. Although not new, the method has come into wide use only recently, as advances in the solution of heterogeneous problems have made it more applicable to problems of interest. Another area not previously featured is sensitivity analysis. Even though the importance of this area has been recognized for some time, the recent introduction of special Newton-Krylov techniques has resulted in much more effective methods for large-scale problems.

Many of the workshop topics seem likely to lead to interesting future research. Nonlinear preconditioning, which generated much discussion among participants, shows considerable potential for resolving well-known stagnation problems associated with Newton's method. Nonlinear multigrid, though not as new, also appears to have much unexploited potential, not only as a nonlinear solver but perhaps as a nonlinear preconditioner as well. Similarly, sensitivity analysis and design optimization seem to be likely candidates for further attention as algorithms are improved and more challenging applications are addressed.

Another area, the use of operator-splitting techniques for preconditioning fully implicit formulations, should lead to more accurate simulations with fully coupled approaches. This technique will also allow the reuse of current methods and codes to solve these preconditioning systems. Nonlinear elimination, seen to be useful in treating shocks in compressible flow applications, also appears worthy of further attention. Finally, automatic differentiation seems at last to have emerged as a practical tool that should see many applications in Newton-Krylov methods. Automatic differentiation has the potential to alleviate the algorithmic slowdowns and failures sometimes encountered when finite-difference techniques are used in approximating matrix-vector products.

A special issue of the journal Numerical Linear Algebra with Applications will feature papers from this workshop. The issue will be co-edited by workshop organizing committee chair Carol Woodward and journal editor Panayot Vassilevski. On the basis of the enthusiasm of workshop participants, LLNL's Center for Applied Scientific Computing and Institute for Terascale Simulation will sponsor more workshops in this series in coming years.

Acknowledgments
This work was performed under the auspices of the U.S. Department of Energy by the University of California Lawrence Livermore National Laboratory under contract W-7405-Eng-48. The first author was also supported in part by subcontract B341493, University of California Lawrence Livermore National Laboratory, and NSF grant DMS-9727128. Neither LLNL nor the U.S. government makes any warranty, express or implied, or assumes any legal liability for the accuracy, completeness, or usefulness of any information, product, or process disclosed in this article.

Homer Walker is a professor and head of the Mathematical Sciences Department at Worcester Polytechnic Institute. His main research interests are iterative methods for large-scale linear and nonlinear systems, especially Krylov subspace methods and Newton-Krylov methods. Carol Woodward is a researcher at CASC and the project leader for the Nonlinear Solvers and Differential Equations Project. Her research interests include nonlinear solvers, especially Newton-Krylov and FAS methods, nonlinear diffusion equations, and parallel computing.


Donate · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube linkedin google+