this is the commit 06.09.15

[kahina_paper1.git] / Root.tex

diff --git a/Root.tex b/Root.tex
index c2359b76ae17d99f8997ad89d2235d5153a8dd13..2ee2c28e0c2d2e7ad23bd0c641a5c20d38d19c93 100644 (file)
--- a/Root.tex
+++ b/Root.tex
@@ -54,9 +54,10 @@ $  Z_{i}=Z_{i}-\frac{P(Z_{i})}{\prod_{i\neq j}(z_{i}-z_{j})} $
 \r
 This formula is mentioned for the first time from Weiestrass [12]\r
 as part of the fundamental theorem of Algebra and is rediscovered\r
 \r
 This formula is mentioned for the first time from Weiestrass [12]\r
 as part of the fundamental theorem of Algebra and is rediscovered\r

-from Ilieff [2], Docev [3], Durand [4], Kerner [5]. Another method\r
-discovered from Borsch-Supan [6] and also described and brought in\r
-the following form from Ehrlich [7] and Aberth [8]\r
+from Ilieff~\cite{Ilief50} [2], Docev [3], Durand [4], Kerner [5].\r
+Another method discovered from Borsch-Supan [6] and also described\r
+and brought in the following form from Ehrlich [7] and\r
+Aberth~\cite{Aberth73}.\r

 \begin{center}\r
 \r
 $  Z_{i}=Z_{i}-\frac{1}{{\frac {P'(Z_{i})}\r
 \begin{center}\r
 \r
 $  Z_{i}=Z_{i}-\frac{1}{{\frac {P'(Z_{i})}\r


@@ -112,68 +113,164 @@ and compare it with the Durand Kerner
 implementation.................To be continued..................\r
 \r
 \r
 implementation.................To be continued..................\r
 \r
 \r

+\section{Aberth method and difficulties}\r
+A cubically convergent iteration method for finding zeros of\r
+polynomials was proposed by O.Aberth[?].The Aberth method is a\r
+purely algebraic derivation.To illustrate the derivation, we let\r
+$w_{i}(z)$ be the product of linear factor $ w_{i}(z)=\prod_{j=1,j\r
+\neq i}^{n} (z-x_{j})$\r

 \r
 \r

-\bibliographystyle{alpha}\r
-\begin{thebibliography}{2}\r
+and rational function $R_{i}(z)$ be the correction term of\r
+Weistrass method (?)\r
+$$R_{i}(z)=\dfrac{p(z)}{w_{i}(Z)} , i=1,2,...,n. $$\r

 \r
 \r

-\bibitem [1] {1} O. Aberth, Iteration Methods for Finding\r
-all Zeros of a Polynomial Simultaneously, Math. Comput. 27, 122\r
-(1973) 339\96344.\r
+Differentiating the rational function $R_{i}(z)$ and applying the\r
+Newton method, we have\r
+$$\dfrac{R_{i}(z)}{R_{i}^{'}(z)}= \dfrac{p(z)}{p^{'}(z)-p(z)\dfrac{w_{i}(z)}{w_{i}^{'}(z)}}= \dfrac{p(z)}{p^{'}(z)-p(z) \sum _{j=1,j \neq i}^{n}\dfrac{1}{z-x_{i}}}, i=1,2,...,n $$\r
+Substituting $x_{j}$ for z we obtain the Aberth iteration method\r

 \r
 \r

-\bibitem [2] {2} Ilieff, L. (1948-50), On the approximations of Newton, Annual\r
-Sofia Univ. 46, 167-171.\r
+Let present the means stages of Aberth's method.\r

 \r
 \r

-\bibitem [3] {3} Docev, K. (1962), An alternative method of Newton for\r
-simultaneous calculation of all the roots of a given algebraic\r
-equation, Phys. Math. J., Bulg. Acad. Sci. 5, 136-139.\r
+\subsection{Polynomials Initialization}\r
+ The initialization of polynomial P(z) with complex coefficients\r
+ are given by:\r
+ $$ p(z)=\sum{a_{i}z^{n-i}}. where a_{n} \neq 0,a_{0}=1, a_{i}\subset C $$\r

 \r
 \r

-\bibitem [4]{4} Durand, E. (1960), Solution Numerique des Equations\r
-Algebriques, Vol. 1, Equations du Type F(x)=0, Racines d'une\r
-Polynome. Masson, Paris.\r

 \r
 \r

-\bibitem [4]  {4} Aberth, O. (1973), Iterative methods for finding all zeros of\r
-a polynomial simultaneously, Math. Comp. 27, 339-344.\r
+\subsection{Vector $Z^{0)}$ Initialization}\r

 \r
 \r

-\bibitem [5] {5} Kerner, I.O. (1966), Ein Gesamtschritteverfahren zur\r
-Berechnung der Nullstellen von Polynomen, Numer. Math. 8, 290-294.\r
+The choice of the initial points $z^{(0)}_{i} , i = 1, . . . , n,$\r
+from which starting the iteration  (2) or (3), is rather delicate\r
+since the number of steps needed by the iterative method to reach\r
+a given approximation strongly depends on it. In [1] the Aberth\r
+iteration is started by selecting n equispaced points on a circle\r
+of center 0 and radius r, where r is an upper bound to the moduli\r
+of the zeros. After[18]  performs this choice by selecting complex\r
+numbers along different circles and relies on the result of [19].\r

 \r
 \r

-\bibitem [6]{6} Borch-Supan, W. (1963), A posteriori error for the zeros of\r
-polynomials, Numer. Math. 5, 380-398.\r
+$$\sigma_{0}=\frac{u+v}{2};u=\frac{\sum_{i=1}^{n}u_{i}}{n.max_{i=1}^{n}u_{i}}; v=\frac{\sum_{i=0}^{n-1}v_{i}}{n.min_{i=0}^{n-1}v_{i}};u_{i}=2.|a_{i}|^{\frac{1}{i}}; v_{i}=\frac{|\frac{a_{n}}{a_{i}}|^{\frac{1}{n-i}}}{2} $$\r

 \r
 \r

-\bibitem [7] {7} Ehrlich, L. W. (1967), A modified Newton method for\r
-polynomials, Comm. Ass. Comput. Mach. 10, 107-108.\r
+\subsection{Iterative Function Hi}\r
+The operator used with Aberth's method is corresponding to the\r
+following equation which will enable the convergence towards\r
+polynomial solutions, provided all the roots are distinct.\r

 \r
 \r

+$$ H_{i}(z)=z_{i}-\frac{1}{\frac{P^{'}(z_{i})}{P(z_{i})}-\sum_{j\neq i}{\frac{1}{z_{i}-z_{j}}}} $$\r

 \r
 \r

+\subsection{Convergence condition}\r
+determines the success of the termination. It consists in stopping\r
+the iterative function $H_{i}(z)$ when the are stable,the method\r
+converge sufficiently:\r
+$$  \forall i \in [1,n]; \frac{z_{i}^{(k)}-z_{i}^{(k-1)}}{z_{i}^{(k)}}< \xi$$\r

 \r
 \r

-\bibitem [10] {10}Loizon, G. (1983), Higher-order iteration functions for\r
-simultaneously approximating polynomial zeros, Intern. J. Computer\r
-Math. 14, 45-58.\r
+\section{Difficulties and amelioration}\r
+the Aberth method implementation suffer of overflow problems. This\r
+situation occurs, for instance, in the case where a polynomial\r
+having positive coefficients and large degree is computed at a\r
+point $\xi$ where $|\xi| > 1$.Indeed the limited number in the\r
+mantissa of floating takings the computation of P(z) wrong when z\r
+is large. for example $(10^{50}) +1+ (- 10_{50})$ will give result\r
+0 instead of 1 in reality.consequently we can't compute the roots\r
+for large polynomial's degree. This problem was discuss in [17]\r
+for the Durand-Kerner method, the authors propose to use the\r
+logratihm and the exponential of a complex:\r

 \r
 \r

-\bibitem [11]{11} E. Durand, Solutions num´eriques des ´equations alg´ebriques,\r
-Tome 1: Equations du type F(X) = 0; Racines d\92un polyn\88ome,\r
-Masson, Paris 1960.\r
+$$ \forall(x,y)\in R^{*2}; \ln (x+i.y)=\ln(x^{2}+y^{2}) 2+i.\arcsin(y\sqrt{x^{2}+y^{2}})_{\left] -\pi, \pi\right[ } $$\r
+$$ \forall(x,y)\in R^{*2}; \exp(x+i.y)= \exp(x).\exp(i.y)$$\r
+$$                                       =\exp(x).\cos(y)+i.\exp(x).\sin(y)$$\r

 \r
 \r

-\bibitem [12] {12} Weierstrass, K. (1903), Neuer Beweis des Satzes, dass\r
-jede ganze rationale function einer veranderlichen dagestellt\r
-werden kann als ein product aus linearen functionen derselben\r
-veranderlichen, Ges. Werke 3, 251-269.\r
-\bibitem [13] {13} Freeman, T. L. (1989), Calculating polynomial zeros on a\r
-local memory parallel computer, Parallel Computing 12, 351-358.\r

 \r
 \r

-\bibitem [14] {14} Freeman, T. L., Brankin, R. K. (1990), Asynchronous\r
-polynomial zero-finding algorithms, Parallel Computing 17,\r
-673-681.\r
+The application of logarithm can replace any multiplications and\r
+divisions with additions and subtractions; consequently it\r
+manipulates lower absolute values and can be compute the roots for\r
+large polynomial's degree exceed 1000[17].\r

 \r
 \r

-\bibitem [15] {15} Raphaël,C. François,S. (2001), Extraction de racines dans des\r
-polynômes creux de degré élevé. RSRCP (Réseaux et Systèmes\r
-Répartis, Calculateurs Parallèles), Numéro thématique :\r
-Algorithmes itératifs parallèles et distribués, 13(1):67--81.\r
+Applying this solution for the Aberth method we obtain the\r
+iteration function with logarithm:\r
+%%$$ \exp \bigl(  \ln(p(z)_{k})-ln(\ln(p(z)_{k}^{'}))- \ln(1- \exp(\ln(p(z)_{k})-ln(\ln(p(z)_{k}^{'})+\ln\sum_{i\neq j}^{n}\frac{1}{z_{k}-z_{j}})$$\r

 \r
 \r

-\bibitem [16]{16} Kahina, G. Raphaël, C. Abderrahmane, S. A\r
-parallel implementation of the Durand-Kerner algorithm for\r
-polynomial root-finding on GPU. In INDS 2014, Int. Conf. on\r
-advanced Networking, Distributed Systems and Applications, Bejaia,\r
-Algeria, pages 53--57, June 2014. IEEE\r
+$$ H_{i}(z)=z_{i}^{k}-\exp \left(\ln \left( p(z_{k})\right)-\ln\left(p(z_{k}^{'})\right)- \ln\left(1- \exp\left( \ln (p(z_{k}))-\ln(p(z_{k}^{'}))+\ln \left( \sum_{k\neq j}^{n}\frac{1}{z_{k}-z_{j}}\right)\right) \right) \right)$$\r

 \r
 \r

-\end{thebibliography}\r
+\r
+\r
+this solution is applying when it is necessary\r
+\r
+\section{The implementation of simultaneous methods in a parallel computer}\r
+\r
+\r
+\bibliographystyle{plain}\r
+\bibliography{biblio}\r
+%% \begin{thebibliography}{2}\r
+\r
+%% \bibitem [1] {1} O. Aberth, Iteration Methods for Finding\r
+\r
+\r
+%% all Zeros of a Polynomial Simultaneously, Math. Comput. 27, 122\r
+%% (1973) 339\96344.\r
+\r
+%% \bibitem [2] {2} Ilieff, L. (1948-50), On the approximations of Newton, Annual\r
+%% Sofia Univ. 46, 167-171.\r
+\r
+%% \bibitem [3] {3} Docev, K. (1962), An alternative method of Newton for\r
+%% simultaneous calculation of all the roots of a given algebraic\r
+%% equation, Phys. Math. J., Bulg. Acad. Sci. 5, 136-139.\r
+\r
+%% \bibitem [4]{4} Durand, E. (1960), Solution Numerique des Equations\r
+%% Algebriques, Vol. 1, Equations du Type F(x)=0, Racines d'une\r
+%% Polynome. Masson, Paris.\r
+\r
+%% \bibitem [4]  {4} Aberth, O. (1973), Iterative methods for finding all zeros of\r
+%% a polynomial simultaneously, Math. Comp. 27, 339-344.\r
+\r
+%% \bibitem [5] {5} Kerner, I.O. (1966), Ein Gesamtschritteverfahren zur\r
+%% Berechnung der Nullstellen von Polynomen, Numer. Math. 8, 290-294.\r
+\r
+%% \bibitem [6]{6} Borch-Supan, W. (1963), A posteriori error for the zeros of\r
+%% polynomials, Numer. Math. 5, 380-398.\r
+\r
+%% \bibitem [7] {7} Ehrlich, L. W. (1967), A modified Newton method for\r
+%% polynomials, Comm. Ass. Comput. Mach. 10, 107-108.\r
+\r
+\r
+\r
+%% \bibitem [10] {10}Loizon, G. (1983), Higher-order iteration functions for\r
+%% simultaneously approximating polynomial zeros, Intern. J. Computer\r
+%% Math. 14, 45-58.\r
+\r
+%% \bibitem [11]{11} E. Durand, Solutions numŽeriques des Žequations algŽebriques,\r
+%% Tome 1: Equations du type F(X) = 0; Racines d\92un polyn\88ome,\r
+%% Masson, Paris 1960.\r
+\r
+%% \bibitem [12] {12} Weierstrass, K. (1903), Neuer Beweis des Satzes, dass\r
+%% jede ganze rationale function einer veranderlichen dagestellt\r
+%% werden kann als ein product aus linearen functionen derselben\r
+%% veranderlichen, Ges. Werke 3, 251-269.\r
+%% \bibitem [13] {13} Freeman, T. L. (1989), Calculating polynomial zeros on a\r
+%% local memory parallel computer, Parallel Computing 12, 351-358.\r
+\r
+%% \bibitem [14] {14} Freeman, T. L., Brankin, R. K. (1990), Asynchronous\r
+%% polynomial zero-finding algorithms, Parallel Computing 17,\r
+%% 673-681.\r
+\r
+%% \bibitem [15] {15} Raphaël,C. François,S. (2001), Extraction de racines dans des\r
+%% polynômes creux de degré élevé. RSRCP (Réseaux et Systèmes\r
+%% Répartis, Calculateurs Parallèles), Numéro thématique :\r
+%% Algorithmes itératifs parallèles et distribués, 13(1):67--81.\r
+\r
+%% \bibitem [16]{16} Kahina, G. Raphaël, C. Abderrahmane, S. A\r
+%% parallel implementation of the Durand-Kerner algorithm for\r
+%% polynomial root-finding on GPU. In INDS 2014, Int. Conf. on\r
+%% advanced Networking, Distributed Systems and Applications, Bejaia,\r
+%% Algeria, pages 53--57, June 2014. IEEE\r
+\r
+%% \bibitem [17] {17} Karim Rhofir, François Spies, and Jean-Claude Miellou.\r
+%%Perfectionnements de la méthode asynchrone de Durand-Kerner pour\r
+%%les polynômes complexes. Calculateurs Parallèles, 10(4):449-- 458,\r
+%%1998.\r
+%% \bibitem [18] {18} Bini, D. A. Numerical computation of polynomial zeros by\r
+%%means of Aberth\92s method. Numerical Algorithms 13 (1996), 179\96\r
+%%200.\r
+%% \bibitem [19] {19} A. Ostrowski, On a Theorem by J.L. Walsh Concerning the Moduli of Roots of Algebraic Equations,\r
+%%Bull. A.M.S., 47 (1941) 742\96746.\r
+%% \end{thebibliography}\r

 \end{document}\r
 \end{document}\r