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