From: Kahina Date: Mon, 2 Nov 2015 13:13:13 +0000 (+0100) Subject: MAJ Mybibfile X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/kahina_paper1.git/commitdiff_plain/0cf063826e3d100cb00eaa4b104306a581de2ac3?hp=c90f146cdefa047c69990e5c0d1891ef6def1bc2 MAJ Mybibfile --- diff --git a/mybibfile.bib b/mybibfile.bib index 2347318..d29bcb2 100644 --- a/mybibfile.bib +++ b/mybibfile.bib @@ -53,51 +53,116 @@ 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", @@ -106,8 +171,8 @@ @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", @@ -116,8 +181,8 @@ @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", diff --git a/paper.tex b/paper.tex index c78df7b..4213238 100644 --- a/paper.tex +++ b/paper.tex @@ -493,32 +493,37 @@ read-only caches. \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} @@ -555,8 +560,7 @@ Algorithm~\ref{alg2-cuda} shows a sketch of the Ehrlich-Aberth algorithm using C %\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)} @@ -565,12 +569,14 @@ tolerance threshold),P(Polynomial to solve)} 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} ~\\