A parallel implementation of the Durand-Kerner algorithm for polynomial root-finding on GPU

被引：4
|
作者：
Ghidouche, Kahina [1 ]
Couturier, Raphael [2 ]
Sider, Abderrahmane [1 ]
机构：
[1] Univ A Mira Bejaia, LIMED Lab, Bejaia, Algeria
[2] Univ Franche Comte, FEMTO ST Inst, IUT Belfort Montbeliard, F-90016 Belfort, France
来源：
2014 International Conference on Advanced Networking Distributed Systems and Applications (INDS 2014) | 2014年
关键词：
polynomial root-finding; high degree; iterative methods; Durant-Kerner method; GPU; CUDA; Parallelization;
D O I：
10.1109/INDS.2014.17
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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 C 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.
引用
收藏
页码：53 / 57
页数：5
相关论文
共 50 条
  • [11] THE DURAND-KERNER POLYNOMIALS ROOTS-FINDING METHOD IN CASE OF MULTIPLE ROOTS
    FRAIGNIAUD, P
    BIT, 1991, 31 (01): : 112 - 123
  • [12] On the convergent condition of Durand-Kerner method in parallel circular iteration of multi-step
    Zhu, L
    APPLIED MATHEMATICS AND COMPUTATION, 2005, 169 (01) : 179 - 191
  • [13] Algorithms for quaternion polynomial root-finding
    Kalantari, Bahman
    JOURNAL OF COMPLEXITY, 2013, 29 (3-4) : 302 - 322
  • [14] Voronoi Diagrams and Polynomial Root-Finding
    Kalantari, Bahman
    2009 6TH INTERNATIONAL SYMPOSIUM ON VORONOI DIAGRAMS (ISVD 2009), 2009, : 31 - 40
  • [15] A ROOT-FINDING ALGORITHM FOR CUBICS
    Northshield, Sam
    PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2013, 141 (02) : 645 - 649
  • [16] 2 OBSERVATIONS ON DURAND-KERNERS ROOT-FINDING METHOD
    KJELLBERG, G
    BIT, 1984, 24 (04): : 556 - 559
  • [17] POLYNOMIAL ROOT-FINDING ALGORITHMS AND BRANCHED COVERS
    KIM, MH
    SUTHERLAND, S
    SIAM JOURNAL ON COMPUTING, 1994, 23 (02) : 415 - 436
  • [18] Structured Matrix Methods for Polynomial Root-Finding
    Gemignani, Luca
    ISSAC 2007: PROCEEDINGS OF THE 2007 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, 2007, : 175 - 180
  • [19] Weierstrass method for quaternionic polynomial root-finding
    Irene Falcao, M.
    Miranda, Fernando
    Severino, Ricardo
    Joana Soares, M.
    MATHEMATICAL METHODS IN THE APPLIED SCIENCES, 2018, 41 (01) : 423 - 437
  • [20] Matrix computations and polynomial root-finding with preprocessing
    Pan, Victor Y.
    Qian, Guoliang
    Zheng, Ai-Long
    Chen, Zhao
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2011, 434 (04) : 854 - 879
12345