}x
-
@Article{Ilie50,
title = "On the approximations of Newton",
journal = "Annual Sofia Univ",
- volume = "",
- number = "46",
+ volume = "46",
+ number = "",
pages = "167--171",
year = "1950",
doi = "10.1016/0003-4916(63)90068-X",
author = "L. Ilieff",
}x
+
@Article{Docev62,
title = "An alternative method of Newton for simultaneous calculation of all the roots of a given algebraic equation",
journal = "Phys. Math. J",
- volume = "",
- number = "5",
+ volume = "5",
+ number = "",
pages = "136-139",
year = "1962",
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
@Book{Durand60,
author = "\'E. Durand",
publisher = "Masson, Paris",
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,
author = "Immo O. Kerner",
title = "{Ein Gesamtschrittverfahren zur Berechnung der
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,
author = "W. Boersch-Supan",
Calgary, Alberta T2N 1N4, Canada",
}
-%@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{Ehrlich67,
title = "A modified Newton method for polynomials",
author = "Louis W. Ehrlich",
year = "2006",
author = "PK. Jana",
}x
-@Article{Kalantari08,
- title = " Polynomial root finding and polynomiography.",
- journal = " World Scientifict,New Jersey",
- volume = "",
- number = "",
- pages = "",
- year = "",
- author = "B. Kalantari",
-}x
-@Article{Gemignani07,
- title = " Structured matrix methods for polynomial root finding.",
- journal = " n: Proc of the 2007 Intl symposium on symbolic and algebraic computation",
- volume = "",
- number = "",
- pages = "175-180",
- year = "2007",
- author = "L. Gemignani",
-}x
+@Book{Kalantari08,
+ALTauthor = {B. Kalantari},
+title = {Polynomial root finding and polynomiography.},
+publisher = {World Scientifict,New Jersey},
+year = {2008},
+OPTkey = {•},
+OPTvolume = {•},
+OPTnumber = {•},
+OPTseries = {•},
+OPTaddress = {•},
+OPTmonth = {December},
+OPTnote = {•},
+OPTannote = {•}
+}
+
+
+@InProceedings{Gemignani07,
+ author = "Luca Gemignani",
+ title = "Structured matrix methods for polynomial
+ root-finding",
+ editor = "C. W. Brown",
+ booktitle = "Proceedings of the 2007 International Symposium on
+ Symbolic and Algebraic Computation, July 29--August 1,
+ 2007, University of Waterloo, Waterloo, Ontario,
+ Canada",
+ publisher = "ACM Press",
+ address = "pub-ACM:adr",
+ ISBN = "1-59593-743-9 (print), 1-59593-742-0 (CD-ROM)",
+ isbn-13 = "978-1-59593-743-8 (print), 978-1-59593-742-1
+ (CD-ROM)",
+ pages = "175--180",
+ year = "2007",
+ doi = "http://doi.acm.org/10.1145/1277548.1277573",
+ bibdate = "Fri Jun 20 08:46:50 MDT 2008",
+ bibsource = "http://portal.acm.org/;
+ http://www.math.utah.edu/pub/tex/bib/issac.bib",
+ abstract = "In this paper we discuss the use of structured matrix
+ methods for the numerical approximation of the zeros of
+ a univariate polynomial. In particular, it is shown
+ that root-finding algorithms based on floating-point
+ eigenvalue computation can benefit from the structure
+ of the matrix problem to reduce their complexity and
+ memory requirements by an order of magnitude.",
+ 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/|",
+ keywords = "complexity; eigenvalue computation; polynomial
+ root-finding; rank-structured matrices",
+ doi-url = "http://dx.doi.org/10.1145/1277548.1277573",
+}
@Article{Skachek08,
author = "V. Skachek",
}x
-@BOOK{Skachek008,
- AUTHOR = {V. Skachek},
- editor = {\7f},
- TITLE = {Probabilistic algorithm for finding roots of linearized polynomials},
- PUBLISHER = {codes and cryptography. Kluwer},
- YEAR = {2008},
- volume = {\7f},
- number = {\7f},
- series = {\7f},
- address = {\7f},
- edition = {Design},
- month = {\7f},
- note = {\7f},
- abstract = {\7f},
- isbn = {\7f},
- price = {\7f},
- keywords = {\7f},
- source = {\7f},
-}x
+@Article{Skachek008,
+ title = "Probabilistic algorithm for finding roots of
+ linearized polynomials",
+ author = "Vitaly Skachek and Ron M. Roth",
+ journal = "Des. Codes Cryptography",
+ year = "2008",
+ number = "1",
+ volume = "46",
+ bibdate = "2008-03-11",
+ bibsource = "DBLP,
+ http://dblp.uni-trier.de/db/journals/dcc/dcc46.html#SkachekR08",
+ pages = "17--23",
+ URL = "http://dx.doi.org/10.1007/s10623-007-9125-y",
+}
@Article{Zhancall08,
title = " A constrained learning algorithm for finding multiple real roots of polynomial",
}x
-@Article{Zhuall08,
- title = " an adaptive algorithm finding multiple roots of polynomials",
- journal = " Lect Notes Comput Sci ",
- volume = "",
- number = "5262",
- pages = "674-681",
- year = "2008",
- author = "W. Zhu AND w. Zeng AND D. Lin",
-}x
+@InProceedings{Zhuall08,
+ title = "An Adaptive Algorithm Finding Multiple Roots of Polynomials",
+ author = "Wei Zhu and Zhe-zhao Zeng and Dong-mei Lin",
+ bibdate = "2008-09-25",
+ bibsource = "DBLP,
+ http://dblp.uni-trier.de/db/conf/isnn/isnn2008-2.html#ZhuZL08",
+ booktitle = "ISNN (2)",
+ publisher = "Springer",
+ year = "2008",
+ volume = "5264",
+ editor = "Fuchun Sun and Jianwei Zhang 0001 and Ying Tan and
+ Jinde Cao and Wen Yu 0001",
+ ISBN = "978-3-540-87733-2",
+ pages = "674--681",
+ series = "Lecture Notes in Computer Science",
+ URL = "http://dx.doi.org/10.1007/978-3-540-87734-9_77",
+}
+
@Article{Azad07,
title = " The performance of synchronous parallel polynomial root extraction on a ring multicomputer",
journal = " Clust Comput ",
@Article{Bini04,
title = " Inverse power and Durand Kerner iterations for univariate polynomial root finding",
journal = " Comput Math Appl ",
- volume = "",
- number = "47",
+ volume = "47",
+ number = "",
pages = "447-459",
year = "2004",
author = "DA. Bini AND L. Gemignani",
year = "1903",
author = "K. Weierstrass",
}x
+@Manual{NVIDIA10,
+title = {NVIDIA CUDA C Programming Guide},
+OPTkey = {•},
+OPTauthor = {NVIDIA Corporation},
+OPTorganization = {Design Guide},
+OPTaddress = {•},
+OPTedition = {•},
+OPTmonth = {march},
+OPTyear = {2015},
+OPTnote = {•},
+OPTannote = {•}
+}
-@BOOK{NVIDIA10,
- AUTHOR = {NVIDIA},
- editor = {Design Guide},
- TITLE = {NVIDIA CUDA C Programming Guide},
- PUBLISHER = {PG},
- YEAR = {2015},
- volume = {7},
- number = {02829},
- series = {001},
- month = {march},
-}x
where $P'(z)$ is the polynomial derivative of $P$ evaluated in the
point $z$.
-Aberth, Ehrlich and Farmer-Loizou~\cite{Loizon83} have proved that
+Aberth, Ehrlich and Farmer-Loizou~\cite{Loizou83} have proved that
the Ehrlich-Aberth method (EA) has a cubic order of convergence for simple roots whereas the Durand-Kerner has a quadratic order of convergence.
Many authors have dealt with the parallelization of
simultaneous methods, i.e. that find all the zeros simultaneously.
Freeman~\cite{Freeman89} implemented and compared DK, EA and another method of the fourth order proposed
-by Farmer and Loizou~\cite{Loizon83}, on a 8-processor linear
+by Farmer and Loizou~\cite{Loizou83}, on a 8-processor linear
chain, for polynomials of degree up to 8. The third method often
diverges, but the first two methods have speed-up equal to 5.5. Later,
Freeman and Bane~\cite{Freemanall90} considered asynchronous
\begin{align}
\label{defexpcomplex}
\forall(x,y)\in R^{*2}; \exp(x+i.y) & = \exp(x).\exp(i.y)\\
- & =\exp(x).\cos(y)+i.\exp(x).\sin(y)\label{defexpcomplex}
+ & =\exp(x).\cos(y)+i.\exp(x).\sin(y)\label{defexpcomplex1}
\end{align}
%%\end{equation}
\subsection{The execution time in seconds of Ehrlich-Aberth algorithm on CPU OpenMP (1 core, 4 cores) vs. on a Tesla GPU}
-%\begin{figure}[H]
-%\centering
- % \includegraphics[width=0.8\textwidth]{figures/Compar_EA_algorithm_CPU_GPU}
-%\caption{The execution time in seconds of Ehrlich-Aberth algorithm on CPU core vs. on a Tesla GPU}
-%\label{fig:01}
-%\end{figure}
\begin{figure}[H]
\centering
\centering
\includegraphics[width=0.8\textwidth]{figures/influence_nb_threads}
\caption{Influence of the number of threads on the execution times of different polynomials (sparse and full)}
-\label{fig:01}
+\label{fig:02}
\end{figure}
The figure 2 show that, the best execution time for both sparse and full polynomial are given when the threads number varies between 64 and 256 threads per bloc. We notice that with small polynomials the best number of threads per block is 64, Whereas, the large polynomials the best number of threads per block is 256. However,In the following experiments we specify that the number of thread by block is 256.
\centering
\includegraphics[width=0.8\textwidth]{figures/sparse_full_explog}
\caption{The impact of exp-log solution to compute very high degrees of polynomial.}
-\label{fig:01}
+\label{fig:03}
\end{figure}
The figure 3, show a comparison between the execution time of the Ehrlich-Aberth algorithm applying exp.log solution and the execution time of the Ehrlich-Aberth algorithm without applying exp.log solution, with full and sparse polynomials degrees. We can see that the execution time for the both algorithms are the same while the full polynomials degrees are less than 4000 and full polynomials are less than 150,000. After,we show clearly that the classical version of Ehrlich-Aberth algorithm (without applying log.exp) stop to converge and can not solving any polynomial sparse or full. In counterpart, the new version of Ehrlich-Aberth algorithm (applying log.exp solution) can solve very high and large full polynomial exceed 100,000 degrees.
in fact, when the modulus of the roots are up than \textit{R} given in ~\ref{R},this exceed the limited number in the mantissa of floating points representations and can not compute the iterative function given in ~\ref{eq:Aberth-H-GS} to obtain the root solution, who justify the divergence of the classical Ehrlich-Aberth algorithm. However, applying log.exp solution given in ~\ref{sec2} took into account the limit of floating using the iterative function in(Eq.~\ref{Log_H1},Eq.~\ref{Log_H2} and allows to solve a very large polynomials degrees .
-%\begin{figure}[H]
-\%centering
- %\includegraphics[width=0.8\textwidth]{figures/log_exp_Sparse}
-%\caption{The impact of exp-log solution to compute very high degrees of polynomial.}
-%\label{fig:01}
-%\end{figure}
-
-%we report the performances of the exp.log for the Ehrlich-Aberth algorithm for solving very high degree of polynomial.
-
\subsection{A comparative study between Ehrlich-Aberth algorithm and Durand-kerner algorithm}
In this part, we are interesting to compare the simultaneous methods, Ehrlich-Aberth and Durand-Kerner in parallel computer using GPU. We took into account the execution time, the number of iteration and the polynomial's size. for the both sparse and full polynomials.
\centering
\includegraphics[width=0.8\textwidth]{figures/EA_DK}
\caption{The execution time of Ehrlich-Aberth versus Durand-Kerner algorithm on GPU}
-\label{fig:01}
+\label{fig:04}
\end{figure}
This figure show the execution time of the both algorithm EA and DK with sparse polynomial degrees ranging from 1000 to 1000000. We can see that the Ehrlich-Aberth algorithm are faster than Durand-Kerner algorithm, with an average of 25 times as fast. Then, when degrees of polynomial exceed 500000 the execution time with EA is of the order 100 whereas DK passes in the order 1000. %with double precision not exceed $10^{-5}$.
\centering
\includegraphics[width=0.8\textwidth]{figures/EA_DK_nbr}
\caption{The iteration number of Ehrlich-Aberth versus Durand-Kerner algorithm}
-\label{fig:01}
+\label{fig:05}
\end{figure}
%\subsubsection{The execution time of Ehrlich-Aberth algorithm on OpenMP(1 core, 4 cores) vs. on a Tesla GPU}
