×

Composing scalable nonlinear algebraic solvers. (English) Zbl 1336.65030

Summary: Most efficient linear solvers use composable algorithmic components, with the most common model being the combination of a Krylov accelerator and one or more preconditioners. A similar set of concepts may be used for nonlinear algebraic systems, where nonlinear composition of different nonlinear solvers may significantly improve the time to solution. We describe the basic concepts of nonlinear composition and preconditioning and present a number of solvers applicable to nonlinear partial differential equations. We have developed a software framework in order to easily explore the possible combinations of solvers. We show that the performance gains from using composed solvers can be substantial compared with gains from standard Newton-Krylov methods.

MSC:

65F08 Preconditioners for iterative methods
65Y05 Parallel numerical computation
65Y20 Complexity and performance of numerical algorithms
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Advanced Micro Devices, {\it AMD Opteron 6200 Series Quick Reference Guide}, 2012.
[2] D. G. Anderson, {\it Iterative procedures for nonlinear integral equations}, J. Assoc. Comput. Mach., 12 (1965), pp. 547-560. · Zbl 0149.11503
[3] S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, K. Rupp, B. F. Smith, and H. Zhang, {\it PETSc Users Manual}, Tech. Rep. ANL-95/11, Revision 3.5, Argonne National Laboratory, 2014.
[4] P. Birken and A. Jameson, {\it On nonlinear preconditioners in Newton-Krylov methods for unsteady flows}, Internat. J. Numer. Methods Fluids, 62 (2010), pp. 565-573. · Zbl 1423.76330
[5] J. H. Bramble, {\it Multigrid Methods}, Longman Scientific and Technical, Essex, UK, 1993.
[6] A. Brandt, {\it Multi-level adaptive solutions to boundary-value problems}, Math. Comp., 31 (1977), pp. 333-390. · Zbl 0373.65054
[7] A. Brandt, {\it Multigrid Techniques: \(1984\) Guide with Applications for Fluid Dynamics}, Tech. Rep. GMD-Studien Nr. 85, Gesellschaft für Mathematik und Dataenverarbeitung, Bonn, Germany, 1984. · Zbl 0581.76033
[8] A. Brandt and D. Ron, {\it Multigrid solvers and multilevel optimization strategies}, in Multilevel Optimization and VLSICAD, Kluwer Academic, Norwell, MA, 2003, pp. 1-69. · Zbl 1046.65043
[9] W. L. Briggs, V. E. Henson, and S. F. McCormick, {\it A Multigrid Tutorial}, 2nd ed., SIAM, Philadelphia, 2000. · Zbl 0958.65128
[10] J. Brown and P. Brune, {\it Low-rank quasi-Newton updates for robust Jacobian lagging in Newton-type methods}, in Proceedings of the International Conference on Mathematics and Computational Methods Applied to Nuclear Science and Engineering, ANS, La Grange Park, IL, 2013, pp. 2554-2565.
[11] P. N. Brown and A. C. Hindmarsh, {\it Matrix-free methods for stiff systems of ODEs}, SIAM J. Numer. Anal., 23 (1986), pp. 610-638. · Zbl 0615.65078
[12] P. N. Brown and Y. Saad, {\it Convergence theory of nonlinear Newton-Krylov algorithms}, SIAM J. Optim., 4 (1994), pp. 297-330. · Zbl 0814.65048
[13] C. G. Broyden, {\it A class of methods for solving nonlinear simultaneous equations}, Math. Comp., 19 (1965), pp. 577-593. · Zbl 0131.13905
[14] R. Byrd, J. Nocedal, and R. Schnabel, {\it Representations of quasi-Newton matrices and their use in limited memory methods}, Math. Programming, 63 (1994), pp. 129-156. · Zbl 0809.90116
[15] X.-C. Cai, {\it Nonlinear overlapping domain decomposition methods}, in Domain Decomposition Methods in Science and Engineering XVIII, Lecture Notes in Comput. Sci. 70, Springer, Berlin, 2009, pp. 217-224. · Zbl 1183.65053
[16] X.-C. Cai and D. E. Keyes, {\it Nonlinearly preconditioned inexact Newton algorithms}, SIAM J. Sci. Comput., 24 (2002), pp. 183-200. · Zbl 1015.65058
[17] X.-C. Cai and X. Li, {\it Inexact Newton methods with restricted additive Schwarz based nonlinear elimination for problems with high local nonlinearity}, SIAM J. Sci. Comput., 33 (2011), pp. 746-762. · Zbl 1227.65045
[18] N. N. Carlson and K. Miller, {\it Design and application of a gradient-weighted moving finite element code I: In one dimension}, SIAM J. Sci. Comput., 19 (1998), pp. 728-765. · Zbl 0911.65087
[19] T. F. Chan and K. R. Jackson, {\it Nonlinearly preconditioned Krylov subspace methods for discrete Newton algorithms}, SIAM J. Sci. Statist. Comput., 5 (1984), pp. 533-542. · Zbl 0574.65043
[20] P. Cresta, O. Allix, C. Rey, and S. Guinard, {\it Nonlinear localization strategies for domain decomposition methods: Application to post-buckling analyses}, Comput. Methods Appl. Mech. Engrg., 196 (2007), pp. 1436-1446. · Zbl 1173.74408
[21] Y. H. Dai and Y. Yuan, {\it A nonlinear conjugate gradient method with a strong global convergence property}, SIAM J. Optim., 10 (1999), pp. 177-182. · Zbl 0957.65061
[22] H. De Sterck, {\it Steepest descent preconditioning for nonlinear GMRES optimization}, Numer. Linear Algebra Appl., 20 (2013), pp. 453-471. · Zbl 1313.65137
[23] R. S. Dembo, S. C. Eisenstat, and T. Steihaug, {\it Inexact Newton methods}, SIAM J. Numer. Anal., 19 (1982), pp. 400-408. · Zbl 0478.65030
[24] J. E. Dennis, Jr. and J. J. Moré, {\it Quasi-Newton methods, motivation and theory}, SIAM Rev., 19 (1977), pp. 46-89. · Zbl 0356.65041
[25] J. E. Dennis, Jr. and R. B. Schnabel, {\it Numerical Methods for Unconstrained Optimization and Nonlinear Equations}, Prentice-Hall, Englewood Cliffs, NJ, 1983.
[26] P. Deuflhard, R. Freund, and A. Walter, {\it Fast secant methods for the iterative solution of large nonsymmetric linear systems}, IMPACT Comput. Sci. Engrg., 2 (1990), pp. 244-276. · Zbl 0729.65027
[27] S. C. Eisenstat and H. F. Walker, {\it Globally convergent inexact Newton methods}, SIAM J. Optim., 4 (1994), pp. 393-422. · Zbl 0814.65049
[28] V. Eyert, {\it A comparative study on methods for convergence acceleration of iterative vector sequences}, J. Comput. Phys., 124 (1996), pp. 271-285. · Zbl 0851.65003
[29] H.-r. Fang and Y. Saad, {\it Two classes of multisecant methods for nonlinear acceleration}, Numer. Linear Algebra Appl., 16 (2009), pp. 197-221. · Zbl 1224.65134
[30] R. Fletcher, {\it Practical Methods of Optimization, Volume} 1, Wiley, New York, 1987. · Zbl 0905.65002
[31] R. Fletcher and C. M. Reeves, {\it Function minimization by conjugate gradients}, Comput. J., 7 (1964), pp. 149-154. · Zbl 0132.11701
[32] A. A. Goldstein, {\it On steepest descent}, J. Soc. Indust. Appl. Math. Ser. A Control, 3 (1965), pp. 147-151. · Zbl 0221.65094
[33] W. Hackbusch, {\it Comparison of different multi-grid variants for nonlinear equations}, Z. Angew. Math. Mech., 72 (1992), pp. 148-151. · Zbl 0766.65044
[34] V. E. Henson, {\it Multigrid methods for nonlinear problems: An overview}, Proc. SPIE, 5016 (2003), pp. 36-48.
[35] M. R. Hestenes and E. Steifel, {\it Methods of conjugate gradients for solving linear systems}, J. Research Nat. Bur. Standards, 49 (1952), pp. 409-436. · Zbl 0048.09901
[36] J. D. Hunter, {\it Matplotlib: A \(2\) d graphics environment}, Comput. Sci. Engrg., 9 (2007), pp. 90-95.
[37] F.-N. Hwang and X.-C. Cai, {\it A parallel nonlinear additive Schwarz preconditioned inexact Newton algorithm for incompressible Navier-Stokes equations}, J. Comput. Phys., 204 (2005), pp. 666-691. · Zbl 1267.76083
[38] C. T. Kelley, {\it Iterative Methods for Linear and Nonlinear Equations}, SIAM, Philadelphia, 1995. · Zbl 0832.65046
[39] C. T. Kelley and D. E. Keyes, {\it Convergence analysis of pseudo-transient continuation}, SIAM J. Numer. Anal., 35 (1998), pp. 508-523. · Zbl 0911.65080
[40] H. Klie and M. F. Wheeler, {\it Nonlinear Krylov-Secant Solvers}, Tech. Rep., Department of Mathematics and Institute of Computational Engineering and Sciences, University of Texas at Austin, 2006.
[41] D. A. Knoll and P. R. McHugh, {\it Enhanced nonlinear iterative techniques applied to a nonequilibrium plasma flow}, SIAM J. Sci. Comput., 19 (1998), pp. 291-301. · Zbl 0913.76067
[42] D. A. Knoll and D. E. Keyes, {\it Jacobian-free Newton-Krylov methods: A survey of approaches and applications}, J. Comput. Phys., 193 (2004), pp. 357-397. · Zbl 1036.65045
[43] P. Ladevèze, J.-C. Passieux, and D. Néron, {\it The LATIN multiscale computational method and the proper generalized decomposition}, Comput. Methods Appl. Mech. Engrg., 199 (2010), pp. 1287-1296. · Zbl 1227.74111
[44] P. Ladevèze and J. Simmonds, {\it Nonlinear Computational Structural Mechanics: New Approaches and Non-incremental Methods of Calculation}, Mechanical Engineering Series, Springer, New York, 1999.
[45] P. J. Lanzkron, D. J. Rose, and J. T. Wilkes, {\it An analysis of approximate nonlinear elimination}, SIAM J. Sci. Comput., 17 (1996), pp. 538-559. · Zbl 0855.65054
[46] D. C. Liu and J. Nocedal, {\it On the limited memory BFGS method for large scale optimization}, Math. Programming, 45 (1989), pp. 503-528. · Zbl 0696.90048
[47] P. A. Lott, H. F. Walker, C. S. Woodward, and U. M. Yang, {\it An accelerated Picard method for nonlinear systems related to variably saturated flow}, Adv. Water Res., 38 (2012), pp. 92-101.
[48] J. M. Martínez, {\it SOR-secant methods}, SIAM J. Numer. Anal., 31 (1994), pp. 217-226. · Zbl 0802.65066
[49] H. Matthies and G. Strang, {\it The solution of nonlinear finite element equations}, Internat. J. Numer. Methods Engrg., 14 (1979), pp. 1613-1626. · Zbl 0419.65070
[50] S. G. Nash, {\it A multigrid approach to discretized optimization problems}, Optim. Methods Softw., 14 (2000), pp. 99-116. · Zbl 0988.90040
[51] J. Nocedal, {\it Updating quasi-Newton matrices with limited storage}, Math. Comp., 35 (1980), pp. 773-782. · Zbl 0464.65037
[52] J. Nocedal and S. J. Wright, {\it Numerical Optimization}, Springer, New York, 1999. · Zbl 0930.65067
[53] C. W. Oosterlee and T. Washio, {\it Krylov subspace acceleration of nonlinear multigrid with application to recirculating flow}, SIAM J. Sci. Comput., 21 (2000), pp. 1670-1690. · Zbl 0968.76061
[54] E. Polak and G. Ribiere, {\it Note sur la convergence de méthodes de directions conjuguées}, Rev. Française Informat. Recherche Opérationnelle, 3 (1969), pp. 35-43. · Zbl 0174.48001
[55] P. Pulay, {\it Convergence acceleration of iterative sequences: The case of SCF iteration}, Chem. Phys. Lett., 73 (1980), pp. 393-398.
[56] A. Quarteroni and A. Valli, {\it Domain Decomposition Methods for Partial Differential Equations}, Oxford Science Publications, Oxford, UK, 1999. · Zbl 0931.65118
[57] P. Ramachandran and G. Varoquaux, {\it Mayavi: 3D Visualization of Scientific Data}, Comput. Sci. Engrg., 13 (2011), pp. 40-51.
[58] Y. Saad, {\it A flexible inner-outer preconditioned GMRES algorithm}, SIAM J. Sci. Comput., 14 (1993), pp. 461-469. · Zbl 0780.65022
[59] Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, 2nd ed., SIAM, Philadelphia, 2003. · Zbl 1031.65046
[60] M. H. Scott and G. L. Fenves, {\it A Krylov subspace accelerated Newton algorithm}, in Proceedings of the 2003 ASCE Structures Congress, L. N. Lowes and G. R. Miller, eds., 2003, pp. 45-55.
[61] D. F. Shanno, {\it Conditioning of quasi-Newton methods for function minimization}, Math. Comp., 24 (1970), pp. 647-656. · Zbl 0225.65073
[62] J. R. Shewchuk, {\it An Introduction to the Conjugate Gradient Method without the Agonizing Pain}, Tech. Rep., Carnegie Mellon University, Pittsburgh, 1994.
[63] B. Smith, {\it Domain decomposition methods for partial differential equations}, ICASE LARC Interdisciplinary Ser. Sci. Engrg., 4 (1997), pp. 225-244. · Zbl 0865.65089
[64] B. F. Smith, P. Bjørstad, and W. D. Gropp, {\it Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations}, Cambridge University Press, Cambridge, UK, 1996. · Zbl 0857.65126
[65] B. F. Smith and X. Tu, {\it Domain decomposition}, in Encyclopedia of Applied and Computational Mathematics, B. Engquist, ed., Springer, New York, 2015.
[66] M. Smooke and R. Mattheij, {\it On the solution of nonlinear two-point boundary value problems on successively refined grids}, Appl. Numer. Math., 1 (1985), pp. 463-487. · Zbl 0619.65074
[67] A. Toselli and O. B. Widlund, {\it Domain Decomposition Methods: Algorithms and Theory}, Springer Ser. Comput. Math. 34, B. Engquist, ed., Springer, New York, 2005. · Zbl 1069.65138
[68] U. Trottenberg, C. Oosterlee, and A. Schüller, {\it Multigrid}, Academic Press, San Diego, CA, 2001.
[69] R. S. Tuminaro, H. F. Walker, and J. N. Shadid, {\it On backtracking failure in Newton-GMRES methods with a demonstration for the Navier-Stokes equations}, J. Comput. Phys., 180 (2002), pp. 549-558. · Zbl 1143.76489
[70] H. F. Walker and P. Ni, {\it Anderson acceleration for fixed-point iterations}, SIAM J. Numer. Anal., 49 (2011), pp. 1715-1735. · Zbl 1254.65067
[71] H. F. Walker, C. S. Woodward, and U. M. Yang, {\it An accelerated fixed-point iteration for solution of variably saturated flow}, in Proceedings of the 18th International Conference on Water Resources, J. Carrera, ed., Barcelona, 2010.
[72] T. Washio and C. Oosterlee, {\it Krylov subspace acceleration for nonlinear multigrid schemes}, Electron. Trans. Numer. Anal., 6 (1997), pp. 271-290. · Zbl 0903.65096
[73] P. Wesseling, {\it An Introduction to Multigrid Methods}, R. T. Edwards, Philadelphia, 2004. · Zbl 0760.65092
[74] P. Wolfe, {\it Convergence conditions for ascent methods}, SIAM Rev., 11 (1969), pp. 226-235. · Zbl 0177.20603
[75] P. Wriggers, {\it Nonlinear Finite Element Methods}, Springer, New York, 2008. · Zbl 1153.74001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.