Part III
Wavelets and Partial Differential
Equations
Chapter 7
Wavelets and differentiation matrices
7.1 Previous wavelet applications to PDEs
Even though the field of wavelet theory has had a great impact on other fields, such as signal processing, it is not yet clear whether it will have a similar impact on numerical methods for solving partial differential equations (PDEs).
In the early nineties people were very optimistic because it seemed that the nice properties of wavelets would automatically lead to efficient solution meth-ods for PDEs. The reason for this optimism was the fact that many nonlinear PDEs have solutions containing local phenomena (e.g. formation of shocks) and interactions between several scales (e.g. turbulence). Such solutions can often be well represented in wavelet bases, as explained in the previous chapters. It was therefore believed that efficient wavelet-based numerical schemes for solving these PDEs would follow from wavelet compression properties [BMP90, LT90b, LPT92, HPW94, GL94, CP96, PW96, F+96, DKU96].
However, this early optimism remains to be honored. Wavelets have not had the expected impact on differential equations, partly because the computational work is not necessarily reduced by applying wavelet compression - even though the solution is sparsely represented in a wavelet basis. In the following chapters we will discuss some of the most promising approaches and shed some light on the obstacles that must be overcome in order to obtain successful wavelet-based PDE solvers.
Schematically, wavelet-based methods for PDEs can be separated into the fol-lowing classes:
Class 1: Methods based on scaling function expansions
The unknown solution is expanded in scaling functions at some chosen level
J
and is solved using a Galerkin approach. Because of their compact support, the scaling functions can be regarded as alternatives to splines or the piecewise poly-nomials used in finite element schemes. While this approach is important in its own right, it cannot exploit wavelet compression. Hence methods in this category are not adaptive [LT90a, QW93, WA94, LR94, Jam93, RE97]. However, this ap-proach has many points of interest. Leland Jameson [Jam93] has shown that one obtains a method which exhibits super convergence at the grid points, the order of approximation being twice as large as that of the projection of the solution onto the space spanned by scaling functions. Johan Wald´en [Wal96] has shown that the size of the differentiation filters grows faster than the optimal centered finite difference method of the same order. In the limit, as the order goes to infinity, it is shown that
R
0(x
;k)(x)dx
!(
;1)
k=k
forD
! 1. Finally, we mention that Teresa Regi´nska and others [RE97, EBR97] use scaling functions to regular-ize the solution of the sideways heat equation. This is an ill-posed problem in the sense that the solution does not depend continuously on the initial condition. By expanding the solution in scaling functions, high frequency components can be filtered away and continuous dependence of the initial condition is restored.Class 2: Methods based on wavelet expansions
The PDE is solved using a Galerkin approach as in the first class. In this case, however, the unknown solution is expressed in terms of wavelets instead of scaling functions so wavelet compression can be applied; either to the solution [LT90b], the differential operator [BCR91, Bey92, EOZ94, XS92], or both [CP96, BK97, PW96]. Several different approaches have been considered for exploiting the spar-sity of a wavelet representation. One is to perform all operations in the wavelet domain [BN96, BMP90, Wal96]. The operators are sparse but the number of sig-nificant coefficients in the solutions
N
s(")
has to be very small compared to the dimension of the problemN
for the methods to be efficient. This is especially true for non-linear operations. However, recent work by Beylkin and Keiser [BK97]suggests that some nonlinearities may be efficiently treated in the wavelet domain.
In another approach linear operations such as differentiation are done in the wavelet domain and nonlinear operations such as squaring in the physical domain.
This is by far the most common approach and it is used by [Kei95, CP96, FS97, PW96, EOZ94, VP96] and the author. This approach involves a number of trans-formations between the physical domain and the wavelet domain in each time step, and this can introduce considerable overhead. Hence, the wavelet compres-sion potential of the solution must be very large for this approach to be feasible.
An interesting aspect of the wavelet approach is that certain operators repre-sented with respect to a wavelet basis become sparser when raised to higher pow-ers [EOZ94]. From this property one can obtain an efficient time-stepping scheme for certain evolution equations. This method has been employed in [CP96, Dor95]
to solve the heat equation.
Finally, we mention that several papers have exploited the so-called Non-standard or BCR form of the differential operator [BCR91, Bey92, Dor95, BK97].
This form is sparser than the standard form, but to apply the non-standard form of the differential operator to a function one needs to know, at all scales, the scaling function coefficients of the function as well as its wavelet coefficients. This repre-sentation is redundant and, even though the function may be sparse in its wavelet representation, the scaling function representation may not be sparse.
We will refer to methods from Class
1
and2
as projection methods.Class 3: Wavelets and finite differences
In the third approach wavelets are used to derive adaptive finite difference meth-ods. Instead of expanding the solution in terms of wavelets, the wavelet transform is used to determine where the finite difference grid must be refined or coarsened to optimally represent the solution. The computational overhead is low because one works with point values in the physical representation. One approach was de-veloped by Leland Jameson, [Jam94, Jam96] under the name Wavelet Optimized Finite Difference Method (WOFD). Wald´en describes a filter bank method in [Wal96], Matts Holmstr¨om has introduced the Sparse Point Representation (SPR) in [Hol97], and also [PK91] have used wavelets to localize where to apply grid refinement.
Class 4: Other methods
There are a few approaches that use wavelets in ways that do not fit into any of the previous classes. Examples are operator wavelets [JS93, EL], anti-derivatives of wavelets [XS92], the method of travelling wavelets [PB91, WZ94], and wavelet-preconditioning [Bey94].
Operator wavelets are wavelets that are (bi-)orthogonal with respect to an in-ner product designed for the particular differential operator in question. This is not a general method since it works only for certain operators. The use of anti-derivatives of wavelets is similar to that of operator wavelets.
In the method of travelling wavelets, an initial condition is expanded using only a few wavelets which are then propagated in time. A disadvantage of this
method is that these few wavelets may be unable to express the solution after it has been propagated for a time.
Finally, in [Bey94] it is shown that any finite difference matrix representa-tion of periodized differential operators can be precondirepresenta-tioned so that the condi-tion number is O
(1)
. Furthermore, if the difference matrix is represented in a wavelet basis (the standard form) then the preconditioner is a diagonal matrix.Thus, wavelets play an auxiliary role in that they provide a means to reduce the condition number of the operator.
In this chapter and Chapter 8 we describe the necessary background for methods belonging to Class
1
and2
. In Chapter 9 we give some applications of these methods to PDEs, and we also illustrate the WOFD method from Class3
. We willnot discuss further methods belonging to class 4.