NonlinearSolve.jl: Other References You Can Turn to

Table of Links

Abstract and 1. Introduction

2. Mathematical Description and 2.1. Numerical Algorithms for Nonlinear Equations

2.2. Globalization Strategies

2.3. Sensitivity Analysis

2.4. Matrix Coloring & Sparse Automatic Differentiation

3. Special Capabilities

3.1. Composable Building Blocks

3.2. Smart PolyAlgortihm Defaults

3.3. Non-Allocating Static Algorithms inside GPU Kernels

3.4. Automatic Sparsity Exploitation

3.5. Generalized Jacobian-Free Nonlinear Solvers using Krylov Methods

4. Results and 4.1. Robustness on 23 Test Problems

4.2. Initializing the Doyle-Fuller-Newman (DFN) Battery Model

4.3. Large Ill-Conditioned Nonlinear Brusselator System

5. Conclusion and References

5. Conclusion

Solving systems of nonlinear equations is a fundamental challenge that arises across many scientific domains. This paper presented NonlinearSolve.jl, a high-performance and robust open-source solver for nonlinear systems implemented natively in the Julia programming language. Through extensive numerical experiments on benchmark problems, real-world applications, and scalability tests, we have demonstrated the superior capabilities of NonlinearSolve.jl compared to existing software tools.

Key strengths of NonlinearSolve.jl include its flexible unified API for rapidly experimenting with different solver options, smart automatic algorithm selection for balancing speed and robustness, specialized non-allocating kernels for small systems, automatic sparsity exploitation, and support for Jacobian-free Krylov methods. These features enable NonlinearSolve.jl to reliably solve challenging nonlinear problems, including cases where standard solvers fail while attaining high performance through techniques.

References.

[1] Gerhard Wanner and Ernst Hairer. Solving ordinary differential equations II, volume 375. Springer Berlin Heidelberg New York, 1996.

[2] Wayne H. Enright and Paul H. Muir. Runge-Kutta Software with Defect Control for Boundary Value ODEs. SIAM J. Sci. Comput., 17:479–497, 1996.

[3] Peter Deuflhard and Georg Bader. Multiple shooting techniques revisited. In Numerical Treatment of Inverse Problems in Differential and Integral Equations: Proceedings of an International Workshop, Heidelberg, Fed. Rep. of Germany, August 30—September 3, 1982, pages 74–94. Springer, 1983.

[4] Uri M Ascher, Robert MM Mattheij, and Robert D Russell. Numerical solution of boundary value problems for ordinary differential equations. SIAM, 1995.

[5] Weidong Zhang. Improved implementation of multiple shooting for BVPs. Computer Science Department, University of Toronto, 2012.

[6] Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep Equilibrium Models. arXiv:1909.01377 [cs, stat], October 2019. URL http://arxiv.org/abs/1909.01377. arXiv: 1909.01377.

[7] Shaojie Bai, Vladlen Koltun, and J. Zico Kolter. Multiscale Deep Equilibrium Models. arXiv:2006.08656 [cs, stat], November 2020. URL http://arxiv.org/abs/ 2006.08656. arXiv: 2006.08656.

[8] Avik Pal, Alan Edelman, and Chris Rackauckas. Continuous Deep Equilibrium Models: Training Neural ODEs Faster by Integrating Them to Infinity. In 2023 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–9, 2023. doi: 10.1109/HPEC58863.2023.10363574.

[9] Avik Pal. On Efficient Training & Inference of Neural Differential Equations. Master’s thesis, Massachusetts Institute of Technology, 2023.

[10] Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. Julia: A fresh approach to numerical computing. SIAM review, 59(1):65–98, 2017. URL https://doi.org/10.1137/141000671.

[11] Yingbo Ma, Shashi Gowda, Ranjan Anantharaman, Chris Laughman, Viral Shah, and Chris Rackauckas. Modelingtoolkit: A composable graph transformation system for equation-based modeling, 2021.

[12] David J Gardner, Daniel R Reynolds, Carol S Woodward, and Cody J Balos. Enabling new flexibility in the SUNDIALS suite of nonlinear and differential/algebraic equation solvers. ACM Transactions on Mathematical Software (TOMS), 2022. doi: 10.1145/3539801.

[13] Alan C Hindmarsh, Peter N Brown, Keith E Grant, Steven L Lee, Radu Serban, Dan E Shumaker, and Carol S Woodward. SUNDIALS: Suite of nonlinear and differential/algebraic equation solvers. ACM Transactions on Mathematical Software (TOMS), 31(3):363–396, 2005. doi: 10.1145/1089014.1089020.

[14] Jorge J Moré, Burton S Garbow, and Kenneth E Hillstrom. User guide for MINPACK-1. Technical report, CM-P00068642, 1980.

