The subject of this thesis is the numerical simulation of physical systems. In particular, we look at systems which are dynamic and distributed. By dynamic, we mean that the system's state evolves as time progresses, and by distributed, that the system is defined over some region in space, called the problem domain. The systems of interest here, always described mathematically by sets of partial differential equations (PDEs) complemented by initial and boundary conditions and possibly external excitations, span a large range of physical scenarios, including electromagnetics, acoustics, transmission lines, the vibration of elastic systems such as strings, membranes, beams, plates and shells, and even nonlinear fluid dynamics.
The simulation techniques that we will discuss are based on analogies between the systems mentioned above and electrical networks, and make use of scattering principles. The time-evolution of the state of a system is modeled as the movement of energy as it is reflected, transmitted and propagated throughout an electrical network; the energy is carried by waves. The chief benefit of a network formulation is that there is direct access to a measure of the system energy, which can be used to bound the size of the solution of the system as it evolves over time. Because many physical systems, in the absence of external excitations, are inherently passive (i.e., they do not produce energy on their own), a network model for a system of PDEs is useful in that this passivity is reflected in an obvious way; a simple positivity condition on all the circuit element values is all that is required. When such a network model is transferred to a discrete setting in an appropriate way (where it will eventually be implemented as a computer program, operating as a recursion over a numerical grid), this passivity condition becomes a sufficient and trivially verifiable condition for the numerical stability of the resulting simulation. It is interesting that these numerical methods have their roots in digital filter design techniques, which were, in turn, based on discrete physical models of mechanical or electrical circuit elements and the connections between them. In a sense, then, simulation is a more ``natural'' use for these structures than filtering. Many important ideas regarding the good behavior of these methods in finite machine arithmetic, however, were first introduced in the filtering context--these also result from passivity in the network model.
We will be primarily concerned with two such methods. The first is based on wave digital filtering, a filter design technique which was initially intended as a means of translating a lumped analog electrical filtering network into discrete time, while preserving its topology and energetic properties (passivity in particular). Because the voltages and currents in a closed analog electrical network will evolve according to a set of ordinary differential equations (ODEs), these digital filter networks can also be viewed as numerical integration methods. The extension of wave digital filters to multiple dimensions, in which case they are referred to as multidimensional wave digital filters (MDWDFs), is direct and makes use of a distributed network formulation of a given system as a means of arriving at a simulation routine. Here there is a compact (though quite abstract) multidimensional circuit representation of the model system of PDEs, just as a lumped network is a representation of a system of ODEs. Despite the sometimes abstruse formalism underlying the construction of MDWDFs for simulation (invoking various coordinate changes, spectral mappings, and the use of non-physical ``circuit elements'' which are distributed, and may have a directional character), these numerical methods always involve the scattering of digital signals over a numerical grid of nodes which fills the problem domain, and are straightforward to program.
The second method, though very similar to the first from the standpoint of the programmer, in that the basic signal processing operation is the scattering of wave variables, is of a seemingly different origin. Here, the network is composed of a large number of connected elements, which are essentially transmission lines, or waveguides, so as to fill the problem domain. Wave propagation along a given waveguide is modeled, in discrete time, by a pair of digital delay lines which transport wave signals in opposite directions. A digital waveguide network (DWN), then, is usually thought of as a large network of lumped elements; there is traditionally not a multidimensional representation, as there is for MDWDFs. We will spend some time looking at the relationship between DWNs and the MDWD networks mentioned above.
These network approaches are relative newcomers in the field of numerical simulation. There are, of course, many other, older ways of designing a simulation method; the most well-established and straightforward tack makes use of finite difference approximations to the model system of PDEs. Partial derivatives are replaced by differences between quantities on a numerical grid, and a recursion (or difference scheme) results. These methods are simpler to program, but the wave/scattering interpretation is lost, and the verification of numerical stability can be very involved, especially in the presence of boundary conditions. Because the electrical network models mentioned above also operate, ultimately, as recursions on grids, it is reasonable to ask how scattering methods fit into the finite difference picture. The eventual identification of scattering methods with standard finite difference methods may come as something of a disappointment to anyone who feels that these methods are completely novel. It is best, however, to think of these methods as a different way of organizing calculation, which leads to more robust numerical behavior. As might be expected, an analogous situation exists in filter design between direct form and ladder/lattice/orthogonal structures.
The most general goal of this thesis is to provide a unified picture of how these scattering methods are related to each other and to finite differences. It is possible to rephrase this goal as an attempt to answer a basic set of questions; we will pose these questions in §1.2. Before we get to that stage, however, it is useful to outline the basics of these methods in a little more detail.