Zero-clusters of polynomials: Best approach in supercomputing era

摘要

Computing a zero-cluster of a polynomial sufficiently accurately within the available precision of computation has been an important issue from time immemorial. All the deterministic numerical methods so far known to us produce varying degree of errors. Often the errors are so dominant that the distinction between two zeros in the cluster becomes meaningfully difficult. Multiple zeros on the other hand can be more easily tackled and do not pose any serious computational problem. We discuss here the limits of both deterministic and randomized methods for zero-clusters and propose a simple exhaustive search algorithm that would obtain the zeros in a real/complex zero-cluster in a reasonable time. We present the computational error and computational/time complexity of this algorithm focusing on the fact that no measuring device can usually measure a quantity with an accuracy greater than 0.005%. We stress the fact that no other algorithm can perform better than the proposed algorithm in an ultra-high speed computing environment for most real-world problems.