Quelques MAJ

[kahina_paper2.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 15031f87ea647951689a5fcccb10ed41a76763e7..9c918b8b574597c0813047c781eb5a8c109de591 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -431,7 +431,7 @@ Finding roots of polynomials is a very important part of solving real-life probl
 
 %The issue of finding the roots of polynomials of very high degrees arises in many complex problems in various fields, such as algebra, biology, finance, physics or climatology [1]. In algebra for example, finding eigenvalues or eigenvectors of any real/complex matrix amounts to that of finding the roots of the so-called characteristic polynomial.
 
 
 %The issue of finding the roots of polynomials of very high degrees arises in many complex problems in various fields, such as algebra, biology, finance, physics or climatology [1]. In algebra for example, finding eigenvalues or eigenvectors of any real/complex matrix amounts to that of finding the roots of the so-called characteristic polynomial.
 

-Finding roots of polynomials of very high degrees arises in many complex problems in various domains such as algebra, biology or physics. A polynomial $p(x)$ in $\mathbb{C}$ in one variable $x$ is an algebraic expression in $x$ of the form
+Finding roots of polynomials of very high degrees arises in many complex problems in various domains such as algebra, biology or physics. A polynomial $p(x)$ in $\mathbb{C}$ in one variable $x$ is an algebraic expression in $x$ of the form:

 \begin{equation}
 p(x) = \displaystyle\sum^n_{i=0}{a_ix^i},a_0\neq 0. 
 \end{equation}
 \begin{equation}
 p(x) = \displaystyle\sum^n_{i=0}{a_ix^i},a_0\neq 0. 
 \end{equation}


@@ -597,7 +597,7 @@ CUDA (Compute Unified Device Architecture) is a parallel computing architecture
 %Here we give a second form of the iterative function used by the Ehrlich-Aberth method: 
 
 %\begin{equation}
 %Here we give a second form of the iterative function used by the Ehrlich-Aberth method: 
 
 %\begin{equation}

-%\label{Eq:EA1}
+%\label{Eq:EA-1}

 %EA: 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_{j=1,j\neq i}^{j=n}{\frac{1}{(z_{i}^{k}-z_{j}^{k})}}}, %i=1,. . . .,n
 %\end{equation}
 %EA: 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_{j=1,j\neq i}^{j=n}{\frac{1}{(z_{i}^{k}-z_{j}^{k})}}}, %i=1,. . . .,n
 %\end{equation}


@@ -606,7 +606,7 @@ CUDA (Compute Unified Device Architecture) is a parallel computing architecture
 %The convergence condition determines the termination of the algorithm. It consists in stopping the %iterative function  when the roots are sufficiently stable. We consider that the method converges %sufficiently when:
 
 %\begin{equation}
 %The convergence condition determines the termination of the algorithm. It consists in stopping the %iterative function  when the roots are sufficiently stable. We consider that the method converges %sufficiently when:
 
 %\begin{equation}

-%\label{eq:Aberth-Conv-Cond}
+%\label{eq:AAberth-Conv-Cond}

 %\forall i \in [1,n];\vert\frac{z_{i}^{k}-z_{i}^{k-1}}{z_{i}^{k}}\vert<\xi
 %\end{equation}
 
 %\forall i \in [1,n];\vert\frac{z_{i}^{k}-z_{i}^{k-1}}{z_{i}^{k}}\vert<\xi
 %\end{equation}
 


@@ -639,7 +639,52 @@ contain 4 steps, start from the initial approximations of all the roots of the p
 \forall i \in [1,n];\vert\frac{z_{i}^{k}-z_{i}^{k-1}}{z_{i}^{k}}\vert<\xi
 \end{equation}
 \subsection{Improving Ehrlich-Aberth method}
 \forall i \in [1,n];\vert\frac{z_{i}^{k}-z_{i}^{k-1}}{z_{i}^{k}}\vert<\xi
 \end{equation}
 \subsection{Improving Ehrlich-Aberth method}

