new

[kahina_paper2.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 4f6ae4b7d84c177500fe5100634c18a2352dd031..4533cb9a1f480739f0ec66f645a47175d53d38ac 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -76,7 +76,7 @@ where $\{\alpha_i\}_{0\leq i\leq n}$ are complex coefficients and $n$ is a high
 Most of the numerical methods that deal with the polynomial root-finding problem are simultaneous methods, \textit{i.e.} the iterative methods to find simultaneous approximations of the $n$ polynomial roots. These methods start from the initial approximations of all $n$ polynomial roots and give a sequence of approximations that converge to the roots of the polynomial. Two examples of well-known simultaneous methods for root-finding problem of polynomials are  Durand-Kerner method~\cite{Durand60,Kerner66} and Ehrlich-Aberth method~\cite{Ehrlich67,Aberth73}.
 
 
 Most of the numerical methods that deal with the polynomial root-finding problem are simultaneous methods, \textit{i.e.} the iterative methods to find simultaneous approximations of the $n$ polynomial roots. These methods start from the initial approximations of all $n$ polynomial roots and give a sequence of approximations that converge to the roots of the polynomial. Two examples of well-known simultaneous methods for root-finding problem of polynomials are  Durand-Kerner method~\cite{Durand60,Kerner66} and Ehrlich-Aberth method~\cite{Ehrlich67,Aberth73}.
 
 

-The convergence time of simultaneous methods drastically increases with the increasing of the polynomial's degree. The great challenge with simultaneous methods is to parallelize them and to improve their convergence. Many authors have proposed parallel simultaneous methods~\cite{Freeman89,Loizou83,Freemanall90,cs01:nj,Couturier02}, using several paradigms of parallelization (synchronous or asynchronous computations, mechanism of shared or distributed memory, etc). However, they have treated only polynomials not exceeding degrees of 20,000.
+The convergence time of simultaneous methods drastically increases with the increasing of the polynomial's degree. The great challenge with simultaneous methods is to parallelize them and to improve their convergence. Many authors have proposed parallel simultaneous methods~\cite{Freeman89,Loizou83,Freemanall90,bini96,cs01:nj,Couturier02}, using several paradigms of parallelization (synchronous or asynchronous computations, mechanism of shared or distributed memory, etc). However, they have treated only polynomials not exceeding degrees of 20,000.

 
 %The main problem of the simultaneous methods is that the necessary
 %time needed for the convergence increases with the increasing of the
 
 %The main problem of the simultaneous methods is that the necessary
 %time needed for the convergence increases with the increasing of the


@@ -193,12 +193,13 @@ Using the logarithm  and the exponential operators, we can replace any
 multiplications and divisions with additions and
 subtractions. Consequently, computations manipulate lower values in
 absolute values~\cite{Karimall98}. In practice, the  exponential and
 multiplications and divisions with additions and
 subtractions. Consequently, computations manipulate lower values in
 absolute values~\cite{Karimall98}. In practice, the  exponential and

-logarithm mode is used a root excepts the circle unit, \LZK{Je n'ai pas compris cette phrase!} represented by the radius $R$ evaluated in C language as :
+logarithm mode is used when a root is outisde the circle unit represented by the radius $R$ evaluated in C language with:

 \begin{equation}
 \label{R.EL}
 R = exp(log(DBL\_MAX)/(2*n) );
 \end{equation}
 \begin{equation}
 \label{R.EL}
 R = exp(log(DBL\_MAX)/(2*n) );
 \end{equation}

-where \verb=DBL_MAX= stands for the maximum representable \verb=double= value.
+where \verb=DBL_MAX= stands for the maximum representable
+\verb=double= value and $n$ is the degree of the polynimal.

 
 
 \subsection{The Ehrlich-Aberth parallel implementation on CUDA}
 
 
 \subsection{The Ehrlich-Aberth parallel implementation on CUDA}


@@ -218,7 +219,7 @@ long since it performs all the operations with complex numbers with
 the normal mode of the EA method but also with the
 logarithm-exponential one. Then the error is computed with a final
 kernel (line 7). Finally when the EA method has converged, the roots
 the normal mode of the EA method but also with the
 logarithm-exponential one. Then the error is computed with a final
 kernel (line 7). Finally when the EA method has converged, the roots

-are transferred from the GPU to the CPU.%\LZK{Quand est ce qu'on utilise un normal mode ou logarithm-exponential mode?}
+are transferred from the GPU to the CPU.

 
 \begin{algorithm}[htpb]
 \label{alg1-cuda}
 
 \begin{algorithm}[htpb]
 \label{alg1-cuda}


@@ -309,7 +310,6 @@ Copy $P$, $P'$ from CPU to GPU\;
 
 
 \subsection{A MPI-CUDA approach}
 
 
 \subsection{A MPI-CUDA approach}

-

 Our parallel implementation of EA to find roots of polynomials using a
 CUDA-MPI approach follows a similar approach to the one used in
 CUDA-OpenMP. Each process is responsible to compute its own part of
 Our parallel implementation of EA to find roots of polynomials using a
 CUDA-MPI approach follows a similar approach to the one used in
 CUDA-OpenMP. Each process is responsible to compute its own part of