Simultaneous determination of polynomial roots and multiplicities: An algorithm and related problems (Q803730)

The algorithm is based on a previously published iterative method, properties of which are outlined. It is able to process polynomials represented in a general form by means of bases satisfying a three term recurrence relation. A module provides the iterative method with a suitable starting point. Multiplicities are dynamically identified, corrected, if necessary, and finally accepted when a sufficient degree of reliability has been reached. The noise threshold is estimated and the related allowed maximum accuracy can be reached for each root. Multiple roots can be approached with a quadratic-like convergence and with the same accuracy as the simple ones. In order to make the algorithm adaptable to different situations, a set of initial preselections is provided to control the flow of the program and some tests are automatically avoided in the simple cases or when a low degree of accuracy is required. The routine was widely tested and a comparison with the Jenkins-Traub algorithm is reported in the last section.