# Algorithm for finding inverse images of a local diffeomorphism

Let $F : R^k \to R^k$ be a smooth map whose Jacobian $J(F): R^k \to R$ vanishes on a discrete set $S$, so that if $O$ is the complement of $S$, then $f: O \to R^k$, the restriction of $F$, is a local diffeomorphism, and in particular there are only finitely many points $x$ inside the unit ball of $R^k$ such that $f(x) = 0$. What I would like to know is if there any a good algorithm for finding such points $x$. Of course, if $k=1$ this is easy, using the Intermediate Value Theorem; just partition the interval $[-1,1]$ into a reasonably large number $N$ of subintervals of length $2/N$ and test on which subintervals $f$ changes sign, and then use bisection to locate a zero in those subintervals. If $k>1$ I suspect that some sort of application of Marching Cubes may work, but the usual search methods have not turned up anything.

-
With a lipschitz bound on $DF$, Newton's method gives an algorithm to approximate $F^{-1}$ effectively. There's a version of this written up in Hubbard's calculus textbook. –  Ryan Budney Aug 22 '13 at 21:27
Do you have $F$ as "a formula", or do you only have the ability to evaluate up to some precision on a suitably dense grid in $\mathbb{R}^k$? –  Vidit Nanda Aug 22 '13 at 23:32
@Nanda For the application I have in mind, F will be given by a formula. –  Dick Palais Aug 22 '13 at 23:51

With a Lipschitz bound on the derivative, Newton's method gives an algorithm to efficiently approximate $F^{-1}$. Hubbard's calculus textbook has a write-up using this perspective, viewing the result as a consequence of Kantorovich's Theorem. There's a fairly extensive analysis of the absolute error.
Yes! Newton's Method is clearly the way to go. For $k=1$, the algorithm I wrote in fact did use Newton's Method, (rather than bisection) since it is much faster. But I guess I forgot that Newton's Method works in higher dimensions too. Thanks Ryan. –  Dick Palais Aug 23 '13 at 5:40