Scalable Higher-order Nonlinear Solvers via Higher-order Automatic Differentiation

Abstract

This paper demonstrates new methods and implementations ofnonlinear solvers with higher-order of convergence, whichis achieved by efficiently computing higher-orderderivatives. Instead of computing full derivatives, whichcould be expensive, we compute directional derivatives withTaylor-mode automatic differentiation. We first implementHouseholder's method with arbitrary order for one variable,and investigate the trade-off between computational costand convergence order. We find that the second-ordervariant, i.e., Halley's method, to be the most valuable,and further generalize Halley's method to systems ofnonlinear equations and demonstrate that it can scaleefficiently to large-scale problems. We further applyHalley's method on solving large-scale ill-conditionednonlinear problems, as well as solving nonlinear equationsinside stiff ODE solvers, and demonstrate that it couldoutperform Newton's method.