%%\usepackage[utf8]{inputenc}
%%\usepackage[T1]{fontenc}
%%\usepackage[french]{babel}
+\usepackage{float}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage[ruled,vlined]{algorithm2e}
%\usepackage[french,boxed,linesnumbered]{algorithm2e}
Polynomials are algebraic structures used in mathematics that capture physical phenomenons and that express the outcome in the form of a function of some unknown variable. Formally speaking, a polynomial $p(x)$ of degree \textit{n} having $n$ coefficients in the complex plane \textit{C} and zeros $\alpha_{i},\textit{i=1,...,n}$
%%\begin{center}
\begin{equation}
- {\Large p(x)=\sum{a_{i}x^{i}}=a_{n}\prod(x-\alpha_{i}),a_{0} a_{n}\neq 0}.
+ {\Large p(x)=\sum_{i=0}^{n}{a_{i}x^{i}}=a_{n}\prod_{i=1}^{n}(x-\alpha_{i}), a_{0} a_{n}\neq 0}.
\end{equation}
%%\end{center}
\section{Experimental study}
\subsection{Definition of the polynomial used}
-We use two forms of polynomials:
-\paragraph{sparse polynomial}:
-in this following form, the roots are distributed on 2 distinct circles:
+We study two forms of polynomials the sparse polynomials and the full polynomials:
+\paragraph{Sparse polynomial}: in this following form, the roots are distributed on 2 distinct circles:
\begin{equation}
- \forall \alpha_{1} \alpha_{2} \in C,\forall n_{1},n_{2} \in N^{*}; P(z)= (z^{n^{1}}-\alpha_{1})(z^{n^{2}}-\alpha_{2})
+ \forall \alpha_{1} \alpha_{2} \in C,\forall n_{1},n_{2} \in N^{*}; P(z)= (z^{n_{1}}-\alpha_{1})(z^{n_{2}}-\alpha_{2})
\end{equation}
-
This form makes it possible to associate roots having two
different modules and thus to work on a polynomial constitute
of four non zero terms.
-\paragraph{Full polynomial}:
- the second form used to obtain a full polynomial is:
+\paragraph{Full polynomial}: the second form used to obtain a full polynomial is:
%%\begin{equation}
%%\forall \alpha_{i} \in C,\forall n_{i}\in N^{*}; P(z)= \sum^{n}_{i=1}(z^{n^{i}}.a_{i})
%%\end{equation}
\begin{equation}
- {\Large \forall a_{i} \in C, i\in N; p(x)=\sum^{n-1}_{i=1} a_{i}.x^{i}}
+ {\Large \forall a_{i} \in C, i\in N; p(x)=\sum^{n}_{i=0} a_{i}.x^{i}}
\end{equation}
with this form, we can have until \textit{n} non zero terms.
\subsection{The study condition}
-In order to have representative average values, for each
-point of our curves we measured the roots finding of 10
-different polynomials.
-
The our experiences results concern two parameters which are
the polynomial degree and the execution time of our program
to converge on the solution. The polynomial degree allows us
polynomials. The execution time remains the
element-key which justifies our work of parallelization.
For our tests we used a CPU Intel(R) Xeon(R) CPU
-E5620@2.40GHz and a GPU K40 (with 6 Go of ram)
+E5620@2.40GHz and a GPU K40 (with 6 Go of ram).
\subsection{Comparative study}
% \label{tab:theConvergenceOfAberthAlgorithm}
%\end{table}
-\begin{figure}[htbp]
+\begin{figure}[H]
\centering
\includegraphics[width=0.8\textwidth]{figures/Compar_EA_algorithm_CPU_GPU}
\caption{Aberth algorithm on CPU and GPU}
%\end{table}
-\begin{figure}[htbp]
+\begin{figure}[H]
\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}
\end{figure}
-
+\subsubsection{The impact of exp-log solution to compute very high degrees of polynomial}
+\begin{figure}[H]
+\centering
+ \includegraphics[width=0.8\textwidth]{figures/log_exp}
+\caption{The impact of exp-log solution to compute very high degrees of polynomial.}
+\label{fig:01}
+\end{figure}
\subsubsection{A comparative study between Aberth and Durand-kerner algorithm}
-\begin{table}[htbp]
- \centering
- \begin{tabular} {|R{2cm}|L{2.5cm}|L{2.5cm}|L{1.5cm}|L{1.5cm}|}
- \hline Polynomial's degrees & Aberth $T_{exe}$ & D-Kerner $T_{exe}$ & Aberth iteration & D-Kerner iteration\\
- \hline 5000 & 0.40 & 3.42 & 17 & 138 \\
- \hline 50000 & 3.92 & 385.266 & 17 & 823\\
- \hline 500000 & 497.109 & 4677.36 & 24 & 214\\
- \hline
- \end{tabular}
- \caption{Aberth algorithm compare to Durand-Kerner algorithm}
- \label{tab:AberthAlgorithCompareToDurandKernerAlgorithm}
-\end{table}
+
+
+\begin{figure}[H]
+\centering
+ \includegraphics[width=0.8\textwidth]{figures/EA_DK}
+\caption{Ehrlisch-Aberth and Durand-Kerner algorithm on GPU}
+\label{fig:01}
+\end{figure}
\bibliography{mybibfile}