[15] Frédéric Devernay. C/C++ Minpack. http://devernay.free.fr/hacks/cminpack/, 2007.

[16] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261–272, 2020. doi: 10.1038/s41592-019-0686-2.

[17] The MathWorks Inc. Optimization Toolbox version: 9.4 (R2022b), 2022. URL https://www.mathworks.com.

[18] Satish Balay, Shrirang Abhyankar, Mark Adams, Jed Brown, Peter Brune, Kris Buschelman, Lisandro Dalcin, Alp Dener, Victor Eijkhout, W Gropp, et al. PETSc users manual. 2019.

[19] Jason Rader, Terry Lyons, and Patrick Kidger. Optimistix: modular optimisation in JAX and Equinox. arXiv preprint arXiv:2402.09983, 2024.

[20] Patrick Kofod Mogensen and Asbjørn Nilsen Riseth. Optim: A mathematical optimization package for Julia. Journal of Open Source Software, 3(24):615, 2018. doi: 10.21105/joss.00615.

[21] Torkel E. Loman, Yingbo Ma, Vasily Ilin, Shashi Gowda, Niklas Korsbo, Nikhil Yewale, Chris Rackauckas, and Samuel A. Isaacson. Catalyst: Fast and flexible modeling of reaction networks. PLOS Computational Biology, 19(10):1–19, 10 2023. doi: 10.1371/journal.pcbi.1011530. URL https://doi.org/10.1371/journal. pcbi.1011530.

[22] Bruno Cordani. The Kepler Problem: Group Theotretical Aspects, Regularization and Quantization, with Application to the Study of Perturbations, volume 29. Springer Science & Business Media, 2003.

[23] Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999.

[24] F-A Potra and Vlastimil Pták. Nondiscrete induction and a double step secant method. Mathematica Scandinavica, 46(2):236–250, 1980.

[25] Harmandeep Singh and Janak Raj Sharma. Simple yet highly efficient numerical techniques for systems of nonlinear equations. Computational and Applied Mathematics, 42(1):22, 2023.

[26] Philip Wolfe. Convergence conditions for ascent methods. SIAM review, 11(2): 226–235, 1969.

[27] Philip Wolfe. Convergence conditions for ascent methods. II: Some corrections. SIAM review, 13(2):185–188, 1971.

[28] William W Hager and Hongchao Zhang. Algorithm 851: CG_DESCENT, a conjugate gradient method with guaranteed descent. ACM Transactions on Mathematical Software (TOMS), 32(1):113–137, 2006.

[29] Jorge J Moré and David J Thuente. Line search algorithms with guaranteed sufficient decrease. ACM Transactions on Mathematical Software (TOMS), 20(3): 286–307, 1994.

[30] Long Hei. A self-adaptive trust region algorithm. Journal of Computational Mathematics, pages 229–236, 2003.

[31] Ya-xiang Yuan. Recent advances in trust region algorithms. Mathematical Programming, 151:249–281, 2015.

[32] Jinyan Fan. Convergence rate of the trust region method for nonlinear equations under local error bound condition. Computational Optimization and Applications, 34(2):215–227, 2006.

[33] Fabian Bastin, Vincent Malmedy, Mélodie Mouffe, Philippe L Toint, and Dimitri Tomanos. A retrospective trust-region method for unconstrained optimization. Mathematical programming, 123:395–418, 2010.

[34] Michael JD Powell. A hybrid method for nonlinear equations. Numerical methods for nonlinear algebraic equations, pages 87–161, 1970.

[35] Avik Pal. Lux: Explicit parameterization of deep neural networks in julia. GitHub repository, 2022.

[36] M Greta Ruppert, Yvonne Späck-Leigsnering, Julian Buschbaum, and Herbert De Gersem. Adjoint variable method for transient nonlinear electroquasistatic problems. Electrical Engineering, pages 1–7, 2023.

[37] M Blondel, Q Berthet, M Cuturi, R Frostig, S Hoyer, and F Llinares-L. opez, f. pedregosa, and j.-p. vert, efficient and modular implicit differentiation. arXiv preprint arXiv:2105.15183, 2021.

[38] Steven G Johnson. Notes on adjoint methods for 18.335. Introduction to Numerical Methods, 2006.

[39] J. Revels, M. Lubin, and T. Papamarkou. Forward-Mode Automatic Differentiation in Julia. arXiv:1607.07892 [cs.MS], 2016. URL https://arxiv.org/abs/1607. 07892.

[40] Michael Innes. Don’t Unroll Adjoint: Differentiating SSA-Form Programs. CoRR, abs/1810.07951, 2018. URL http://arxiv.org/abs/1810.07951.

