# How to find all complex roots of an equation in a domain

I am facing a problem where I want to find the complex roots of $f(z)=z-sin(z)=0$ numerically.

There are infinitely many roots of the function, but I am only interested in the $N$ closest to the origin, or to put it more general, within a certain domain in the complex plane.

The Newton-Raphson method also works on complex functions, so given some initial $z_0$, I end up in some root of $f(z)$. However, this is not giving me all roots. I know that the roots will have a basin of attraction, so I will basically need a $z_0$ in every basin of attraction, except that I don't have this basin to start with. Smartest I can come up with, is starting with a grid of $z_0$'s, and to select the uniques. This seems very inefficient.

Therefor my question: is there an efficient method to find all complex roots of $f(z)$ within a domain of the complex plane?

-
I asked this relatex question on Math.SE math.stackexchange.com/questions/243228/… – Bernhard Nov 23 '12 at 15:33

To find all complex roots in some domain you need to employ a branch and bound method. Typically one begins with an enclosing box and splits it recursively into subboxes, then applies some constructive method for getting lower and/or upper bounds on the number of solutions in the box. If no solution exists in a box it can be discarded.

Some applicable test are for example in my paper
A. Neumaier, Enclosing clusters of zeros of polynomials, J. Comput. Appl. Math. 156 (2003), 389-401.
http://www.mat.univie.ac.at/~neum/ms/polzer.pdf

-
Thanks for your answer. I skimmed your paper, but have to take a much more detailed look to get it to work. – Bernhard Nov 16 '12 at 7:01
Online, I found this paper (pdf-alert) journal.austms.org.au/ojs/index.php/ANZIAMJ/article/download/… , describing more extensively the method you propose. Can you see this as a feasible approach to my problem? (The authors don't claim efficiency, but robustness) – Bernhard Nov 22 '12 at 20:29
@Bernhard: Yes, it is feasible, but the calculation of the contour integrals is quite costly. Perhaps you can combine the method there with the tests from my paper (which are fairly cheap in comparison). – Arnold Neumaier Nov 23 '12 at 10:53
Thanks. I was able to implement the method I provided in the comment. For the specific case I am considering, I have some knowledge about the pole distribution, which allows me in principle to dismiss a lot of the squares on beforehand. I don't think it is necessary for me to implement the tests you provided. – Bernhard Nov 23 '12 at 14:14

Arnold has already given a good answer. In general, what you are asking for is similar to a global optimization algorithm for finding all the minima of a function (in your case, the minima would be those of $|f(z)|^2=f(z)\overline{f(z)}$. There is a vast amount of literature on this issue if you know the keyword (global optimization) to look for.

-
Do you have any advised reading or authors on global optimization? – Bernhard Nov 16 '12 at 7:02
Your local library. – Wolfgang Bangerth Nov 17 '12 at 11:35
Off course I can find books, but as I am absolutely not familiar with this material, I'd rather pick the right one right away. – Bernhard Nov 18 '12 at 9:23
I have nothing concrete. I've mostly learned optimization from the book by Nocedal and Wright (who I think have a section on global optimization) and from papers. I know that there are books on global optimization but I haven't looked at any of them. – Wolfgang Bangerth Nov 19 '12 at 2:51