\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), Pu (the derivative of P), $n$ (Polynomial's degrees),$\Delta z_{max}$ (maximum value of stop condition)}
+ threshold), P(Polynomial to solve), Pu (the derivative of P), $n$ (Polynomial's degrees), $\Delta z_{max}$ (maximum value of stop condition)}
\KwOut {$Z$ (The solution root's vector), $ZPrec$ (the previous solution root's vector)}
Initialization of the of P\;
Initialization of the of Pu\;
Initialization of the solution vector $Z^{0}$\;
-Allocate and copy initial data to the GPU global memory ($d\_Z,d\_ZPrec,d\_P,d\_Pu$)\;
+Allocate and copy initial data to the GPU global memory\;
k=0\;
\While {$\Delta z_{max} > \epsilon$}{
Let $\Delta z_{max}=0$\;
-$ kernel\_save(d\_ZPrec,d\_Z)$\;
+$ kernel\_save(ZPrec,Z)$\;
k=k+1\;
-$ kernel\_update(d\_Z,d\_P,d\_Pu)$\;
-$kernel\_testConverge(\Delta z_{max},d\_Z,d\_ZPrec)$\;
+$ kernel\_update(Z,P,Pu)$\;
+$kernel\_testConverge(\Delta z_{max},Z,ZPrec)$\;
}
Copy results from GPU memory to CPU memory\;
%\LinesNumbered
\caption{Kernel update}
-\eIf{$(\left|d\_Z\right|<= R)$}{
-$kernel\_update((d\_Z,d\_P,d\_Pu)$\;}
+\eIf{$(\left|Z\right|<= R)$}{
+$kernel\_update((Z,P,Pu)$\;}
{
-$kernel\_update\_ExpoLog((d\_Z,d\_P,\_Pu))$\;
+$kernel\_update\_ExpoLog((Z,P,Pu))$\;
}
\end{algorithm}
\label{fig:04}
\end{figure}
+\begin{figure}[htbp]
+\centering
+ \includegraphics[width=0.8\textwidth]{figures/EA_DK1}
+\caption{Execution times of the Durand-Kerner and the Ehrlich-Aberth methods on GPU}
+\label{fig:0}
+\end{figure}
+
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
