next up previous
Next: The Interpolated Rectilinear Scheme Up: Finite Difference Schemes for Previous: Finite Difference Schemes for

The Rectilinear Scheme

The finite difference scheme corresponding to a rectilinear mesh is obtained by applying centered differences to the wave equation, over a rectangular grid with indices $ i$ and $ j$ (which refer to points with spatial coordinates $ x=i\Delta$ and $ y=j\Delta$). The difference scheme, given originally as (4.53) is

\begin{displaymath}\begin{split}U_{i,j}(n+1)+U_{i,j}(n-1) &= \lambda^{2}\Big(U_{...
...\ &\quad\quad+\left(2-4\lambda^{2}\right)U_{i,j}(n) \end{split}\end{displaymath} (A.14)

and the amplification polynomial equation is of the form (A.5), with

$\displaystyle B_{\mbox{{\scriptsize\boldmath$\beta$}}} = -2\Big(1+\lambda^{2}\left(\cos(\beta_{x}\Delta)+\cos(\beta_{y}\Delta)-2\right)\Big)$    

for $ \beta$ $ = [\beta_{x},\beta_{y}]^{T}$. From (A.7), we thus have

$\displaystyle F_{\mbox{{\scriptsize\boldmath$\beta$}}} = \cos(\beta_{x}\Delta)+\cos(\beta_{y}\Delta)-2$    

and we have

$\displaystyle \max_{\mbox{{\scriptsize\boldmath$\beta$}}}F_{\mbox{{\scriptsize\...
...ox{{\scriptsize\boldmath$\beta$}}}F_{\mbox{{\scriptsize\boldmath$\beta$}}} = -4$    

Condition (A.8) is thus satisfied, and condition (A.9) gives the bound

$\displaystyle \lambda\leq\frac{1}{\!\!\sqrt{2}}$   for stability    

which implies that the amplification factor $ \vert G_{\mbox{{\scriptsize\boldmath $\beta$}}, \pm}\vert = 1$ for such values of $ \lambda $. Because $ \lambda = \gamma/v_{0}$, this bound is the same as the bound for passivity of the associated mesh scheme, given in (4.63). The amplification factors, however, are distinct at all spatial frequencies only for $ \lambda< 1/\sqrt{2}$. If $ \lambda =1/\sqrt{2}$, then the factors are degenerate for $ \beta_{x}=\beta_{y}=0$, and for $ \beta_{x}=\beta_{y}= \pm\pi/\Delta$ and we are then in the situation discussed in §A.1.2 where linear growth of the solution may occur. This is an important special case, because it corresponds to the standard finite difference scheme for the rectilinear waveguide mesh (i.e., the realization without self-loops). The waveguide mesh implementation does not allow such growth at these frequencies% latex2html id marker 88711

Figure A.1: The rectilinear scheme (A.13)-- (a) grid, of spacing $ \Delta$, where grey/white coloring indicates a subgrid decomposition possible when $ \lambda =1/\sqrt{2}$. (b) $ v_{\mbox{{\scriptsize\boldmath$\beta$}}, phase}/\gamma$ for $ \lambda =1/\sqrt{2}$. Contour lines are drawn, representing successive deviations of 2 per cent from the ideal value of 1 which is obtained at spatial DC. (c) $ v_{\mbox{{\scriptsize\boldmath$\beta$}}, phase}/\gamma$ away from the stability bound, for $ \lambda = 1/2$.
\end{picture} \end{center} \vspace{0.5in}

As far as assessing the computational requirements of the finite difference scheme, first consider the case $ \lambda< 1/\sqrt{2}$. Five adds are required at each grid point in order to update. Given that $ T = \Delta/v_{0}$, we can write the computational and add densities for the scheme as

$\displaystyle \rho_{rect} = \frac{v_{0}}{\Delta^{3}}\hspace{0.3in}\sigma_{rect} = \frac{5v_{0}}{\Delta^{3}}$   for$\displaystyle \hspace{0.3in}v_{0}>\sqrt{2}\gamma$    

For $ \lambda =1/\sqrt{2}$, however, scheme (A.13) simplifies to

$\displaystyle U_{i,j}(n+1)+U_{i,j}(n-1) = \frac{1}{2}\Big(U_{i+1,j}(n)+U_{i-1,j}(n)+U_{i,j+1}(n)+U_{i,j-1}(n)\Big)$ (A.15)

which may be operated on alternating grids, i.e., $ U_{i,j}(n)$ need only be calculated for $ i+j+n$ even (or odd). The computational and add densities, for $ \lambda =1/\sqrt{2}$ are then

$\displaystyle \rho_{rect}^{s} = \frac{v_{0}}{2\Delta^{3}}\hspace{0.3in}\sigma_{rect}^{s} = \frac{2v_{0}}{\Delta^{3}}$   for$\displaystyle \hspace{0.3in}v_{0}=\sqrt{2}\gamma$    

where we note that the reduced scheme (A.14) requires only four adds for updating at a given grid point; in addition, the multiplies by $ 1/2$ may be accomplished, in a fixed-point implementation, by simple bit-shifting operations. The increased efficiency of this scheme must be weighed against the danger of instability, and the fact that because grid density is reduced, the scheme is now applicable over a smaller range of spatial frequencies. The numerical phase velocities of the schemes, at the stability limit, and away from it, at $ \lambda = 1/2$, are plotted in Figure A.1. It is interesting to note that away from the stability limit, the numerical dispersion is somewhat less directionally-dependent; this important factor may be useful from the point of view of frequency-warping techniques [157] which may be used to reduce numerical dispersion effects for schemes which are relatively directionally-independent. This idea has been discussed in the waveguide mesh context (where self-loops will be present) in [175].

next up previous
Next: The Interpolated Rectilinear Scheme Up: Finite Difference Schemes for Previous: Finite Difference Schemes for
Stefan Bilbao 2002-01-22