[41] Michael Innes, Elliot Saba, Keno Fischer, Dhairya Gandhi, Marco Concetto Rudilosso, Neethu Mariya Joy, Tejan Karmali, Avik Pal, and Viral Shah. Fashionable modelling with flux. arXiv preprint arXiv:1811.01457, 2018.

[42] Brett M Averick, Jorge J Moré, Christian H Bischof, Alan Carle, and Andreas Griewank. Computing large sparse Jacobian matrices using automatic differentiation. SIAM Journal on Scientific Computing, 15(2):285–294, 1994.

[43] Ralf Giering, Thomas Kaminski, and Thomas Slawig. Generating efficient derivative code with TAF: Adjoint and tangent linear Euler flow around an airfoil. Future generation computer systems, 21(8):1345–1355, 2005.

[44] Andrea Walther and Andreas Griewank. Getting Started with ADOL-C. Combinatorial scientific computing, 181:202, 2009.

[45] Shashi Gowda, Yingbo Ma, Valentin Churavy, Alan Edelman, and Christopher Rackauckas. Sparsity Programming: Automated Sparsity-Aware Optimizations in Differentiable Programming. In Program Transformations for ML Workshop at NeurIPS 2019, 2019.

[46] Assefaw Hadish Gebremedhin, Fredrik Manne, and Alex Pothen. What color is your Jacobian? Graph coloring for computing derivatives. SIAM review, 47(4): 629–705, 2005.

[47] Pankaj Mishra, Shashi Gowda, Langwen Huang, and Chris Rackauckas. SparseDiffTools.jl. JuliaDiff/SparseDiffTools.jl, 2020.

[48] Ivo FD Oliveira and Ricardo HC Takahashi. An enhancement of the bisection method average performance preserving minmax optimality. ACM Transactions on Mathematical Software (TOMS), 47(1):1–24, 2020.

[49] Charles G Broyden. A class of methods for solving nonlinear simultaneous equations. Mathematics of computation, 19(92):577–593, 1965.

[50] Jan Klement. On using quasi-newton algorithms of the Broyden class for modelto-test correlation. Journal of Aerospace Technology and Management, 6:407–414, 2014.

[51] Youcef Saad and Martin H Schultz. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on scientific and statistical computing, 7(3):856–869, 1986.

[52] Alexis Montoison and Dominique Orban. Krylov.jl: A Julia basket of handpicked Krylov methods. Journal of Open Source Software, 8(89):5187, 2023. doi: 10.21105/joss.05187.

[53] Sivan Toledo. Locality of reference in LU decomposition with partial pivoting. SIAM Journal on Matrix Analysis and Applications, 18(4):1065–1081, 1997.

[54] Yingbo Ma and Chris Elrod. GitHub – JuliaLinearAlgebra/RecursiveFactorization.jl — github.com. https://github.com/JuliaLinearAlgebra/ RecursiveFactorization.jl. [Accessed 16-02-2024].

[55] V Churavy, D Aluthge, LC Wilcox, S Byrne, M Waruszewski, A Ramadhan, S Schaub Meredith, J Schloss, J Samaroo, J Bolewski, et al. JuliaGPU/KernelAbstractions. jl: v0. 6.0, 2021.

[56] Utkarsh, Vaibhav Kumar Dixit, Julian Samaroo, Avik Pal, Alan Edelman, and Christopher Vincent Rackauckas. Efficient GPU-Accelerated Global Optimization for Inverse Problems. In ICLR 2024 Workshop on AI4DifferentialEquations In Science, 2024. URL https://openreview.net/forum?id=nD10o1ge97.

[57] Mark K Transtrum and James P Sethna. Improvements to the LevenbergMarquardt algorithm for nonlinear least-squares minimization. arXiv preprint arXiv:1201.5885, 2012.

[58] Marc Doyle, Thomas F Fuller, and John Newman. Modeling of galvanostatic charge and discharge of the lithium/polymer/insertion cell. Journal of the Electrochemical society, 140(6):1526, 1993.

[59] Chris Rackauckas, Maja Gwozdz, Anand Jain, Yingbo Ma, Francesco Martinuzzi, Utkarsh Rajput, Elliot Saba, Viral B Shah, Ranjan Anantharaman, Alan Edelman, et al. Composing modeling and simulation with machine learning in julia. In 2022 Annual Modeling and Simulation Conference (ANNSIM), pages 1–17. IEEE, 2022.

[60] Marc D Berliner, Daniel A Cogswell, Martin Z Bazant, and Richard D Braatz. Methods—PETLION: Open-source software for millisecond-scale porous electrode theory-based lithium-ion battery simulations. Journal of The Electrochemical Society, 168(9):090504, 2021.