author = "K. Docev",
}x
-@Article{Durand60,
- title = "Solution Numerique des Equations Algebriques, Vol. 1, Equations du Type F(x)=0, Racines d'une Polynome",
- journal = "",
- volume = "Vol.1",
- number = "",
- pages = "",
- year = "1960",
- author = "E. Durand",
-}x
+%@Article{Durand60,
+ % title = "Solution Numerique des Equations Algebriques, Vol. 1, Equations du Type F(x)=0, Racines d'une Polynome",
+ %journal = "",
+% volume = "Vol.1",
+% number = "",
+ % pages = "",
+ %year = "1960",
+ % author = "E. Durand",
+%}x
+@Book{Durand60,
+ author = "\'E. Durand",
+ publisher = "Masson, Paris",
+ title = "Solutions num\'eriques des \'equations alg\'ebriques.
+ {T}ome {I}: \'{E}quations du type {$F(x)=0$}; racines
+ d'un polyn\^ome",
+ year = "1960",
+}x
+
+%@Article{Kerner66,
+ %title = "Ein Gesamtschritteverfahren zur Berechnung der Nullstellen von Polynomen",
+ % journal = "Numerische Mathematik",
+% volume = "8",
+% number = "3",
+% pages = "290-294",
+ %year = "1966",
+ % author = "I. Kerner",
+%}x
+
@Article{Kerner66,
- title = "Ein Gesamtschritteverfahren zur Berechnung der Nullstellen von Polynomen",
- journal = " ",
- volume = "",
- number = "8",
- pages = "290-294",
- year = "1966",
- author = "I. Kerner",
-}x
+ author = "Immo O. Kerner",
+ title = "{Ein Gesamtschrittverfahren zur Berechnung der
+ Nullstellen von Polynomen}. ({German}) [{A} Complete
+ Step Method for the Computation of Zeros of
+ Polynomials]",
+ journal = "Numerische Mathematik",
+ volume = "8",
+ number = "3",
+ pages = "290--294",
+ month = may,
+ year = "1966",
+ CODEN = "NUMMA7",
+ ISSN = "0029-599X (print), 0945-3245 (electronic)",
+ bibdate = "Mon Oct 18 01:28:20 MDT 1999",
+ bibsource = "http://www.math.utah.edu/pub/tex/bib/nummath.bib",
+ acknowledgement = "Nelson H. F. Beebe, University of Utah, Department
+ of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake
+ City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1
+ 801 581 4148, e-mail: \path|beebe@math.utah.edu|,
+ \path|beebe@acm.org|, \path|beebe@computer.org|
+ (Internet), URL:
+ \path|http://www.math.utah.edu/~beebe/|",
+ fjournal = "Numerische Mathematik",
+ journal-url = "http://link.springer.com/journal/211",
+ language = "German",
+}
+%@Article{Borch-Supan63,
+% title = "A posteriori error for the zeros of polynomials",
+ %journal = " Numerische Mathematik",
+ % volume = "5",
+% number = "",
+% pages = "380-398",
+ %year = "1963",
+ % author = "W. Borch-Supan",
+%}x
@Article{Borch-Supan63,
- title = "A posteriori error for the zeros of polynomials",
- journal = " ",
- volume = "",
- number = "5",
- pages = "380-398",
- year = "1963",
- author = "W. Borch-Supan",
-}x
+ author = "W. Boersch-Supan",
+ title = "A Posteriori Error Bounds for the Zeros of
+ Polynomials",
+ journal = "Numerische Mathematik",
+ volume = "5",
+ pages = "380--398",
+ year = "1963",
+ CODEN = "NUMMA7",
+ ISSN = "0029-599X",
+ bibdate = "Fri Jan 12 11:37:56 1996",
+ acknowledgement = "Jon Rokne, Department of Computer Science, The
+ University of Calgary, 2500 University Drive N.W.,
+ Calgary, Alberta T2N 1N4, Canada",
+}
-@Article{Ehrlich67,
- title = "A modified Newton method for polynomials",
- journal = " Comm. Ass. Comput. Mach.",
- volume = "",
- number = "10",
- pages = "107-108",
- year = "1967",
- author = "L.W. Ehrlich",
-}x
+%@Article{Ehrlich67,
+% title = "A modified Newton method for polynomials",
+% journal = " Comm. Ass. Comput. Mach.",
+% volume = "10",
+% number = "2",
+% pages = "107-108",
+ %year = "1967",
+ % author = "L.W. Ehrlich",
+%}x
-@Article{Loizon83,
+@Article{Ehrlich67,
+ title = "A modified Newton method for polynomials",
+ author = "Louis W. Ehrlich",
+ journal = "Commun. ACM",
+ year = "1967",
+ number = "2",
+ volume = "10",
+ bibdate = "2003-11-20",
+ bibsource = "DBLP,
+ http://dblp.uni-trier.de/db/journals/cacm/cacm10.html#Ehrlich67",
+ pages = "107--108",
+ URL = "http://doi.acm.org/10.1145/363067.363115",
+}
+@Article{Loizou83,
title = "Higher-order iteration functions for simultaneously approximating polynomial zeros",
journal = " Intern. J. Computer Math",
- volume = "",
- number = "14",
+ volume = "14",
+ number = "",
pages = "45-58",
year = "1983",
author = "G. Loizon",
@Article{Freeman89,
title = " Calculating polynomial zeros on a local memory parallel computer",
journal = " Parallel Computing",
- volume = "",
- number = "12",
+ volume = "12",
+ number = "",
pages = "351-358",
year = "1989",
author = "T.L. Freeman",
@Article{Freemanall90,
title = " Asynchronous polynomial zero-finding algorithms",
journal = " Parallel Computing",
- volume = "",
- number = "17",
+ volume = "17",
+ number = "",
pages = "673-681",
year = "1990",
author = "T.L. Freeman AND R.K. Brankin",
\subsection{A sequential Ehrlich-Aberth algorithm}
The main steps of Ehrlich-Aberth method are shown in Algorithm.~\ref{alg1-seq} :
-
+%\LinesNumbered
\begin{algorithm}[H]
\label{alg1-seq}
-%\LinesNumbered
+
\caption{A sequential algorithm to find roots with the Ehrlich-Aberth method}
-\KwIn{$Z^{0}$(Initial root's vector),$\varepsilon$ (error tolerance threshold),P(Polynomial to solve)}
-\KwOut {Z(The solution root's vector)}
+\KwIn{$Z^{0}$(Initial root's vector),$\varepsilon$ (error tolerance threshold), P(Polynomial to solve),$\Delta z_{max}$ (maximum value of stop condition),k (number of iteration),n(Polynomial's degrees)}
+\KwOut {Z (The solution root's vector),ZPrec (the previous solution root's vector)}
\BlankLine
Initialization of the coefficients of the polynomial to solve\;
Initialization of the solution vector $Z^{0}$\;
+$\Delta z_{max}=0$\;
+ k=0\;
-\While {$\Delta z_{max}\succ \epsilon$}{
+\While {$\Delta z_{max} > \varepsilon$}{
Let $\Delta z_{max}=0$\;
\For{$j \gets 0 $ \KwTo $n$}{
-$ZPrec\left[j\right]=Z\left[j\right]$\;
-$Z\left[j\right]=H\left(j,Z\right)$\;
+$ZPrec\left[j\right]=Z\left[j\right]$;// save Z at the iteration k.\
+
+$Z\left[j\right]=H\left(j,Z\right)$;//update Z with the iterative function.\
}
+k=k+1\;
\For{$i \gets 0 $ \KwTo $n-1$}{
-$c=\frac{\left|Z\left[i\right]-ZPrec\left[i\right]\right|}{Z\left[i\right]}$\;
+$c= testConverge(\Delta z_{max},ZPrec\left[j\right],Z\left[j\right])$\;
\If{$c > \Delta z_{max}$ }{
$\Delta z_{max}$=c\;}
}
+
}
\end{algorithm}
%\LinesNumbered
\caption{CUDA Algorithm to find roots with the Ehrlich-Aberth method}
-\KwIn{$Z^{0}$(Initial root's vector),$\varepsilon$ (error
-tolerance threshold),P(Polynomial to solve)}
+\KwIn{$Z^{0}$(Initial root's vector),$\varepsilon$ (error tolerance threshold), P(Polynomial to solve), $\Delta z_{max}$ (maximum value of stop condition)}
\KwOut {Z(The solution root's vector)}
Initialization of the coeffcients of the polynomial to solve\;
Initialization of the solution vector $Z^{0}$\;
Allocate and copy initial data to the GPU global memory\;
-
+k=0\;
\While {$\Delta z_{max}\succ \epsilon$}{
Let $\Delta z_{max}=0$\;
-$ kernel\_save(d\_z^{k-1})$\;
-$ kernel\_update(d\_z^{k})$\;
-$kernel\_testConverge(\Delta z_{max},d_z^{k},d_z^{k-1})$\;
+$ kernel\_save(d\_Z^{k-1})$\;
+k=k+1\;
+$ kernel\_update(d\_Z^{k})$\;
+$kernel\_testConverge(\Delta z_{max},d\_Z^{k},d\_Z^{k-1})$\;
+
}
\end{algorithm}
~\\
