Also, see Fast Multipole Method for solving such problems: https://en.wikipedia.org/wiki/Fast_multipole_method At 07:19 AM 7/3/2015, Warren D Smith wrote:
Actually, the whole view of a "monic polynomial" P(z) as P(z)=PRODUCT_j (z-r_j) where r_j are the roots hence log P(z) = SUM_j log(z-r_j) hence log|P(z)| = SUM_j log|z-r_j| = potential energy of movable negative unit charge located at z in the coulomb fields of positive unit charges fixed at the r_j, is often quite useful.
For one example, suppose you want to make a rootfinding algorithm. "Newton's iteration" is equivalent to: you assume the whole electric field -P'(z)/P(z) at z is due to just one root R, and solve for its location; then go there (z:=R) and do it again. Some other iterations can also be thought of electrostatically.
One can also create "simultaneous iterations" in this way which attempt to converge to all N roots of P(z) at once. Place N movable negative unit charges in the complex plane. They will repel each other. There will also be attractive forces from the N fixed roots r_j of P(z), which are positive unit charges. The min-energy locations of the N movable charges are co-located with the N roots. Minimizing energy solves for the roots. Basically any iteration which keeps decreasing energy in a sensible way must converge. You can at each guess-location compute the electric field arising from both the fixed and movable charges, pretend it is due to just a constant number of them, e.g. to 1 positive and 1 negative charge, and go to the location of the positive... or take a smaller step in that direction (keep decreasing step size until cause energy decrease; one can devise a "safety rule" of that sort to provably assure convergence). By fast polynomial algorithm methods the simultaneous iteration can be implemented to run in O(N*(logN)^2) flops per simultaneous-adjust. A famous theorem of electrostatics assures that there exists no energy local-min for the movable charges aside from the global min we want. These schemes can be shown to converge ultimately in a manner such that the number of correct decimals grows geometrically, if all roots are isolated. Convergence to multiple roots is slower, geometric, although you can devise variant algorithms which do not care about multiplicities up to say, 4, and you can remove all multiple roots ahead of time by solving for the roots not of P(z) but rather of Q(z)=P(z)/GCD(P(z), P'(z)) which has only single roots.
I invented and programmed this class of rootfinding methods in the 1980s. They work pretty well if you use your own floating point arithmetic (not machine's) with larger exponent field so as to remove worries about numerical overflow with high-degree polynomials.