# Rootfinding algorithm that takes advantage of automatic differentiation

Is there any algorithm (or tricks) for rootfinding to take advantages of automatic differentiation (AD)?

Rootfinding algorithms typically solve $$\mathbf{f}(\mathbf{y}) = \mathbf{0}$$ where $$\mathbf{f}:\mathbb{R}^n\rightarrow\mathbb{R}^n$$ and $$\mathbf{y}:\mathbb{R}^n$$.

Newton's method is not applicable in my case because the whole Jacobian does not fit in my memory while Broyden's method (one of the most popular method) usually doesn't converge.

I wonder if there's any way to take advantage of automatic differentiation in making root finder algorithm more stable or faster to converge (e.g. initializing the inverse of Jacobian with AD maybe?).

• How large is $n$? Is the Jacobian sparse or dense? Sep 28 '20 at 14:46
• $n$ is typically 10^4-10^5 and constructing the full Jacobian is expensive. I'm not sure if it's sparse or dense, but the AD engine can provide the vector-Jacobian and Jacobian-vector product automatically. Sep 28 '20 at 14:55
• I haven't used AD, but it sounds like you can form the entries of the Jacobian on the fly as they are needed. If this is true, you could use this to express the Jacobian as an operator on a vector, which would let you use "matrix-free" iterative solver methods that rely on matrix-vector products (conjugate gradient, GMRES, etc). Not sure if this is what @BrianBorchers meant by "interactive methods" Sep 28 '20 at 17:55
• Sorry for the typo. "interactive" should have been "iterative" in my answer. Sep 28 '20 at 18:01
• @BrianBorchers Didn't mean to be snooty, I actually googled "interactive methods" as I assumed it was some state of the art concept! Sep 28 '20 at 19:28

Dennis and Schnabel advocate treating the problem of finding a root of $$f(p)=0$$ as a nonlinear least squares problem:
$$\min \sum_{i=1}^{n} f_{i}(p)^{2}$$
Another approach would be to directly solve the nonlinear least-squares problem using an iterative method for unconstrained nonlinear minimization such as conjugate gradients, limited memory BFGS, etc. All of these require gradient computations, which in turn boil down to multiplying the Jacobian times $$f(p)$$. Your AD tool should be able to help with that.