biblio

[kahina_paper1.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 96e01fd054a410f2d09c9958b0154fcd26892f22..2dcee5775eefb549e1dbff4c00c96a5267b763e2 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -345,14 +345,12 @@ propose to use the logarithm and the exponential of a complex in order to comput
 Using the logarithm (eq.~\ref{deflncomplex}) and the exponential (eq.~\ref{defexpcomplex}) operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations
 manipulate lower absolute values and the roots for large polynomial's degrees can be looked for successfully~\cite{Karimall98}.
 
 Using the logarithm (eq.~\ref{deflncomplex}) and the exponential (eq.~\ref{defexpcomplex}) operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations
 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 exponential and logarithm:
+Applying this solution for the iteration function Eq.~\ref{Eq:Hi} of Ehrlich-Aberth method, we obtain the 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}
 EA.EL: z^{k+1}_{i}=z_{i}^{k}-\exp \left(\ln \left(
 %%$$ \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}
 EA.EL: z^{k+1}_{i}=z_{i}^{k}-\exp \left(\ln \left(

-p(z_{i}^{k})\right)-\ln\left(p'(z^{k}_{i})\right)- \ln
-\left(1-Q(z^{k}_{i})\right)\right),
+p(z_{i}^{k})\right)-\ln\left(p'(z^{k}_{i})\right)- \ln\left(1-Q(z^{k}_{i})\right)\right),

 \end{equation}
 
 where:
 \end{equation}
 
 where:


@@ -366,7 +364,7 @@ Q(z^{k}_{i})=\exp\left( \ln (p(z^{k}_{i}))-\ln(p'(z^{k}_{i}))+\ln \left(
 This solution is applied when the root except the circle unit, represented by the radius $R$ evaluated in C language as :
 \begin{equation}
 \label{R.EL}
 This solution is applied when the root except the circle unit, represented by the radius $R$ evaluated in C language as :
 \begin{equation}
 \label{R.EL}

-R = exp(log(DBL_MAX)/(2*n) );
+R = exp(log(DBL\_MAX)/(2*n) );

 \end{equation}
 
 
 \end{equation}
 
 


@@ -409,7 +407,7 @@ other processors at the end of each iteration (synchronous). Therefore they
 cause a high degree of memory conflict. Recently the author
 in~\cite{Mirankar71} proposed two versions of parallel algorithm
 for the Durand-Kerner method, and Ehrlich-Aberth method on a model of
 cause a high degree of memory conflict. Recently the author
 in~\cite{Mirankar71} proposed two versions of parallel algorithm
 for the Durand-Kerner method, and Ehrlich-Aberth method on a model of

-Optoelectronic Transpose Interconnection System (OTIS).The
+Optoelectronic Transpose Interconnection System (OTIS). The

 algorithms are mapped on an OTIS-2D torus using $N$ processors. This
 solution needs $N$ processors to compute $N$ roots, which is not
 practical for solving polynomials with large degrees.
 algorithms are mapped on an OTIS-2D torus using $N$ processors. This
 solution needs $N$ processors to compute $N$ roots, which is not
 practical for solving polynomials with large degrees.


@@ -542,7 +540,7 @@ polynomials of 48,000.
 \subsection{Parallel implementation with CUDA }
 
 In order to implement the Ehrlich-Aberth method in CUDA, it is
 \subsection{Parallel implementation with CUDA }
 
 In order to implement the Ehrlich-Aberth method in CUDA, it is

-possible to use the Jacobi scheme or the Gauss Seidel one.  With the
+possible to use the Jacobi scheme or the Gauss-Seidel one.  With the

 Jacobi iteration, at iteration $k+1$ we need all the previous values
 $z^{k}_{i}$ to compute the new values $z^{k+1}_{i}$, that is :
 
 Jacobi iteration, at iteration $k+1$ we need all the previous values
 $z^{k}_{i}$ to compute the new values $z^{k+1}_{i}$, that is :
 


@@ -560,7 +558,7 @@ With the Gauss-Seidel iteration, we have:
 \begin{equation}
 \label{eq:Aberth-H-GS}
 EAGS: z^{k+1}_{i}=z_{i}^{k}-\frac{\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}}
 \begin{equation}
 \label{eq:Aberth-H-GS}
 EAGS: z^{k+1}_{i}=z_{i}^{k}-\frac{\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}}

-{1-\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}(\sum^{i-1}_{j=1}\frac{1}{z^{k}_{i}-z^{k+1}_{j}}+\sum_{j=1,j\neq i}^{j=n}{\frac{1}{(z_{i}^{k}-z_{j}^{k})}})}, i=1,. . . .,n
+{1-\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}(\sum^{i-1}_{j=1}\frac{1}{z^{k}_{i}-z^{k+1}_{j}}+\sum_{j=i+1}^{j=n}{\frac{1}{(z_{i}^{k}-z_{j}^{k})}})}, i=1,. . . .,n

 \end{equation}
 
 Using Eq.~\ref{eq:Aberth-H-GS} to update the vector solution
 \end{equation}
 
 Using Eq.~\ref{eq:Aberth-H-GS} to update the vector solution


@@ -582,7 +580,7 @@ quickly because, just as any Jacobi algorithm (for solving linear systems of equ
 
 %In CUDA programming, all the instructions of the  \verb=for= loop are executed by the GPU as a kernel. A kernel is a function written in CUDA and defined by the  \verb=__global__= qualifier added before a usual \verb=C= function, which instructs the compiler to generate appropriate code to pass it to the CUDA runtime in order to be executed on the GPU. 
 
 
 %In CUDA programming, all the instructions of the  \verb=for= loop are executed by the GPU as a kernel. A kernel is a function written in CUDA and defined by the  \verb=__global__= qualifier added before a usual \verb=C= function, which instructs the compiler to generate appropriate code to pass it to the CUDA runtime in order to be executed on the GPU. 
 

-Algorithm~\ref{alg2-cuda} shows sketch of the Ehrlich-Aberth algorithm using CUDA.
+Algorithm~\ref{alg2-cuda} shows sketch of the Ehrlich-Aberth method using CUDA.

 
 \begin{enumerate}
 \begin{algorithm}[H]
 
 \begin{enumerate}
 \begin{algorithm}[H]


@@ -590,7 +588,7 @@ Algorithm~\ref{alg2-cuda} shows sketch of the Ehrlich-Aberth algorithm using CUD
 %\LinesNumbered
 \caption{CUDA Algorithm to find roots with the Ehrlich-Aberth method}
 
 %\LinesNumbered
 \caption{CUDA Algorithm to find roots with the Ehrlich-Aberth method}
 

-\KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (error tolerance
+\KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance

   threshold), P (Polynomial to solve), Pu (Derivative of P), $n$ (Polynomial's degrees), $\Delta z_{max}$ (Maximum value of stop condition)}
 
 \KwOut {$Z$ (Solution root's vector), $ZPrec$ (Previous solution root's vector)}
   threshold), P (Polynomial to solve), Pu (Derivative of P), $n$ (Polynomial's degrees), $\Delta z_{max}$ (Maximum value of stop condition)}
 
 \KwOut {$Z$ (Solution root's vector), $ZPrec$ (Previous solution root's vector)}