MAJ Mybibfile

[kahina_paper1.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 276c50a9b3eb46e64687e1ceacbf25a4beeca9b6..4213238dc15bba747cab568e22b4b4baecab2c2e 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -312,8 +312,7 @@ The convergence condition determines the termination of the algorithm. It consis
 
 \begin{equation}
 \label{eq:Aberth-Conv-Cond}
-\forall i \in
-[1,n];\frac{z_{i}^{k}-z_{i}^{k-1}}{z_{i}^{k}}<\xi
+\forall i \in [1,n];\vert\frac{z_{i}^{k}-z_{i}^{k-1}}{z_{i}^{k}}\vert<\xi
 \end{equation}
 
 
@@ -348,7 +347,7 @@ Using the logarithm (eq.~\ref{deflncomplex}) and the exponential (eq.~\ref{defex
 manipulate lower absolute values and the roots for large polynomial's degrees can be looked for successfully~\cite{Karimall98}.
 
 Applying this solution for the Ehrlich-Aberth method we obtain the
-iteration function with logarithm:
+iteration function with exponential and logarithm:
 %%$$ \exp \bigl(  \ln(p(z)_{k})-ln(\ln(p(z)_{k}^{'}))- \ln(1- \exp(\ln(p(z)_{k})-ln(\ln(p(z)_{k}^{'})+\ln\sum_{i\neq j}^{n}\frac{1}{z_{k}-z_{j}})$$
 \begin{equation}
 \label{Log_H2}
@@ -494,32 +493,37 @@ read-only caches.
 
 \subsection{A sequential Ehrlich-Aberth algorithm}
 The main steps of Ehrlich-Aberth method are shown in Algorithm.~\ref{alg1-seq} :
-  
+%\LinesNumbered  
 \begin{algorithm}[H]
 \label{alg1-seq}
-%\LinesNumbered
+
 \caption{A sequential algorithm to find roots with the Ehrlich-Aberth method}
 
-\KwIn{$Z^{0}$(Initial root's vector),$\varepsilon$ (error tolerance threshold),P(Polynomial to solve)}
-\KwOut {Z(The solution root's vector)}
+\KwIn{$Z^{0}$(Initial root's vector),$\varepsilon$ (error tolerance threshold), P(Polynomial to solve),$\Delta z_{max}$ (maximum value of stop condition),k (number of iteration),n(Polynomial's degrees)}
+\KwOut {Z (The solution root's vector),ZPrec (the previous solution root's vector)}
 
 \BlankLine
 
 Initialization of the coefficients of the polynomial to solve\;
 Initialization of the solution vector $Z^{0}$\;
+$\Delta z_{max}=0$\;
+ k=0\;
 
-\While {$\Delta z_{max}\succ \epsilon$}{
+\While {$\Delta z_{max} > \varepsilon$}{
  Let $\Delta z_{max}=0$\;
 \For{$j \gets 0 $ \KwTo $n$}{
-$ZPrec\left[j\right]=Z\left[j\right]$\;
-$Z\left[j\right]=H\left(j,Z\right)$\;
+$ZPrec\left[j\right]=Z\left[j\right]$;// save Z at the iteration k.\
+
+$Z\left[j\right]=H\left(j,Z\right)$;//update Z with the iterative function.\
 }
+k=k+1\;
 
 \For{$i \gets 0 $ \KwTo $n-1$}{
-$c=\frac{\left|Z\left[i\right]-ZPrec\left[i\right]\right|}{Z\left[i\right]}$\;
+$c= testConverge(\Delta z_{max},ZPrec\left[j\right],Z\left[j\right])$\;
 \If{$c > \Delta z_{max}$ }{
 $\Delta z_{max}$=c\;}
 }
+
 }
 \end{algorithm}
 
@@ -556,8 +560,7 @@ Algorithm~\ref{alg2-cuda} shows a sketch of the Ehrlich-Aberth algorithm using C
 %\LinesNumbered
 \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)}
+\KwIn{$Z^{0}$(Initial root's vector),$\varepsilon$ (error tolerance threshold), P(Polynomial to solve), $\Delta z_{max}$ (maximum value of stop condition)}
 
 \KwOut {Z(The solution root's vector)}
 
@@ -566,12 +569,14 @@ tolerance threshold),P(Polynomial to solve)}
 Initialization of the coeffcients of the polynomial to solve\;
 Initialization of the solution vector $Z^{0}$\;
 Allocate and copy initial data to the GPU global memory\;
-
+k=0\;
 \While {$\Delta z_{max}\succ \epsilon$}{
  Let $\Delta z_{max}=0$\;
-$ kernel\_save(d\_z^{k-1})$\;
-$ kernel\_update(d\_z^{k})$\;
-$kernel\_testConverge(\Delta z_{max},d_z^{k},d_z^{k-1})$\;
+$ kernel\_save(d\_Z^{k-1})$\;
+k=k+1\;
+$ kernel\_update(d\_Z^{k})$\;
+$kernel\_testConverge(\Delta z_{max},d\_Z^{k},d\_Z^{k-1})$\;
+
 }
 \end{algorithm}
 ~\\