General polynomial roots and their multiplicities inO(N)memory andO(N2)Time∗
Frank Uhlig · Linear and Multilinear Algebra · 1999
For a given real or complex polynomial p of degree n we modify the Euclidean algorithm to find a general tridiagonal matrix representation T of the monic version of p and then use the tridiagonal DQR eigenvalue algorithm on T in order to find all roots ofp with their multiplicities in O(n 2) operations and 0(n) storage. We include details of the implementation and comparisons with several, standard and recent, essentially 0(n 3) polynomial root finders.