1 \documentclass[11pt,a4paper]{article}
\r
2 \usepackage[latin1]{inputenc}
\r
4 \usepackage{amsfonts}
\r
7 \title{Paper1_kahina}
\r
9 \section{Root finding problem}
\r
10 we consider a polynomial of degree \textit{n} having coefficients
\r
11 in the complex \textit{C} and zeros $\alpha
\r
12 _{i},\textit{i=1,...,n}$. \\
\r
14 {\Large$p(x)=\sum{a_{i}x^{i}}=a_{n}\prod(x-\alpha_{i}),
\r
18 the root finding problem consist to find
\r
19 all n root of \textit{p(x)}. the problem of finding a root is
\r
20 equivalent to the problem of finding a fixed-point. To see this
\r
21 consider the fixed-point problem of finding the n-dimensional
\r
26 where $g : C^{n}\longrightarrow C^{n}$. Note that we can easily
\r
27 rewrite this fixed-point problem as a root-finding problem by
\r
28 setting $f (x) = x-g(x)$ and likewise we can recast the
\r
29 root-finding problem into a fixed-point problem by setting
\r
33 Often it will not be possible to solve such nonlinear equation
\r
34 root-finding problems analytically. When this occurs we turn to
\r
35 numerical methods to approximate the solution. Generally speaking,
\r
36 algorithms for solving problems numerically can be divided into
\r
37 two main groups: direct methods and iterative methods.
\r
39 Direct methods exist only for $n \leqslant4$,solved in closed form by G. Cardano
\r
40 in the mid-16th century. However, N.H. Abel in the early 19th
\r
41 century showed that polynomials of degree five or more could not
\r
42 be solved by directs methods. Since then researchers have
\r
43 concentrated on numerical (iterative) methods such as the famous
\r
44 Newton s method, Bernoulli s method of the 18th, and Graeffe s.
\r
45 With the advent of electronic computers, different methods has
\r
46 been developed such as the Jenkins-Traub method, Larkin s method,
\r
47 Muller s method, and several methods for simultaneous
\r
48 approximation of all the roots, starting with the Durand-Kerner
\r
52 $ Z_{i}=Z_{i}-\frac{P(Z_{i})}{\prod_{i\neq j}(z_{i}-z_{j})} $
\r
55 This formula is mentioned for the first time from Weiestrass [12]
\r
56 as part of the fundamental theorem of Algebra and is rediscovered
\r
57 from Ilieff [2], Docev [3], Durand [4], Kerner [5]. Another method
\r
58 discovered from Borsch-Supan [6] and also described and brought in
\r
59 the following form from Ehrlich [7] and Aberth [8]
\r
62 $ Z_{i}=Z_{i}-\frac{1}{{\frac {P'(Z_{i})}
\r
63 {P(Z_{i})}}-{\sum_{i\neq j}(z_{i}-z_{j})}} $
\r
66 Aberth, Ehrlich and Farmer-Loizou [10] have proved that the above
\r
67 method has cubic order of convergence for simple roots.
\r
70 Iterative methods raise several problem when implemented e.g.
\r
71 specific sizes of numbers must be used to deal with this
\r
72 difficulty.Moreover,the convergence time of iterative methods
\r
73 drastically increase like the degrees of high polynomials. The
\r
74 parallelization of these algorithms will improve the convergence
\r
77 Many authors have treated the problem of parallelization of
\r
78 simultaneous methods. Freeman [13] has tested the DK method, EA
\r
79 method and another method of the fourth order proposed from Farmer
\r
80 and Loizou [10],on a 8- processor linear chain, for polynomial of
\r
81 degree up to 8. The third method often diverges, but the first two
\r
82 methods have speed-up 5.5 (speed-up=(Time on one processor)/(Time
\r
83 on p processors)). Later Freeman and Bane [14] consider
\r
84 asynchronous algorithms, in which each processor continues to
\r
85 update its approximations even although the latest values of other
\r
86 $z_i((k))$ have not received from the other processors, in
\r
87 difference with the synchronous version where it would wait. in
\r
88 [15]proposed two methods of parallelization for architecture with
\r
89 shared memory and distributed memory,it able to compute the root
\r
90 of polynomial degree 10000 on 430 s with only 8 pc and 2
\r
91 communications per iteration. Compare to the sequential it take
\r
92 3300 s to obtain the same results.
\r
94 After this few works discuses this problem until the apparition of
\r
95 the Compute Unified Device Architecture (CUDA) [19],a parallel
\r
96 computing platform and a programming model invented by NVIDIA. the
\r
97 computing ability of GPU has exceeded the counterpart of CPU. It
\r
98 is a waste of resource to be just a graphics card for GPU. CUDA
\r
99 adopts a totally new computing architecture to use the hardware
\r
100 resources provided by GPU in order to offer a stronger computing
\r
101 ability to the massive data computing.
\r
104 Indeed [16]proposed the implementation of the Durand-Kerner method
\r
105 on GPU (Graphics Processing Unit). The main result prove that a
\r
106 parallel implementation is 10 times as fast as the sequential
\r
107 implementation on a single CPU for high degree polynomials that is
\r
108 greater than about 48000.
\r
110 The mean part of our work is to implement the Aberth method on GPU
\r
111 and compare it with the Durand Kerner
\r
112 implementation.................To be continued..................
\r
116 \bibliographystyle{alpha}
\r
117 \begin{thebibliography}{2}
\r
119 \bibitem [1] {1} O. Aberth, Iteration Methods for Finding
\r
120 all Zeros of a Polynomial Simultaneously, Math. Comput. 27, 122
\r
123 \bibitem [2] {2} Ilieff, L. (1948-50), On the approximations of Newton, Annual
\r
124 Sofia Univ. 46, 167-171.
\r
126 \bibitem [3] {3} Docev, K. (1962), An alternative method of Newton for
\r
127 simultaneous calculation of all the roots of a given algebraic
\r
128 equation, Phys. Math. J., Bulg. Acad. Sci. 5, 136-139.
\r
130 \bibitem [4]{4} Durand, E. (1960), Solution Numerique des Equations
\r
131 Algebriques, Vol. 1, Equations du Type F(x)=0, Racines d'une
\r
132 Polynome. Masson, Paris.
\r
134 \bibitem [4] {4} Aberth, O. (1973), Iterative methods for finding all zeros of
\r
135 a polynomial simultaneously, Math. Comp. 27, 339-344.
\r
137 \bibitem [5] {5} Kerner, I.O. (1966), Ein Gesamtschritteverfahren zur
\r
138 Berechnung der Nullstellen von Polynomen, Numer. Math. 8, 290-294.
\r
140 \bibitem [6]{6} Borch-Supan, W. (1963), A posteriori error for the zeros of
\r
141 polynomials, Numer. Math. 5, 380-398.
\r
143 \bibitem [7] {7} Ehrlich, L. W. (1967), A modified Newton method for
\r
144 polynomials, Comm. Ass. Comput. Mach. 10, 107-108.
\r
148 \bibitem [10] {10}Loizon, G. (1983), Higher-order iteration functions for
\r
149 simultaneously approximating polynomial zeros, Intern. J. Computer
\r
152 \bibitem [11]{11} E. Durand, Solutions num´eriques des ´equations alg´ebriques,
\r
153 Tome 1: Equations du type F(X) = 0; Racines d
\92un polyn
\88ome,
\r
154 Masson, Paris 1960.
\r
156 \bibitem [12] {12} Weierstrass, K. (1903), Neuer Beweis des Satzes, dass
\r
157 jede ganze rationale function einer veranderlichen dagestellt
\r
158 werden kann als ein product aus linearen functionen derselben
\r
159 veranderlichen, Ges. Werke 3, 251-269.
\r
160 \bibitem [13] {13} Freeman, T. L. (1989), Calculating polynomial zeros on a
\r
161 local memory parallel computer, Parallel Computing 12, 351-358.
\r
163 \bibitem [14] {14} Freeman, T. L., Brankin, R. K. (1990), Asynchronous
\r
164 polynomial zero-finding algorithms, Parallel Computing 17,
\r
167 \bibitem [15] {15} Raphaël,C. François,S. (2001), Extraction de racines dans des
\r
168 polynômes creux de degré élevé. RSRCP (Réseaux et Systèmes
\r
169 Répartis, Calculateurs Parallèles), Numéro thématique :
\r
170 Algorithmes itératifs parallèles et distribués, 13(1):67--81.
\r
172 \bibitem [16]{16} Kahina, G. Raphaël, C. Abderrahmane, S. A
\r
173 parallel implementation of the Durand-Kerner algorithm for
\r
174 polynomial root-finding on GPU. In INDS 2014, Int. Conf. on
\r
175 advanced Networking, Distributed Systems and Applications, Bejaia,
\r
176 Algeria, pages 53--57, June 2014. IEEE
\r
178 \end{thebibliography}
\r