-......
+With high degree polynomial, the Ehrlich-Aberth method suffer from overflow because the limited number in the mantissa of floating points representations, which makes the computation of $p(z)$ wrong when z is large.
+ 
+Experimentally, it is very difficult to solve polynomials with Ehrlich-Aberth method and have roots which except the circle of unit, represented by the radius $r$ evaluated as: 
+
+\begin{equation}
+\label{R.EL}
+R = exp(log(DBL\_MAX)/(2*n) );
+\end{equation}
+
+
+%\begin{equation}
+
+%R = \exp( \log(DBL\_MAX) / (2*n) )
+%\end{equation}
+ where \verb=DBL_MAX= stands for the maximum representable \verb=double= value.
+ 
+In order to hold into account the limit of size of floats, we propose to modifying the iterative function and compute the logarithm of:
+
+\begin{equation}
+EA: 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_{j=1,j\neq i}^{j=n}{\frac{1}{(z_{i}^{k}-z_{j}^{k})}}}, i=1,. . . .,n
+\end{equation}
+
+This method allows, indeed, to exceed the computation of the polynomials of degree 100,000 and to reach a degree upper to 1,000,000. For that purpose, it is necessary to use the logarithm and the exponential of a complex. The iterative  function of Ehrlich-Aberth method with exponential and logarithm is given as following:
+
+\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),
+\end{equation}
+
+where:
+
+\begin{equation}
+\label{Log_H1}
+Q(z^{k}_{i})=\exp\left( \ln (p(z^{k}_{i}))-\ln(p'(z^{k}_{i}))+\ln \left(
+\sum_{i\neq j}^{n}\frac{1}{z^{k}_{i}-z^{k}_{j}}\right)\right)i=1,...,n,
+\end{equation}
+
+
+%We propose to use the logarithm and the exponential of a complex in order to compute the power at a high exponent. 
+Using the logarithm  and the exponential operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations manipulate lower absolute values and the roots for large polynomial degrees can be looked for successfully~\cite{Karimall98}.
+
+%This problem was discussed earlier in~\cite{Karimall98} for the Durand-Kerner method. The authors
+%propose to use the logarithm and the exponential of a complex in order to compute the power at a high exponent. Using the logarithm  and the exponential operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations manipulate lower absolute values and the roots for large polynomial degrees can be looked for successfully~\cite{Karimall98}.
+

 \subsection{Ehrlich-Aberth parallel implementation on CUDA}
 We introduced three paradigms of parallel programming. Our objective consists in implementing a root finding polynomial algorithm on multiple GPUs. To this end, it is primordial to know how to manage CUDA contexts of different GPUs. A direct method for controlling the various GPUs is to use as many threads or processes as GPU devices. We can choose the GPU index based on the identifier of OpenMP thread or the rank of the MPI process. Both approaches will be investigated.
 
 \subsection{Ehrlich-Aberth parallel implementation on CUDA}
 We introduced three paradigms of parallel programming. Our objective consists in implementing a root finding polynomial algorithm on multiple GPUs. To this end, it is primordial to know how to manage CUDA contexts of different GPUs. A direct method for controlling the various GPUs is to use as many threads or processes as GPU devices. We can choose the GPU index based on the identifier of OpenMP thread or the rank of the MPI process. Both approaches will be investigated.
 


@@ -656,7 +701,7 @@ sequential operations and the operations that have data
 dependencies between threads or recursive computations must
 be executed by only one CUDA or CPU thread (step 1 and step 2). Initially, we specify the organization of parallel threads, by specifying the dimension of the grid Dimgrid, the number of blocks per grid DimBlock and the number of threads per block. 
 
 dependencies between threads or recursive computations must
 be executed by only one CUDA or CPU thread (step 1 and step 2). Initially, we specify the organization of parallel threads, by specifying the dimension of the grid Dimgrid, the number of blocks per grid DimBlock and the number of threads per block. 
 

-The code is organzed  by what is named kernels, portions o code that are run on GPU devices. For step 3, there are two kernels, the
+The code is organized  by what is named kernels, portions code that are run on GPU devices. For step 3, there are two kernels, the

 first named \textit{save} is used to save vector $Z^{K-1}$ and the seconde one is named
 \textit{update} and is used to update the $Z^{K}$ vector. For step 4, a kernel 
 tests the convergence of the method. In order to
 first named \textit{save} is used to save vector $Z^{K-1}$ and the seconde one is named
 \textit{update} and is used to update the $Z^{K}$ vector. For step 4, a kernel 
 tests the convergence of the method. In order to


@@ -695,11 +740,11 @@ Algorithm~\ref{alg1-cuda} shows the GPU parallel implementation of Ehrlich-Abert
 \item Initialization of the solution vector $Z^{0}$\;
 \item Allocate and copy initial data to the GPU global memory\;
 \item k=0\;
 \item Initialization of the solution vector $Z^{0}$\;
 \item Allocate and copy initial data to the GPU global memory\;
 \item k=0\;

-\While {$\Delta z_{max} > \epsilon$}{
-\item Let $\Delta z_{max}=0$\;
-\item $ kernel\_save(ZPrec,Z)$\;
-\item  k=k+1\;
-\item $ kernel\_update(Z,P,Pu)$\;
+\item \While {$\Delta z_{max} > \epsilon$}{
+\item   Let $\Delta z_{max}=0$\;
+\item   $ kernel\_save(ZPrec,Z)$\;
+\item   k=k+1\;
+\item   $ kernel\_update(Z,P,Pu)$\;

 \item $kernel\_testConverge(\Delta z_{max},Z,ZPrec)$\;
 
 }
 \item $kernel\_testConverge(\Delta z_{max},Z,ZPrec)$\;
 
 }