From dc93483689b3327eada2eb44f000c8c0d40753c7 Mon Sep 17 00:00:00 2001 From: couturie Date: Fri, 6 Nov 2015 15:00:06 +0100 Subject: [PATCH] fin correct --- paper.tex | 33 +++++++++++++++++---------------- 1 file changed, 17 insertions(+), 16 deletions(-) diff --git a/paper.tex b/paper.tex index 4d08b49..44f01e2 100644 --- a/paper.tex +++ b/paper.tex @@ -810,7 +810,7 @@ high degree 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 times, the number of iterations and the polynomials size for the both sparse and full polynomials. +methods on GPU. We took into account the execution times, the number of iterations and the polynomials size for both sparse and full polynomials. \begin{figure}[htbp] \centering @@ -822,8 +822,8 @@ methods on GPU. We took into account the execution times, the number of iteratio 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 500,000 the execution times with DK are very long. +algorithm, being on average 25 times faster. Then, when degrees of +polynomials exceed 500,000 the execution times with DK are very long. %with double precision not exceed $10^{-5}$. @@ -835,14 +835,15 @@ polynomial exceed 500,000 the execution times with DK are very long. \label{fig:05} \end{figure} -Figure~\ref{fig:05} show the evaluation of the number of iteration according -to degree of polynomial from both EA and DK algorithms, we can see -that the iteration number of DK is of order 100 while EA is of order -10. Indeed the computing of the derivative of P (the polynomial to -resolve) in the iterative function (Eq.~\ref{Eq:Hi}) executed by EA -allows the algorithm to converge more quickly. In counterpart, the -DK operator (Eq.~\ref{DK}) needs low operation, consequently low -execution time per iteration, but it needs more iterations to converge. +Figure~\ref{fig:05} shows the evaluation of the number of iterations according +to the degree of polynomials for both EA and DK algorithms. We can see +that the number of iterations of DK is of order 100 while EA is of order +10. Indeed the computation of the derivative of P in the iterative function (Eq.~\ref{Eq:Hi}) executed by EA +allows the algorithm to converge faster. On the contrary, the +DK operator (Eq.~\ref{DK}) needs low operations, consequently low +execution times per iteration, but it needs more iterations to converge. + + \section{Conclusion and perspectives} @@ -855,17 +856,17 @@ applied to the iterative function allows to solve high degree polynomials. We have performed many experiments with the Ehrlich-Aberth method in -GPU. These experiments highlight that this method is very efficient in -GPU compared to all the other implementations. The improvement with +GPU. These experiments highlight that this method is more efficient in +GPU than all the other implementations. The improvement with the exponential logarithm solution allows us to solve sparse and full high degree polynomials up to 1,000,000 degree. Hence, it may be -possible to consider to use polynomial root finding methods in other +possible to consider using polynomial root finding methods in other numerical applications on GPU. In future works, we plan to investigate the possibility of using -several multiple GPUs simultaneously, either with multi-GPU machine or -with cluster of GPUs. It may also be interesting to study the +several multiple GPUs simultaneously, either with a multi-GPU machine or +with a cluster of GPUs. It may also be interesting to study the implementation of other root finding polynomial methods on GPU. -- 2.39.5