martin@sep.stanford.edu

## 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

(1) |

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*

(2) |

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

(3) |

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

(4) |

(5) |

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:

(6) |

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

(7) |

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 *u*_{tt} 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

(8) |

Choosing *Q* = *s ^{-1}* would decolor the source completely, but
would not modify contributions that are introduced by the medium operator

(9) |

Retaining only the first factor in equation splitprecon, we get a preconditioner that only depends on the medium operator itself, namely

(10) |

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

(11) |

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:

(12) |

Accepting the fact that we want to approximate efficiently the inverse of operator simplemat, we can try it using another tridiagonal matrix

(13) |

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

(14) |

(15) |

(16) |

As can be seen in equation timestep, we have to solve implicitly
for a *u*^{n+1}. It is a system of simultaneous equations where
*u*_{i}^{n+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

(17) |

(18) |

(19) |

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

(20) |

A similar solution is

(21) | ||

(22) | ||

(23) |

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.

[SEP,paper]

5/11/2001