1 Attachment(s)

Figure of Merit for Algorithms which extract roots from real polynomials

Tester for Rooting Algorithms

I am looking for source code, preferably C++, for algorithms which extract the roots of modest sized real polynomials (order up to ~20). I need accuracy, not speed, particularly for small/zero roots. I've found code on the WWW including r_poly_aki, a C++ port from Fortran of the Jenkins Traub TOMS493. But nothing with figures of merit.

To discriminate betweeen candidates I've written a GUI tester running under windows. It incorporates r_poly_aki and some lesser candidates. The purpose of this post is to persuade maths guys knowledgeable of rooting algorithms to download and play with the tester, and to let me know

a. if they think the r_poly_aki algorithm can be bettered.

b. of other algorithms worthy of incorporation in the Tester.

It works by generating random conjugate roots, multiplying these out to real polys and by comparing the generated and extracted roots of same. It plots the normalised differences between generated and extracted roots in the x/y plane and generates a log file of root errors. The user specifies the size of the polynomials, the max size of the roots, and the minimum error size to be written to file. With a decent CPU the Tester will plot tens of thousands of iterations per minute, allowing the rapid characterisation of a rooting algorithm for different sized polys and roots. It has bugs, but is (just) fit for purpose.

If I get useful feedback I'm prepared to improve it.

The Tester is zipped, the passwork is:- roottester

It extracts to an exe, lib files and a readme.txt.

It doesn't install, the exe runs as is.

Its quite benign, and will not litter your registry, but note that it can generate BIG log files if used carelessly.

Hoping someone is interested, . . .

John