Efficient high degree polynomial root finding using GPU

Polynomials are mathematical algebraic structures that play a great role in science and engineering. Finding the roots of high degree polynomials is computationally demanding. In this paper, we present the results of a parallel implementation of the Ehrlich-Aberth algorithm for the root finding problem for high degree polynomials on GPUs using CUDA and on multi-core processors using OpenMP. The main result we achieved is to solve high degree polynomials (up to 1,000,000) efficiently. We also compare the Ehrlich-Aberth method and the Durand-Kerner one on both full and sparse polynomials. Accordingly, our second result is that the first method is much faster and more efficient. Last, but not least, an original proof of the convergence of the asynchronous implementation for the EA method is produced. (C) 2016 Elsevier B.V. All rights reserved.