From: Kahina Date: Wed, 4 Nov 2015 11:15:51 +0000 (+0100) Subject: Merge branch 'master' of ssh://info.iut-bm.univ-fcomte.fr/kahina_paper1 X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/kahina_paper1.git/commitdiff_plain/e190c5da7c414d75199c2179a1d0268f4171c6c9?hp=407f6448703e5d6ae4aa91a11ac80ffa92414bce Merge branch 'master' of ssh://info.iut-bm.univ-fcomte.fr/kahina_paper1 Conflicts: paper.tex --- diff --git a/figures/sparse_full_explog.pdf b/figures/sparse_full_explog.pdf index 3c7c22e..c206985 100644 Binary files a/figures/sparse_full_explog.pdf and b/figures/sparse_full_explog.pdf differ diff --git a/figures/sparse_full_explog.plot b/figures/sparse_full_explog.plot deleted file mode 100644 index 1d86c55..0000000 --- a/figures/sparse_full_explog.plot +++ /dev/null @@ -1,25 +0,0 @@ -# Analysis description -set encoding iso_8859_1 -set terminal x11 -set size 1,0.5 -set term postscript enhanced portrait "Helvetica" 12 - -set ylabel "execution times (in s)" -set xlabel "Sparse and full polynomial's degrees" -set logscale x -set logscale y -#'#dd181f -#'#dd181f' - -#set key on outside left bmargin -set style line 1 lc rgb '#000c16' lt 1 lw 2 pt 1 ps 1.5 # --- blue -set style line 2 lc rgb '#000c16' lt 1 lw 2 pt 5 ps 1.5 # --- red -set style line 4 lc rgb '#000c16' lt 1 lw 2 pt 9 ps 1.5 # --- red -set style line 3 lc rgb '#000c16' lt 1 lw 2 pt 6 ps 1.5 # --- red - - plot'log_exp_Sparse.txt' index 0 using 1:4 t "Sparse polynomial No exp.log" with linespoints ls 4,\ - 'log_exp_Sparse.txt' index 0 using 1:2 t "Sparse polynomial with exp.log" with linespoints ls 1,\ - 'log_exp_Sparse.txt' index 1 using 1:2 t "Sparse polynomial with exp.log" with linespoints ls 1,\ -'log_exp.txt' index 0 using 1:4 t "Full polynomial No exp.log" with linespoints ls 2,\ - 'log_exp.txt' index 0 using 1:2 t "Full polynomial with exp.log" with linespoints ls 3,\ - 'log_exp.txt'index 1 using 1:2 t "Full polynomail with exp.log" with linespoints ls 3 \ No newline at end of file diff --git a/paper.tex b/paper.tex index cf26c41..34b803c 100644 --- a/paper.tex +++ b/paper.tex @@ -734,7 +734,7 @@ The figure 2 show that, the best execution time for both sparse and full polynom \subsection{The impact of exp.log solution to compute very high degrees of polynomial} -In this experiment we report the performance of exp.log solution describe in ~\ref{sec2} to compute very high degrees polynomials. +In this experiment we report the performance of exp-log solution described in Section~\ref{sec2} to compute very high degrees polynomials. \begin{figure}[htbp] \centering \includegraphics[width=0.8\textwidth]{figures/sparse_full_explog} @@ -742,23 +742,44 @@ In this experiment we report the performance of exp.log solution describe in ~\r \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 exp.log) stop to converge and can not solving any polynomial sparse or full. In counterpart, the new version of Ehrlich-Aberth algorithm (applying exp.log 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 exp.log 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 . +Figure~\ref{fig:03} shows a comparison between the execution time of +the Ehrlich-Aberth algorithm using the exp.log solution and the +execution time of the Ehrlich-Aberth algorithm without this solution, +with full and sparse polynomials degrees. We can see that the +execution times for both algorithms are the same with full polynomials +degrees less than 4000 and sparse polynomials less than 150,000. We +also clearly show that the classical version (without log.exp) of +Ehrlich-Aberth algorithm do not converge after these degree with +sparse and full polynomials. In counterpart, the new version of +Ehrlich-Aberth algorithm with the log.exp solution can solve very +high degree polynomials. +%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 . -\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. + + +\subsection{Comparison of the Durand-Kerner and the Ehrlich-Aberth methods} + +In this part, we compare the Durand-Kerner and the Ehrlich-Aberth +methods on GPU. We took into account the execution time, the number of iteration and the polynomial's size for the both sparse and full polynomials. \begin{figure}[htbp] \centering \includegraphics[width=0.8\textwidth]{figures/EA_DK} -\caption{The execution time of Ehrlich-Aberth versus Durand-Kerner algorithm on GPU} +\caption{Execution times of the Durand-Kerner and the Ehrlich-Aberth methods on GPU} \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}$. +Figure~\ref{fig:04} shows the execution times of both methods with +sparse polynomial degrees ranging from 1,000 to 1,000,000. We can see +that the Ehrlich-Aberth algorithm is faster than Durand-Kerner +algorithm, with an average of 25 times faster. 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}$. \begin{figure}[htbp] \centering