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

Distributed Problems and Coordinate Changes

Symmetric Hyperbolic Systems

Multidimensional time and space-dependent physical systems are often described by systems of PDEs which are symmetric hyperbolic. For example, in 1D, a typical situation is:

$\displaystyle {\bf P}\frac{\partial {\bf u}}{\partial t} = {\bf A}\frac{\partial {\bf u}}{\partial x} + {\bf Bu}$    

where $ {\bf P(x)}$ is symmetric, $ >0$ , and $ {\bf A(x)}$ is symmetric (both square, real). Can write:
$\displaystyle {\bf u^{T}P}\frac{\partial {\bf u}}{\partial t}$ $\displaystyle =$ $\displaystyle {\bf u^{T}A}\frac{\partial {\bf u}}{\partial x} + {\bf u^{T}Bu}$  
$\displaystyle \frac{1}{2}\frac{\partial {\bf u^{T}P u}}{\partial t}$ $\displaystyle =$ $\displaystyle \frac{1}{2}\frac{\partial {\bf u^{T}Au}}{\partial x} -\frac{1}{2}u^{T}\frac{\partial {\bf A}}{\partial x}u + \frac{1}{2}{\bf u^{T}(B+B^{T})u}$  

and integrating over the real line (assuming no boundaries,

$\displaystyle \frac{\partial}{\partial t}\int_{x}{\bf u^{T}Pu}dx = \int_{x}{\bf u^{T}\left(-A'+B+B^{T}\right)u}$    

CFL Criterion

Hyperbolic systems $ \rightarrow$ finite propagation speeds.

For explicit numerical methods on a grid, have a necessary stability condition on the time-step space-step ratio. In 1D, on a regular grid, only neighboring points:

$\displaystyle v_{0}\equiv \frac{{\rm space-step}}{{\rm time-step}}\geq\qquad{\rm maximum\qquad speed.}$    

(Courant-Friedrichs-Lewy Condition).


\begin{picture}(550,200)
\par
% graphpaper(0,0)(550,200)
\put(0,20){\epsfig{file=eps/cfl.eps}}
\put(550,85){$T$}
\put(435,200){$\Delta$}
\put(-100,150){{$t=(n+1)T$:}}
\put(-90,25){{$t=nT$:}}
\put(185,180){{\mbox{\rm {Current Point}}}}
\end{picture}
In higher-D, same general result, but extra factors appear (solution does not necessarily move along a grid direction).

In the network approaches, CFL appears in an elementary way as a constraint on the positivity of the circuit elements (for passivity).

Multidimensional Problems and Coordinate Transformation

Multidimensional (distributed) systems $ \rightarrow$ system of PDEs.

Time-dependent systems derived from conservation laws:

In order to obtain a multidimensional circuit representation of a system of PDEs, useful to consider coordinate changes

$\displaystyle {\bf u}=({\bf x},t)^{T}\rightarrow {\bf t} = (t_{1}\hdots t_{k})^{T}$    

New coordinates should be causal, in the sense that:

A simple set of linear coordinate transformations:

$\displaystyle {\bf t} = {\bf H}^{-1}{\bf Vu}$    

Remarks: A theoretical ``hack'' for extending passivity ideas to multi-D

A Simple Coordinate Change and Sampling

If we have only one spatial dimension, then coordinate change options are limited. The only suitable one (in this context) is

$\displaystyle \begin{bmatrix}t_{1}\\ t_{2}\\ \end{bmatrix}=\frac{1}{\sqrt{2}}\begin{bmatrix}1 &1\\ -1 & 1\\ \end{bmatrix} \begin{bmatrix}1 &\\ & v_{0}\\ \end{bmatrix} \begin{bmatrix}x\\ t\\ \end{bmatrix}$    

A simple rotation of the coordinates by 45 degrees. If we now define uniform grids in the two coordinate systems, we get:


\begin{picture}(600,220)
\par
\put(-125,-680){\epsfig{file=eps/coorch1dpic.eps}}
\end{picture}

Coordinate Changes in Higher Dimensions: Hexagonal Coordinates

The transformation defined by

$\displaystyle \mathbf{H} = \begin{bmatrix}\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}&0\\ \frac{1}{\sqrt{6}}&\frac{1}{\sqrt{6}}&-\sqrt{\frac{2}{3}}\\ \frac{1}{\sqrt{3}}&\frac{1}{\sqrt{3}}&\frac{1}{\sqrt{3}}\\ \end{bmatrix}$    

when uniformly ``sampled'' in the new coordinates gives rise to the following grid pattern (viewed in the original coordinate system):


\begin{picture}(600,220)
\par
\put(-125,-680){\epsfig{file=eps/coorchhexpic.eps}}
\end{picture}

Three different grids (white, grey, black points) which exist every third time step.

Rectangular coordinates

In order to generate a standard rectangular grid by uniformly sampling in the causal coordinates, need to use an embedding:

$\displaystyle \mathbf{H} = \begin{bmatrix}1&0&-1&0&0\\ 0&1&0&-1&0\\ 1&1&1&1&1 \end{bmatrix}$    

which maps $ (x,y,t)$ to a 5-dimensional space $ {\bf t}$ = (north+time , south+time , east+time, west+time, time alone), and we get a normal rectangular grid in $ (x,y)$ if we sample uniformly in the five directions

Picture is:


\begin{picture}(400,300)
\par
% graphpaper(0,0)(400,300)
\put(0,20){\epsfig{file=eps/rectcoord.eps}}
\put(410,190){$y$}
\put(410,50){$x$}
\put(200,330){$t$}
\put(310,220){$t_{1}$}
\put(310,300){$t_{2}$}
\put(80,230){$t_{4}$}
\put(80,300){$t_{3}$}
\put(210,250){$t_{5}$}
\end{picture}


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

Download Meshes.pdf
Download Meshes_2up.pdf
Download Meshes_4up.pdf

``Wave Digital Filters and Waveguide Networks for Numerical Integration of Time-Dependent PDEs'', by Stefan Bilbao<bilbao@ccrma.stanford.edu>, (From CCRMA DSP Seminar Presentation, Music 423).
Copyright © 2019-02-05 by Stefan Bilbao<bilbao@ccrma.stanford.edu>
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA  [Automatic-links disclaimer]