1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2% latex multiGrid 3% xdvi multiGrid & 4% dvips -D600 multiGrid.dvi -o multiGrid.ps 5%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 6\documentclass[11pt]{article} 7\usepackage{graphicx} 8\usepackage{fullpage} 9\usepackage{times} 10\newcommand{\ProtoMol}{\textsc{ProtoMol }} 11\author{Thierry Matthey\\{\tt matthey@ii.uib.no}} 12 13\title{Multigrid} 14%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 15\begin{document} 16%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 17\maketitle 18%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 19 20%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 21\section{Introduction} 22 23Multi grid is a method for the fast summation of long range forces, 24i.e. Coulomb force, in a system consisting of a large number of 25particles. For $N$-particle system, multi grid has a time complexity 26of $O(N)$, where the direct solution, the Ewald Sum and Particle Mesh 27Ewald are of order $O(N^2)$, $O(N^{\frac{3}{2}})$ respectively 28$O(N\log N)$. Multi grid decomposes the Coulomb interaction between the 29particles into a local and a smooth part. 30 31%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 32\section{Input parameters} 33 34This sections gives the definition of the multi grid input parameters 35for \ProtoMol. 36 37%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 38\subsection{General syntax} 39 40\ProtoMol\ expects the following input for multi grid: 41\begin{verbatim} 42 -algorithm MultiGrid -interpolation <Hermite|BSpline> -kernel <C1|C2|C3|C4> 43 -direct -smooth -correction 44 -s <real,positive> 45 -toplevelgrid <uint,positive> <uint,positive> <uint,positive> # Vacuum 46 -h <coordinates,non-zero> # PBC 47 -levels <int,positive> 48 -order <uint=4,positive> 49 -ratio <uint=2,positive> 50 \end{verbatim} 51, where \texttt{=}{\it value} defines the default value, i.e. optional 52input.\\ 53Note that \texttt{Coulomb} can be replaced by a new, user defined potential, 54which is of the form $c r^a$, where $c$ is a constant and $r$ is the 55distance between particle pairs. The new potential also requires 56re-definition of \texttt{C1}, \texttt{C2}, \texttt{C3} and 57\texttt{C4}. For the Lennard-Jones potential a new template is 58required due to the sum in the potential definition. 59 60%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 61\subsection{Interpolation} 62 63\texttt{-interpolation} defines the interpolation scheme between the 64grids the particle level. For the moment \ProtoMol\ 65does only accept Hermitian interpolation (\texttt{Hermite}). Other 66interpolations like b-splines (\texttt{BSpline}) did not improve the 67accuracy. 68 69%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 70\subsection{Kernel} 71 72\texttt{-kernel} defines how the {\it kernel} $G(r)$ (i.e. the Coulomb 73potential, $r=|\vec{r}_{i} - \vec{r}_{j}|$) is 74{\it softened}. To {\it smooth} the kernel we only modify in a local range 75$r<s$, where $s$ is the softening 76distance. The {\it smoothed kernel} is defined as follow: 77\begin{equation} 78 G_{smooth}(r) \left\{ 79 \begin{array}{lcl} 80 G_s(r) & : & r<s\\ 81 G(r) & : & \mbox{otherwise} 82 \end{array} 83\right. 84\end{equation} 85, where $G_s(r)$ is the {\it smoothing function}. \texttt{C1}, 86\texttt{C2}, \texttt{C3} and \texttt{C4} are smoothing functions 87$G_s(r)$, which satisfy the the $C^1$, $C^3$, $C^3$ respectively 88$C^4$ property. The smoothing functions fit 89only together with the Coulomb potential ($C\frac{q_i 90 q_j}{|\vec{r}_{i} - \vec{r}_{j}|}$). 91 92%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 93\subsection{Direct, smooth part and correction} 94 95\texttt{-direct} \texttt{-smooth} and \texttt{-correction} indicate the part to be 96 evaluated. \texttt{-correction} accounts the point self energy and the 97 intra molecular term. By default (none of them set) all parts are computed. 98 99 100%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 101\subsection{Levels} 102 103\texttt{-levels} defines the number of levels (grids). 104\\ 105From experiments we know that finest grid should reflect a mesh size 106of order of the average distance between particles. Note that the number of 107levels and the ratio (\texttt{-ratio}) define roughly the relation of 108grid points between the fines and the coarsest grid. The relation is of 109 $\mbox{ratio}^{levels}$. 110 111%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 112\subsection{Toplevelgrid or mesh size} 113 114\texttt{-toplevelgrid} defines the number of grid points in each 115dimension ($n_x$, $n_y$, $n_z$) for the coarsest grid for vacuum systems, the one on the 116top. \ProtoMol will 117itself figure out the number of grid points required, for each finer 118grid.\\ 119In case of periodic boundary conditions the relation of grid 120points between to grids is defined by the ratio (\texttt{-ratio}) and 121mesh size of the finest grid (\texttt{-g}): 122\begin{equation} 123 n_f = n_c \cdot \mbox{ ratio} 124\end{equation} 125Obviously, the length, depth and high of the grids are the same ($ d_f 126= d_c$), defined by the cell basis vectors. The 127number of grid points of the toplevel is equivalent to the number of 128subdivision for the coarsest grid (Fig. \ref{fig:levels_bpc}). 129\begin{figure}[hbt] 130 \centerline{\includegraphics[width=3cm]{levels_pbc.pdf}} 131 \caption{2-level, periodic boundaries, ratio, $n_1 = n_2 = 8$, $d_1 = d_2$, .} 132 \label{fig:levels_bpc} 133\end{figure} 134\\ 135For the case of vacuum (i.e. no boundaries) the relation between two grids 136depends on the ratio, the interpolation and order of interpolation: 137\begin{equation} 138 n_f = (n_c - \mbox{ order }+1) \mbox{ ratio } +1 139\end{equation} 140, assuming Hermitian interpolation, where for other interpolation 141schemes the inner $+1$ may fall away. For the correctness of 142interpolation the coarser grid must overlap the finer grid (Fig. \ref{fig:levels_nbc}). 143The length, depth and high of the finer grid is computed as follow: 144\begin{equation} 145 d_f = \frac{d_c n_f-1}{\mbox{ratio }(\mbox{order }-2)} 146\end{equation} 147, assuming Hermitian interpolation, where for other interpolation 148schemes the $-2$ may change to $-1$. 149\begin{figure}[hbt] 150 \centerline{\includegraphics[width=3cm]{levels_nbc.pdf}} 151 \caption{2-level, no boundaries, 4-order, ratio 2, $n_1 = 13$, 152 $n_2 = 9$, $d_1 = \frac{6}{5}d_0$, $d_2 = \frac{8}{5}d_0$.} 153 \label{fig:levels_nbc} 154\end{figure} 155\\ 156From experiments we see that the number of grid points in each 157dimension for the coarsest grid should be at least the double of the interpolation order, 158this yields especially for vacuum. Further the 159number of grid points for the finest grid should reflect a mesh size 160of the order of the average distance between particles. 161 162%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 163\subsection{S - softening distance} 164 165\texttt{-s} defines the softening distance of the smoothed kernel 166$G_{smooth}(r)$. It defines also the local correction at 167each grid level. The softening distance is scaled according the ratio 168and the actual level. 169\\ 170An increased softening distance will increase the accuracy, but also 171the computational work. A softening distance of order of the simulation 172box results in a $O(N^2)$ time complexity. 173 174%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 175\subsection{Order} 176 177\texttt{-order} defines the interpolation order. The interpolation 178order must be even, where 4 and 6 stand for a {\it cubic} and 179{\it quintic} interpolation respectively. 180\\ 181From experiments we see that the interpolation order and the smoothing 182function $G_S(r)$ must correspond. 183 184%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 185\subsection{Ratio} 186 187\texttt{-ratio} defines the ratio of grid points between a fine and 188coarse grid. 189\\ 190Mostly 2 is used as ratio. For higher order interpolations a ratio 191more than 2 may be an option. 192 193%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 194\subsection{Gridsize} 195 196\texttt{-h} defines the size (length, not grid points) of the finest 197grid. It's optional and only available for vacuum.\\ 198 199%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 200\subsection{Origin - optional} 201\texttt{-origin} defines the origin of the finest grid. It's optional 202and only available for vacuum. The same applies as 203for \texttt{-h}. 204 205 206%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 207\subsection{Compilation} 208 209For experimental purpose the multi grid has several conditional compilation 210flags.\\ 211\begin{tabular}{cp{7cm}} 212\texttt{\small DEBUG\_MULTIGRID} & Debug\\ 213\texttt{\small DEBUG\_MULTIGRID\_TIMING} & Printing the different timings\\ 214\end{tabular} 215 216%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 217\end{document} 218%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 219