Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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?

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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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
1  
@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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.