Computer methodologies for comparison of computational efficiency of simultaneous methods for finding polynomial zeros

Abstract

© 2019 Elsevier B.V. The study and analysis of iterative methods for the determination of zeros of algebraic polynomials, the subject of this paper, is one of the most actual tasks in the theory and practice. Our main goal is to examine and compare the quality of most frequently used methods for simultaneously finding all zeros of a polynomial by combining numerical experiments, theoretical models and empirical CPU time-methodology. Special attention is devoted to empirical average case model assuming that average CPU times are calculated performing the experiment (i) on several different computers, (ii) running each method through many loops for a fixed example, (iii) testing reasonably large number of polynomials of different structure body, and (iv) the use of (almost) arbitrary initial approximations. The empirical model ranks the tested methods on the base of the consumed CPU times needed for the fulfillment of the required accuracy of approximations under the same initial conditions. Our aim is to select a group of the most powerful simultaneous methods with globally convergent performance. Convergence behavior of two most powerful methods is illustrated by trajectories in the complex plane that consist of the point approximations, starting with initial points and going towards the endpoints where the iterative process stops due to the termination criterion.