ABSTRACTThe solution of systems of equations can employ preconditioning of the involved operators. This preconditioning process aims at accelerating convergence and requires some estimate of the solution or of the operator behavior. I outline a preconditioning operation for use with wave equations having the aim of increasing the region of stability of the evolution equation.
A well known mathematical/numerical tool in solving large systems of equations is the use of a preconditioner. Nichols outlines the characteristics of the left and right preconditioner for an algebraic system of equations. I try to extend this method from its inversion problem setting to the wave equation setting and reinterpret its consequences. Following expositions by Tal-Ezer , I am trying to find an efficient preconditioner for solving wave equation problems. A proper preconditioner for wave equation problems should ideally help with two aspects, namely stability and accuracy. Numerical dispersion is viewed as part of the accuracy problem.
THE GENERAL WAVE EQUATION A general second order wave equation can be written as
In the following, let us look at the time evolution problem, but keep in mind that it actually represents any general evolution/extrapolation problem. One will then seek to solve a related problem using an operator P
THE GENERAL FORM The task for P, where is a parametric preconditioner, is as always, to decolor the right hand side of equation full. P is a system of preconditioners and we can see what the preconditioner does to the original solution u by expanding equation full
If the last term is dropped with the argument that is assumed to be very small, we get the preconditioned problem pregen. In this general notation
In the most general case the preconditioner P will depend on the discretization of the derivative operator, the medium, and thus on the wave types within the medium. However, a simple representation can still be found that should allow increased range of stability and accuracy.
In order to understand the problem, one can simplify it to include only one wave type (scalar problem) in one space dimension. Equation full reduces then to the familiar:
Assuming one would like to extrapolate equation scalar1d in time, we are confronted with a basic problem resulting from the nature of this equation. First, the source term has a certain frequency content that gets injected at each time step. Second, the medium is characterized by a heterogeneous velocity v that introduces potentially high spatial wave numbers. Thus the solution to this equation is possibly highly oscillatory.
Imagine for a moment that for some reason the right hand side of equation scalar1d is not oscillatory, but smooth. If this thought is taken to the extreme, it could be a constant function. Then, extrapolating u would be easy, since we know how to extrapolate a constant function. In reality, we will hardly be able to get the right hand side of equation scalar1d to be constant, except for very special media and special sources. However, we could recast the problem scalar1d and solve a slightly different problem
We can now ask ourselves, how we could choose Q such that extrapolation of equation scalarpre1d is quick and efficient, despite the fact that v might be blocky, discontinuous, and heterogeneous and u highly oscillatory. If would be smooth, then utt and u would be band-limited and low frequency, and predictability along the extrapolation axis would be good. For example, a sinusoid is predictable and can be extrapolated without much of a problem.
Taking this idea to the extreme would require us to have Q such that is a constant function. How to extrapolate a constant function would now be self-evident.
We see then what the preconditioner for the wave equation extrapolation should do: effectively lower the frequency content in in such a way that the extrapolation is stable in larger regions and thus allows us to take bigger time steps with higher accuracy.
THE CHOICE OF PRECONDITIONER
Accepting the previously outlined role of the function Q as a preconditioner, we are faced with the problem of how to determine Q in reality. What Q should we actually use for preconditioning? Clearly the source term s and the spatial operator in equation scalar1d influence the choice. More specifically, it is the temporal and spatial frequency of the source term s and the spatial frequency content of the discretization of the medium operator .Obviously, choosing Q to satisfy
Choosing Q = s-1 would decolor the source completely, but would not modify contributions that are introduced by the medium operator D. Clearly, the source s and the solution u are not totally independent, but we can always argue that the frequency content of u is similar to s modulo contributions from the medium operator term. A preconditioner that would attempt to decolor the right hand side under the assumptions that the frequency content of u and s is similar to
Retaining only the first factor in equation splitprecon, we get a preconditioner that only depends on the medium operator itself, namely
A PARAMETRIC PRECONDITIONER Equation mediumprecon gives preconditioner Q that is fixed for the entire evolution problem. Since the evolution problem is not like an optimization problem, we might argue that a variation of the preconditioner during the evolution process is a good idea. This is true, of course, if we have a strategy of choosing Q appropriately, such as to increase convergence, accuracy or stability. A reasonable choice is the form
SHAPE OF PRECONDITIONERS In the previous paragraph we saw how a preconditioning operator can be chosen for a wave propagation problem. But, now that we know how to design a preconditioning operator, we are faced with the problem of how to apply it. In this section I explain an approximation procedure and in the next I show how to apply it implicitly, but exactly.
Take again the parametric preconditioner epsprecon that can be discretized with a simple second order stencil in one space dimension:
Accepting the fact that we want to approximate efficiently the inverse of operator simplemat, we can try it using another tridiagonal matrix
PRECONDITIONERS AND IMPLICIT SOLUTIONS An alternative to using an approximation such as equation simplematinv is to solve equation scalarpre1d implicitly. Consequently, we would solve it in the following form
As can be seen in equation timestep, we have to solve implicitly for a un+1. It is a system of simultaneous equations where uin+1 are coupled spatially depending on the spatial discretization operator , such that the number of unknowns corresponds to the number of convolution coefficients in the operator. We solve that system at each time step. Thus implicit time stepping can be viewed as an implicit preconditioning of the solution to the original wave equation.
Solving the wave equation implicitly is only efficient if the time step can now be chosen to be larger than the explicit solution would give. However, the solution of the system of equations at each time step slows the algorithm down. Consequently, there is a potential inefficiency. Note also the similarity of the implicit preconditioner to methods such as Crank-Nicholson.
MORE THAN ONE DIMENSION In the previous sections I restricted myself to a wave propagation problem in one space dimension in order to give illustrative examples. In 2D or 3D the scalar wave equation illuminates still some more interesting points. The 3D scalar wave equation takes on this form
Choosing optimally During the time stepping the preconditioner can be varied, in particular via the small parameter . As an upper bound one can require that has to be chosen such that the energy in the timestepped terms is less than some tolerance
A similar solution is
Wave propagation problems can be tackled using the numerical tool of preconditioning. The task of a preconditioner in a wave propagation setting is to increase for a numerical solution the range of stability and rate of convergence to the correct solution. In solving evolution equations an efficient preconditioner has to be found that depends on the discretization of the spatial medium operator. Implicit solutions of wave equations implicitly precondition the original problem. Second order scalar wave equations in 1D serve as illustrative examples and lead to a general preconditioning formulation for general wave propagation problems.
I enjoyed working together with SEP's visitor Hillel Tal-Ezer from Tel Aviv University, who pointed me in the direction of preconditioning partial differential equations.