From c5f581ffe6e32e34c3fb1048707698d5d4b67c53 Mon Sep 17 00:00:00 2001 From: Kahina Guidouche Date: Mon, 24 Aug 2015 09:22:57 +0200 Subject: [PATCH] commit Root.tex the first part for the paper --- Root.tex | 179 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 179 insertions(+) create mode 100644 Root.tex diff --git a/Root.tex b/Root.tex new file mode 100644 index 0000000..c2359b7 --- /dev/null +++ b/Root.tex @@ -0,0 +1,179 @@ +\documentclass[11pt,a4paper]{article} +\usepackage[latin1]{inputenc} +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\author{ghidouche} +\title{Paper1_kahina} +\begin{document} +\section{Root finding problem} +we consider a polynomial of degree \textit{n} having coefficients +in the complex \textit{C} and zeros $\alpha +_{i},\textit{i=1,...,n}$. \\ +\begin{center} + {\Large$p(x)=\sum{a_{i}x^{i}}=a_{n}\prod(x-\alpha_{i}), +a_{0}a_{n}\neq0,$} +\end{center} + + the root finding problem consist to find +all n root of \textit{p(x)}. the problem of finding a root is +equivalent to the problem of finding a fixed-point. To see this +consider the fixed-point problem of finding the n-dimensional +vector x such that +\begin{center} +$x=g(x). $ +\end{center} +where $g : C^{n}\longrightarrow C^{n}$. Note that we can easily +rewrite this fixed-point problem as a root-finding problem by +setting $f (x) = x-g(x)$ and likewise we can recast the +root-finding problem into a fixed-point problem by setting +\begin{center} +$g(x)= f(x)-x$ +\end{center} +Often it will not be possible to solve such nonlinear equation +root-finding problems analytically. When this occurs we turn to +numerical methods to approximate the solution. Generally speaking, +algorithms for solving problems numerically can be divided into +two main groups: direct methods and iterative methods. +\\ + Direct methods exist only for $n \leqslant4$,solved in closed form by G. Cardano +in the mid-16th century. However, N.H. Abel in the early 19th +century showed that polynomials of degree five or more could not +be solved by directs methods. Since then researchers have +concentrated on numerical (iterative) methods such as the famous +Newton s method, Bernoulli s method of the 18th, and Graeffe s. +With the advent of electronic computers, different methods has +been developed such as the Jenkins-Traub method, Larkin s method, +Muller s method, and several methods for simultaneous +approximation of all the roots, starting with the Durand-Kerner +method: +\begin{center} + +$ Z_{i}=Z_{i}-\frac{P(Z_{i})}{\prod_{i\neq j}(z_{i}-z_{j})} $ +\end{center} + +This formula is mentioned for the first time from Weiestrass [12] +as part of the fundamental theorem of Algebra and is rediscovered +from Ilieff [2], Docev [3], Durand [4], Kerner [5]. Another method +discovered from Borsch-Supan [6] and also described and brought in +the following form from Ehrlich [7] and Aberth [8] +\begin{center} + +$ Z_{i}=Z_{i}-\frac{1}{{\frac {P'(Z_{i})} +{P(Z_{i})}}-{\sum_{i\neq j}(z_{i}-z_{j})}} $ +\end{center} + +Aberth, Ehrlich and Farmer-Loizou [10] have proved that the above +method has cubic order of convergence for simple roots. + + +Iterative methods raise several problem when implemented e.g. +specific sizes of numbers must be used to deal with this +difficulty.Moreover,the convergence time of iterative methods +drastically increase like the degrees of high polynomials. The +parallelization of these algorithms will improve the convergence +time. + +Many authors have treated the problem of parallelization of +simultaneous methods. Freeman [13] has tested the DK method, EA +method and another method of the fourth order proposed from Farmer +and Loizou [10],on a 8- processor linear chain, for polynomial of +degree up to 8. The third method often diverges, but the first two +methods have speed-up 5.5 (speed-up=(Time on one processor)/(Time +on p processors)). Later Freeman and Bane [14] consider +asynchronous algorithms, in which each processor continues to +update its approximations even although the latest values of other +$z_i((k))$ have not received from the other processors, in +difference with the synchronous version where it would wait. in +[15]proposed two methods of parallelization for architecture with +shared memory and distributed memory,it able to compute the root +of polynomial degree 10000 on 430 s with only 8 pc and 2 +communications per iteration. Compare to the sequential it take +3300 s to obtain the same results. + +After this few works discuses this problem until the apparition of +the Compute Unified Device Architecture (CUDA) [19],a parallel +computing platform and a programming model invented by NVIDIA. the +computing ability of GPU has exceeded the counterpart of CPU. It +is a waste of resource to be just a graphics card for GPU. CUDA +adopts a totally new computing architecture to use the hardware +resources provided by GPU in order to offer a stronger computing +ability to the massive data computing. + + +Indeed [16]proposed the implementation of the Durand-Kerner method +on GPU (Graphics Processing Unit). The main result prove that a +parallel implementation is 10 times as fast as the sequential +implementation on a single CPU for high degree polynomials that is +greater than about 48000. +\paragraph{} +The mean part of our work is to implement the Aberth method on GPU +and compare it with the Durand Kerner +implementation.................To be continued.................. + + + +\bibliographystyle{alpha} +\begin{thebibliography}{2} + +\bibitem [1] {1} O. Aberth, Iteration Methods for Finding +all Zeros of a Polynomial Simultaneously, Math. Comput. 27, 122 +(1973) 339–344. + +\bibitem [2] {2} Ilieff, L. (1948-50), On the approximations of Newton, Annual +Sofia Univ. 46, 167-171. + +\bibitem [3] {3} Docev, K. (1962), An alternative method of Newton for +simultaneous calculation of all the roots of a given algebraic +equation, Phys. Math. J., Bulg. Acad. Sci. 5, 136-139. + +\bibitem [4]{4} Durand, E. (1960), Solution Numerique des Equations +Algebriques, Vol. 1, Equations du Type F(x)=0, Racines d'une +Polynome. Masson, Paris. + +\bibitem [4] {4} Aberth, O. (1973), Iterative methods for finding all zeros of +a polynomial simultaneously, Math. Comp. 27, 339-344. + +\bibitem [5] {5} Kerner, I.O. (1966), Ein Gesamtschritteverfahren zur +Berechnung der Nullstellen von Polynomen, Numer. Math. 8, 290-294. + +\bibitem [6]{6} Borch-Supan, W. (1963), A posteriori error for the zeros of +polynomials, Numer. Math. 5, 380-398. + +\bibitem [7] {7} Ehrlich, L. W. (1967), A modified Newton method for +polynomials, Comm. Ass. Comput. Mach. 10, 107-108. + + + +\bibitem [10] {10}Loizon, G. (1983), Higher-order iteration functions for +simultaneously approximating polynomial zeros, Intern. J. Computer +Math. 14, 45-58. + +\bibitem [11]{11} E. Durand, Solutions num´eriques des ´equations alg´ebriques, +Tome 1: Equations du type F(X) = 0; Racines d’un polynˆome, +Masson, Paris 1960. + +\bibitem [12] {12} Weierstrass, K. (1903), Neuer Beweis des Satzes, dass +jede ganze rationale function einer veranderlichen dagestellt +werden kann als ein product aus linearen functionen derselben +veranderlichen, Ges. Werke 3, 251-269. +\bibitem [13] {13} Freeman, T. L. (1989), Calculating polynomial zeros on a +local memory parallel computer, Parallel Computing 12, 351-358. + +\bibitem [14] {14} Freeman, T. L., Brankin, R. K. (1990), Asynchronous +polynomial zero-finding algorithms, Parallel Computing 17, +673-681. + +\bibitem [15] {15} Raphaël,C. François,S. (2001), Extraction de racines dans des +polynômes creux de degré élevé. RSRCP (Réseaux et Systèmes +Répartis, Calculateurs Parallèles), Numéro thématique : +Algorithmes itératifs parallèles et distribués, 13(1):67--81. + +\bibitem [16]{16} Kahina, G. Raphaël, C. Abderrahmane, S. A +parallel implementation of the Durand-Kerner algorithm for +polynomial root-finding on GPU. In INDS 2014, Int. Conf. on +advanced Networking, Distributed Systems and Applications, Bejaia, +Algeria, pages 53--57, June 2014. IEEE + +\end{thebibliography} +\end{document} -- 2.39.5