Re: Lehmer-Schur pseudocode?

On Jul 14, 8:34 pm, Henry Bronson <h.bron...@xxxxxxxxxxxxxxxxxxxxxxxx>
wrote:
Unfortunately there seems to be very little information on the net about
the Lehmer-Schur algorithm. Almost everything Google finds is either
dead-tree, locked behind some academic journal's paywall, or a mirror of
the Wikipedia article for it or subset of the same information, which is
not enough to implement it I don't think. Particularly, would sampling
the four corners of each rect suffice to guess the winding number?

A Google Groups search shows a single mention in the history of Usenet,
before this post, in comp.compression.

(Why is there no comp.algorithms?)

So I'm asking here for pseudocode, or just useful information or links
to guide an implementation. If anyone can suggest a better algorithm
choice for finding the roots of a black-box analytic function, please do so.

(By "black-box analytic" I mean the algorithm should work without
knowing or guessing at how roots will be distributed, and the function
can be pretty much anything, save that it will be continuous, won't have
any poles on the complex plane, and won't involve z-bar. It should work
for arbitrary polynomials and, preferably, for stuff like sin, cos, etc.)

You will find links for it in "Numerical Recipes" but don't bother. I
have the NR collection and it's just a tiny blurb about its existence
in all of those books.

Here is what you want:
http://www.cs.uu.nl/research/techreps/repo/CS-1979/1979-01.pdf

This may also prove useful:
https://svn.ece.lsu.edu/svn/dmk/trunk/benchmarks/simtools/scpu2k/gap/polystff.g

P.S.
Acton is hardly complimentary. He says of Lehmer-Schur on p 197 of
"Numerical Methods That Work":
"Since the basic question-answering routine is not bothered by
multiple roots, it would seem that this iterative procedure might be
the universal polynomial root finder that we seek. Alas no! Tests on
a number of polynomials, both nasty and nice, show that Lehmer finds
roots about as precisely as one of the unattractive standard packages
but takes three times as long."
.

Relevant Pages

  • Lehmer-Schur pseudocode?
    ... Almost everything Google finds is either dead-tree, locked behind some academic journal's paywall, or a mirror of the Wikipedia article for it or subset of the same information, which is not enough to implement it I don't think. ... If anyone can suggest a better algorithm choice for finding the roots of a black-box analytic function, ...
    (comp.programming)
  • Re: Lehmer-Schur pseudocode?
    ... A Google Groups search shows a single mention in the history of Usenet, ... If anyone can suggest a better algorithm ... choice for finding the roots of a black-box analytic function, ...
    (sci.math.num-analysis)
  • Lehmer-Schur pseudocode?
    ... Almost everything Google finds is either dead-tree, locked behind some academic journal's paywall, or a mirror of the Wikipedia article for it or subset of the same information, which is not enough to implement it. ... If anyone can suggest a better algorithm choice for finding the roots of a black-box analytic function, ...
    (sci.math.num-analysis)
  • Re: Lehmer-Schur pseudocode?
    ... the Lehmer-Schur algorithm. ... choice for finding the roots of a black-box analytic function, ... for arbitrary polynomials and, preferably, for stuff like sin, cos, etc..) ...
    (comp.programming)
  • Re: Exact (LISP-ish) calculations in Ruby?
    ... There's an algorithm for calculating square roots, ... not in process) to the algorithm for long division. ... Raphson method) for calculating square/cube/fourth/... ...
    (comp.lang.ruby)