Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

FDTD and DW Equivalence

The FDTD and DW recursions both compute time updates by forming fixed linear combinations of past state. As a result, each can be described in ``state-space form'' [452, Appendix G] by a constant matrix operator, the ``state transition matrix'', which multiplies the state vector at the current time to produce the state vector for the next time step. The FDTD operator propagates K variables while the DW operator propagates W variables. We may show equivalence by (1) defining a one-to-one transformation which will convert K variables to W variables or vice versa, and (2) showing that given any common initial state for both schemes, the state transition matrices compute the same next state in both cases.

The next section shows that the linear transformation from W to K variables,

$\displaystyle y(n,m) = y^{+}(n-m) + y^{-}(n+m), \protect$ (E.7)

for all $ n$ and $ m$ , sets up a one-to-one linear transformation between the K and W variables. Assuming this holds, it only remains to be shown that the DW and FDTD schemes preserve mapping Eq.$ \,$ (E.7) after a state transition from one time to the next. While this has been shown previously [445], we repeat the derivation here for completeness. We also provide a state-space analysis reaching the same conclusion in §E.4.

From Fig.E.1, it is clear that the DW scheme preserves mapping Eq.$ \,$ (E.7) by definition. For the FDTD scheme, we expand the right-hand of Eq.$ \,$ (E.3) using Eq.$ \,$ (E.7) and verify that the left-hand side also satisfies the map, i.e., that $ y(n+1,m) = y^{+}(n+1-m) + y^{-}(n+1+m)$ holds:

\begin{eqnarray*}
y(n+1,m) &=& y(n,m+1) + y(n,m-1) - y(n-1,m) \\
&=& y^{+}(n-m-1) + y^{-}(n+m+1) \\
&& + y^{+}(n-m+1) + y^{-}(n+m-1) \\
&& - y^{+}(n-m-1) - y^{-}(n+m-1) \\
&=& y^{-}(n+m+1) + y^{+}(n-m+1) \\
&=& y^{+}[(n+1)-m] + y^{-}[(n+1)+m] \\
&\isdef & y(n+1,m) \nonumber
\end{eqnarray*}

Since the DW method propagates sampled (bandlimited) solutions to the ideal wave equation without error, it follows that the FDTD method does the same thing, despite the relatively crude approximations made in Eq.$ \,$ (E.2). In particular, it is known that the FDA introduces artificial damping when applied to first order partial derivatives arising in lumped, mass-spring systems [450].

The equivalence of the DW and FDTD state transitions extends readily to the DW mesh [520,450] which is essentially a lattice-work of DWs for simulating membranes and volumes. The equivalence is more important in higher dimensions because the FDTD formulation requires less computations per node than the DW approach in higher dimensions (see [33] for some quantitative comparisons).

Even in one dimension, the DW and finite-difference methods have unique advantages in particular situations [224], and as a result they are often combined together to form a hybrid traveling-wave/physical-variable simulation [354,355,223,124,123,225,265,33].


Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

[How to cite this work]  [Order a printed hardcopy]  [Comment on this page via email]

``Physical Audio Signal Processing'', by Julius O. Smith III, W3K Publishing, 2010, ISBN 978-0-9745607-2-4.
Copyright © 2014-06-11 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA