A Parallel Implementation of the Durand-Kerner Algorithm for Polynomial Root-Finding on GPU

Author

Ghidouche, Kahina ; Couturier, Raphail ; Sider, Abderrahmane

Author_Institution

LIMED Lab., Univ. A-Mira of Bejaia, Bejaia, Algeria

fYear

2014

fDate

17-19 June 2014

Firstpage

53

Lastpage

57

Abstract

In this article we present a parallel implementation of the Durand-Kerner algorithm to find roots of polynomials of high degree on a GPU architecture (Graphics Processing Unit). We have implemented both a CPU version in and a GPU compatible version with CUDA. The main result of our work is a parallel implementation that is 10 times as fast as its sequential counterpart on a single CPU for high degree polynomials that is greater than about 48,000.

Keywords

graphics processing units; mathematics computing; parallel architectures; polynomials; CPU version; CUDA; Durand-Kerner algorithm; GPU architecture; GPU compatible version; graphics processing unit; parallel implementation; polynomial root-finding; Computer architecture; Graphics processing units; Instruction sets; Iterative methods; Jacobian matrices; Kernel; Polynomials; CUDA; Durant-Kerner method; GPU; Parallelization; high degree; iterative methods; polynomial root-finding;

fLanguage

English

Publisher

ieee

Conference_Titel

Advanced Networking Distributed Systems and Applications (INDS), 2014 International Conference on

Conference_Location

Bejaia

Type

conf

DOI

10.1109/INDS.2014.17

Filename

6969057