... | @@ -83,27 +83,27 @@ an observation location latexmath:[(x,y,z)]. |
... | @@ -83,27 +83,27 @@ an observation location latexmath:[(x,y,z)]. |
|
|
|
|
|
For an isolated distribution of charge this reduces to
|
|
For an isolated distribution of charge this reduces to
|
|
|
|
|
|
|
|
[[eq:convolutionsolution]]
|
|
[latexmath]
|
|
[latexmath]
|
|
++++
|
|
++++
|
|
\phi(x,y,z)=\int\int\int{\mathrm{d}x' \,\mathrm{d}y' \,\mathrm{d}z'}\rho(x',y',z') G(x-x',y-y',z-z'),
|
|
\phi(x,y,z)=\int\int\int{\mathrm{d}x' \,\mathrm{d}y' \,\mathrm{d}z'}\rho(x',y',z') G(x-x',y-y',z-z'),
|
|
\label{eq:convolutionsolution}
|
|
|
|
++++
|
|
++++
|
|
|
|
|
|
where
|
|
where
|
|
|
|
|
|
|
|
[[eq:isolatedgreenfunction]]
|
|
[latexmath]
|
|
[latexmath]
|
|
++++
|
|
++++
|
|
G(u,v,w)={\frac{1}{\sqrt{u^2+v^2+w^2}}}.
|
|
G(u,v,w)={\frac{1}{\sqrt{u^2+v^2+w^2}}}.
|
|
\label{eq:isolatedgreenfunction}
|
|
|
|
++++
|
|
++++
|
|
|
|
|
|
A simple discretization of Equation [convolutionsolution] on a Cartesian
|
|
A simple discretization of Equation [convolutionsolution] on a Cartesian
|
|
grid with cell size latexmath:[(h_x,h_y,h_z)] leads to,
|
|
grid with cell size latexmath:[(h_x,h_y,h_z)] leads to,
|
|
|
|
|
|
|
|
[[eq:openbruteforceconvolution]]
|
|
[latexmath]
|
|
[latexmath]
|
|
++++
|
|
++++
|
|
\phi_{i,j,k}=h_x h_y h_z \sum_{i'=1}^{M_x}\sum_{j'=1}^{M_y}\sum_{k'=1}^{M_t} \rho_{i',j',k'}G_{i-i',j-j',k-k'},
|
|
\phi_{i,j,k}=h_x h_y h_z \sum_{i'=1}^{M_x}\sum_{j'=1}^{M_y}\sum_{k'=1}^{M_t} \rho_{i',j',k'}G_{i-i',j-j',k-k'},
|
|
\label{eq:openbruteforceconvolution}
|
|
|
|
++++
|
|
++++
|
|
|
|
|
|
where latexmath:[\rho_{i,j,k}] and latexmath:[G_{i-i',j-j',k-k'}]
|
|
where latexmath:[\rho_{i,j,k}] and latexmath:[G_{i-i',j-j',k-k'}]
|
... | @@ -118,6 +118,7 @@ FFTs can be used to compute convolutions by appropriate zero-padding of |
... | @@ -118,6 +118,7 @@ FFTs can be used to compute convolutions by appropriate zero-padding of |
|
the sequences. Discrete convolutions arise in solving the Poisson
|
|
the sequences. Discrete convolutions arise in solving the Poisson
|
|
equation, and one is typically interested in the following,
|
|
equation, and one is typically interested in the following,
|
|
|
|
|
|
|
|
[[eq:bruteforceconvolution]]
|
|
[latexmath]
|
|
[latexmath]
|
|
++++
|
|
++++
|
|
\bar{\phi}_j=\sum_{k=0}^{K-1}\bar{\rho}_k \bar{G}_{j-k}\quad,
|
|
\bar{\phi}_j=\sum_{k=0}^{K-1}\bar{\rho}_k \bar{G}_{j-k}\quad,
|
... | @@ -126,7 +127,6 @@ j=0,\ldots,J-1 \\ |
... | @@ -126,7 +127,6 @@ j=0,\ldots,J-1 \\ |
|
k=0,\ldots,K-1 \\
|
|
k=0,\ldots,K-1 \\
|
|
j-k=-(K-1),\ldots,J-1 \\
|
|
j-k=-(K-1),\ldots,J-1 \\
|
|
\end{array}
|
|
\end{array}
|
|
\label{eq:bruteforceconvolution}
|
|
|
|
++++
|
|
++++
|
|
|
|
|
|
where latexmath:[\bar{G}] corresponds to the free space Green
|
|
where latexmath:[\bar{G}] corresponds to the free space Green
|
... | @@ -153,6 +153,7 @@ latexmath:[\rho], |
... | @@ -153,6 +153,7 @@ latexmath:[\rho], |
|
Define a periodic Green function,
|
|
Define a periodic Green function,
|
|
latexmath:[G_m], as follows,
|
|
latexmath:[G_m], as follows,
|
|
|
|
|
|
|
|
[[eq:periodicgreenfunction]]
|
|
[latexmath]
|
|
[latexmath]
|
|
++++
|
|
++++
|
|
G_m=\left\{
|
|
G_m=\left\{
|
... | @@ -161,18 +162,17 @@ G_m=\left\{ |
... | @@ -161,18 +162,17 @@ G_m=\left\{ |
|
0 & \quad \text{if }m=J,\ldots,N-K, \\
|
|
0 & \quad \text{if }m=J,\ldots,N-K, \\
|
|
G_{m+iN}=G_{m} & \quad \text{for } i \text{ integer }.
|
|
G_{m+iN}=G_{m} & \quad \text{for } i \text{ integer }.
|
|
\end{array}\right.
|
|
\end{array}\right.
|
|
\label{eq:periodicgreenfunction}G
|
|
|
|
++++
|
|
++++
|
|
|
|
|
|
Now consider the sum
|
|
Now consider the sum
|
|
|
|
|
|
|
|
[[eq:fftconvolution]]
|
|
[latexmath]
|
|
[latexmath]
|
|
++++
|
|
++++
|
|
{\phi}_j=\frac{1}{N}\sum_{k=0}^{N-1} W^{-jk}
|
|
{\phi}_j=\frac{1}{N}\sum_{k=0}^{N-1} W^{-jk}
|
|
\left(\sum_{n=0}^{N-1} \rho_n W^{nk}\right)
|
|
\left(\sum_{n=0}^{N-1} \rho_n W^{nk}\right)
|
|
\left(\sum_{m=0}^{N-1} G_m W^{mk}\right),
|
|
\left(\sum_{m=0}^{N-1} G_m W^{mk}\right),
|
|
~~~~~~0 \le j \le N-1,
|
|
~~~~~~0 \le j \le N-1,
|
|
\label{eq:fftconvolution}
|
|
|
|
++++
|
|
++++
|
|
|
|
|
|
where latexmath:[W=e^{-2\pi i/N}]. This
|
|
where latexmath:[W=e^{-2\pi i/N}]. This
|
... | @@ -206,11 +206,11 @@ It follows that |
... | @@ -206,11 +206,11 @@ It follows that |
|
But latexmath:[G] is periodic with period
|
|
But latexmath:[G] is periodic with period
|
|
latexmath:[N]. Hence,
|
|
latexmath:[N]. Hence,
|
|
|
|
|
|
|
|
[[eq:finaleqn]]
|
|
[latexmath]
|
|
[latexmath]
|
|
++++
|
|
++++
|
|
{\phi}_j=\sum_{n=0}^{K-1}~\bar{\rho}_n G_{j-n}
|
|
{\phi}_j=\sum_{n=0}^{K-1}~\bar{\rho}_n G_{j-n}
|
|
~~~~~~0 \le j \le N-1.
|
|
~~~~~~0 \le j \le N-1.
|
|
\label{eq:finaleqn}
|
|
|
|
++++
|
|
++++
|
|
|
|
|
|
In the physical (unpadded) region,
|
|
In the physical (unpadded) region,
|
... | @@ -246,6 +246,7 @@ latexmath:[W^{j k}] and latexmath:[W^{-m k}], respectively, in |
... | @@ -246,6 +246,7 @@ latexmath:[W^{j k}] and latexmath:[W^{-m k}], respectively, in |
|
Equation [fftconvolution]. In other words, the FFT-based approach can be
|
|
Equation [fftconvolution]. In other words, the FFT-based approach can be
|
|
used to compute
|
|
used to compute
|
|
|
|
|
|
|
|
[[eq:bruteforcecorrelation]]
|
|
[latexmath]
|
|
[latexmath]
|
|
++++
|
|
++++
|
|
\bar{\phi}_j=\sum_{k=0}^{K-1}\bar{\rho}_k \bar{G}_{j+k}\quad,
|
|
\bar{\phi}_j=\sum_{k=0}^{K-1}\bar{\rho}_k \bar{G}_{j+k}\quad,
|
... | @@ -254,7 +255,6 @@ j=0,\ldots,J-1 \\ |
... | @@ -254,7 +255,6 @@ j=0,\ldots,J-1 \\ |
|
k=0,\ldots,K-1 \\
|
|
k=0,\ldots,K-1 \\
|
|
j-k=-(K-1),\ldots,J-1 \\
|
|
j-k=-(K-1),\ldots,J-1 \\
|
|
\end{array}
|
|
\end{array}
|
|
\label{eq:bruteforcecorrelation}
|
|
|
|
++++
|
|
++++
|
|
|
|
|
|
simply by changing the direction of
|
|
simply by changing the direction of
|
... | @@ -268,10 +268,10 @@ Algorithm used in _OPAL_ |
... | @@ -268,10 +268,10 @@ Algorithm used in _OPAL_ |
|
As a result, the solution of Equation [openbruteforceconvolution] is
|
|
As a result, the solution of Equation [openbruteforceconvolution] is
|
|
then given by
|
|
then given by
|
|
|
|
|
|
|
|
[[eq:oneterm]]
|
|
[latexmath]
|
|
[latexmath]
|
|
++++
|
|
++++
|
|
\phi_{i,j,k}=h_x h_y h_z \text{FFT}^{-1} \{ ( \text{FFT}\{\rho_{i,j,k}\}) ( \text{FFT}\{G_{i,j,k}\}) \}
|
|
\phi_{i,j,k}=h_x h_y h_z \text{FFT}^{-1} \{ ( \text{FFT}\{\rho_{i,j,k}\}) ( \text{FFT}\{G_{i,j,k}\}) \}
|
|
\label{eq:oneterm}
|
|
|
|
++++
|
|
++++
|
|
|
|
|
|
where the notation has been introduced that
|
|
where the notation has been introduced that
|
... | | ... | |