One of the semi-recommended ones for finding roots in the complex plane is Laguerre's method, which for some reason is not included in the Wikipedia article on root-finding.

http://en.wikipedia.org/wiki/Laguerre's_method

The reason I know of this is a colloquium lecture long ago by Steven Smale on the complexity of Newton's method, during which William Kahan stood up and held forth on why Newton's method was worthless and Laguerre's was much better.

I cannot tell whether you insist on finding all roots to high accuracy. One could perhaps divide out by $(x - r_k)^{n_k}$ each time a root $r_k$ with multiplicity $n_k$ is found, and search for roots for the new polynomial, using those results as seed values for finding accurate roots using the original polynomial.

One of the semi-recommended ones for finding roots in the complex plane is Laguerre's method, which for some reason is not included in the Wikipedia article on root-finding.

http://en.wikipedia.org/wiki/Laguerre's_method

The reason I know of this is a colloquium lecture long ago by Steven Smale on the complexity of Newton's method, during which William Kahan stood up and held forth on why Newton's method was worthless and Laguerre's was much better.

I cannot tell whether you insist on finding all roots to high accuracy. One could perhaps divide out by $(x - r_k)^{n_k}$ each time a root $r_k$ with multiplicity $n_k$ is found, and search for roots for the new polynomial, using those results as seed values for finding accurate roots using the original polynomial.