Tests for polynomial root finders

[ivan-pi]

I have extracted the polynomials from an early issue of ACM TOMS (in case anyone is interested in the Algol code, a copy is available here):

Grau, A. A. (1960). Solution of polynomial equation by Bairstow-Hitchcock method. Communications of the ACM, 3(2), 74-75. https://doi.org/10.1145/366959.366966

I've attached the polynomials in the MPSolve polynomial file format: polyBH.tar.gz. MPSolve can be used to find the roots with arbitrary precision. (Some of the polynomials have nice roots, which could be easily specified analytically.)

The ground work for testing polynomial root solvers are laid out in

Jenkins, M. A., & Traub, J. F. (1975). Principles for testing polynomial zero finding programs. ACM Transactions on Mathematical Software (TOMS), 1(1), 26-34. https://doi.org/10.1145/355626.355632

which also provides a collection of test polynomials.

The following resources also provide or refer to collections of test polynomials:

• Lang, M., & Frenzel, B. C. (1994). Polynomial root finding. IEEE Signal Processing Letters, 1(10), 141-143. [PDF]
• Malek, F. (1995). Polynomial zerofinding matrix algorithms. University of Ottawa (Canada). [PDF]; (I've done my best to transcribe these polynomials from the thesis in the file getpoly.f.txt, however a few support routines are missing and the code is in terrible shape)
• Edelman, A., & Murakami, H. (1995). Polynomial roots from companion matrix eigenvalues. Mathematics of Computation, 64(210), 763-776. https://doi.org/10.1090/S0025-5718-1995-1262279-2
• Zeng, Z. (2004). Algorithm 835: MultRoot---a Matlab package for computing polynomial roots and multiplicities. ACM Transactions on Mathematical Software (TOMS), 30(2), 218-236. https://doi.org/10.1145/980175.980189

That's about all I can do for one evening.