Wavelet-Based Numerical Homogenization.
A numerical homogenization procedure for elliptic differential equations is presented. It is based on wavelet decompositions of discrete operators in fine and  coarse scale components  followed by the elimination of the fine scale contributions. If the operator is in divergence form, this is preserved by the homogenization procedure. For periodic problems, results similar to classical effective coefficient theory are proved. The procedure can be applied to problems that are not cell-periodic.
Introduction
In many applications the problem and solution exhibit a number of different scales.
In certain cases we are interested in finding the correct coarse-scale features of the
solution without resolving the finer scales. The fine-scale features may be of lesser
importance, or they may be prohibitively expensive to compute. However, the fine
scales cannot be completely ignored because they contribute to the coarse scale
solution: the high frequencies of solution may combine with the high frequencies of
Research supported by Office of Naval Research grants N00014-92-J-1890 P00003 and N00014-
95-I-0272
y Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm
(mihai@nada.kth.se).
z Department of Mathematics, University of California, Los Angeles, California 90024
(engquist@math.ucla.edu) and Numerical Analysis and Computing Science, Royal Institute of
Technology, Stockholm.
the differential operator to yield low frequency components.
The homogenization problem can be stated in various formulations. A classical
formulation, see e.g. Bensoussan et al. [1], is the following: Consider a family of
operators indexed by the small parameter ", and for a given f , let u " solve the
problem
Assume that homogenization problem is to find an operator
L and f such that:
For example, consider the following operator with oscillating coefficients
d
dx
d
dx
where a(x) is a positive 1-periodic function bounded away from zero. Then it is easy
to show that and the limit u satisfies a constant
coefficients equation. The coefficient is not the average of a(x) over a period, but
rather the harmonical average
a
also called the effective coefficient. The homogenized operator is
since
f:
In practice, we often need to solve the equation (1) for a small but fixed ". Since
close to u, we may solve the homogenized equation (2) instead of the original
equation. The homogenized equation is usually much simpler to solve. In the case
of effective coefficients, the solution of the homogenized equation contains no high
frequency components and thus it is an approximation to the coarse scale behavior
of
In a very interesting paper, M. E. Brewster and G. Beylkin [3] describe a homogenization
procedure based on a multi-resolution analysis (MRA) decomposition. They
consider integral equations, which may arise, e.g., from the Method of Lines discretization
of a PDE, and homogenize over the time-variable. In a MRA, the concept
of different scales is contained in the nested spaces V j . Homogenization is reduced
to projecting the solution of the original equation from the fine resolution space V n
onto the coarse resolution space V 0 . The homogenized operator, if it exists, operates
on the space V 0 , but in general it is not the projection of the original operator onto
the coarse space.
Many classical homogenization techniques are based on the essential assumption
that the coefficients are periodic on the fine scale. However, this does not hold
in many applications. The analytic expansions methods require an 'a priori known
number of scales, which again may be a serious restriction, see e.g., L. Durlofsky [7].
For two-dimensional elliptic operators with cell-periodic coefficients
@
the homogenized operator is
The effective coefficients A ij are found by computing
Z /
is the solution to the cell-problem:
@
@a ik
Wavelet-based homogenization can deal with both non-periodic coefficients on the
fine scale and use the all the scales involved from the fine-scale space V j to the
coarse-scale space V 0 .
Following the construction in [6], using the Haar system, we build a homogenized
operator L J for the discrete operator 1
. The grid-size is
are the forward and backward (undivided) difference operators. We show
that the homogenized operator has a natural structure of the form 1
where H is well approximated by a band diagonal matrix. In some cases, we prove
that H equals the effective coefficients predicted by the classical homogenization the-
ory, modulo a small error-term. In the two-dimensions, we show that our technique
preserves divergence form of operators.
We are concerned with a model of fine- and coarse-resolution spaces. The framework
is multi-resolution analysis or wavelet formalism. In this framework, we have the
concepts of fine and coarse scales together with the locality properties needed in
analyzing operators with variable coefficients.
For the precise definitions of a MRA, we defer the reader to the books by I.
Daubechies [4] and Y. Meyer [9]. We consider a ladder of spaces V J ae V J+1 which
are spanned by the dilates and integer translates of one shape-function
The functions ' J;k form an L 2 -orthonormal basis. The orthogonal complement of
V J in V J+1 is denoted by W J and it is generated by another orthonormal basis
is called the mother wavelet. The transformation
that mapping the basis f' J+1;k g into f/ J;k ; ' J;k g is an orthogonal operator and
we denote its inverse by W ? . The product W J
called the wavelet transform and it can be optimally implemented
(called the fast wavelet transform). We denote by P j and Q j the L 2 -projections onto
If an operator L J+1 is acting on the space V J+1 , it can be decomposed
into four operators L acting on the subspaces W J and V J ,
where
As a shorthand notation we have that
or simply
Note that if evaluated on a basis, the operator notation becomes a legitimate block-
matrix construction.
The identification of a function f 2 V J with the sequence c of coefficients in the
basis ' J;K is an isometry: If
Unless otherwise specified, the jj:jj notation refers to the corresponding 2-norm (con-
tinuous or discrete). The same holds for the inner-product notation.
Our results are proven in the simplest multi-resolution analysis, the Haar system.
The shape function is the indicator function of the interval [0 1] and the mother
wavelet is
The Haar system provides an orthonormal basis in both L 2 (R) and L 2 ([0 1]). The
space V J consists of piece-wise constant functions on a grid with step-size
It is identified with l 2 (or R 2 J
in the finite case).
The Haar transform from V J+1 to W J \Phi V J is simply:
3 Homogenization in the Haar Basis
Discretize the equation
d
dx
a
d
dx
on a uniform grid with using finite volumes. Let diag(a) be the diagonal
matrix containing the values of a(x) at the grid-points. As an operator on V J+1 ,
diag(a) represents multiplication by the grid-function a. The discrete equation
is split by the natural decomposition V
U l
F l
where the indices h and l denote the W J and V J components. The equation (3) is a
discretization of the continuous equation (a(x)u 0
The coarse scale solution of the discrete equation (3) is the projection of U onto V J ,
i.e. U l . Eliminating U h yields the equation for U l :
The homogenized operator is the Schur complement
Let us make some preliminary remarks:
ffl The homogenization procedure is in fact block Gaussian elimination. The idea
is not new, it can be found, e.g., in odd-even reduction techniques. There is a
real gain only if the homogenized operator L J can be well approximated by a
sparse matrix. It is the compression properties of wavelets that maintain the
homogenization procedure efficient, similar to the case of Calderon-Zygmund
operators as seen in [2, 5].
ffl The experience with the non-standard form representation of elliptic operators
indicate that A J has a strong diagonal dominance and thus its inversion will
not be as difficult as inverting the operator L J+1 , see [6].
ffl We expect that the homogenized operator L J will have a similar structure as
the operator L J . In fact we will see that if L J+1 is in divergence form,
where H is a strongly diagonal dominant matrix. We will call H the homogenized
coefficient matrix.
ffl The homogenization procedure can be applied recursively. If we have the
equation
that produces the solution on the scale then we
homogenize the operator L j+1 . This means that we produce the operator L j
on and the right-hand side f j such that the solution of the homogenized
equation
is
ffl If the homogenized operator has a rapid decay away from the diagonal, then
it can be well approximated by a band-diagonal operator. The same applies
for the matrix H.
The structure of the homogenized operator is given by the decomposition of the
discrete operators \Delta
and diag(a).
3.1 multiplication operator
We first examine the multiplication-by-functions operator diag(a). The following
lemma is obvious:
Lemma 1 If ' is the Haar system's shape function and / the mother wavelet, then
For we use the notation W J
a fi v denote the component-wise multiplication of vectors. We have the following
point-wise multiplication rule:
e a
e a fi e
Proof: Set a =
P a J+1;k ' J+1;k and
Using Lemma 1, we have
k;l
a J+1;k v J+1;l ' J+1;k ' J+1;l
a J+1;k v J+1;k
Thus point-wise multiplication of functions is the equivalent to component-wise
multiplication of the coefficients. Then we have:
e a k / J;k
e
which proves the statement.2
The high frequency components of a and v interact and contribute to the low frequency
part of the product av. This is modeled in the Haar basis by correcting the
product a fi v of the coarse scale coefficients with the fine scale contribution e a fi e v.
The structure of the pointwise multiplication operator is given by the following
statement:
Proposition 1 If W J
diag(a) diag(e a)
diag(e a) diag(a)7 5 :
The matrix diag(a) is the point-wise multiplication operator. We have the following
amusing result:
Proposition diag(a) be the multiplication-by-function operator on
. The coarse-grid projection P J M J+1 P J is multiplication by the arithmetical
averages (a 2k + a 2k+1 )=2 The homogenized operator M J is multiplication by the har-
monical averages ff
Proof: The coarse grid projection of diag(a) is 1=
2 diag(a), which is, in each
component, the arithmetical average (a 2k + a 2k+1 )=2 of the corresponding fine-grid
values. The homogenized operator ispi
Component-wise this
a k
2a 2k a 2k+1
which is the harmonical cell-average of the corresponding fine-grid values. 2
3.2 Decomposition of \Delta
We start by computing the decomposition W J \Delta +W
on the basis functions
of W J \Phi
Then we have
Similar computations yield
and then
Let S n be the shift matrix S n defined by S (n)
which is the projection of the
shift operator We have the following proposition:
Proposition 3 The decomposition of 1
in the Haar system is
Obviously, the structure is repeated at each level j. Since
, we have that
Dropping the diag notation in Proposition 1, we have that
p- A J
where A
3.3 Boundary conditions
The notations for the discrete difference operators and their corresponding
matrices. They can describe periodic, Neumann or Dirichlet boundary
conditions. They can also operate (as infinite matrices) on infinite sequences arising
from discretizing problems on the whole real axis.
The derivation of the decompositions of the L J+1 and the homogenized coefficient
matrix H are formally the same. However, in the periodic case, the operator L J+1
is singular and it is not trivial that A J is invertible.
In the periodic case, the matrices \Delta are circulant. This property is preserved
by the transform W J . If we define the shift matrices S \Sigma1 as circulant matrices,
then M is also circulant, and thus all the matrices corresponding to the level J have
the same property. In the infinite case, are trivially circulant.
With periodic boundary conditions, it is easy to show that L J+1 has a 1-dimensional
null-space spanned by the constant grid-functions: Since vanishes only on con-
stants, the ellipticity condition a ? 0 implies that any non-constant zero-eigenfunction
must satisfy constant. It follows that v is monotone, which contradicts
periodicity.
The null-space of L J+1 is transformed by W J into the one-dimensional space N
spanned by [0 is a constant grid-function. The quadratic form
J x is positive whenever x 62 N . In particular, putting
have
[y
for any y 6= 0. This proves that A J is positive definite and therefore invertible
and thus the homogenized operator L J is well-defined even with periodic boundary
conditions.
Both the equations L J+1 u need extra conditions. If we
decide e.g., to fix a boundary value, we can eliminate a row from both systems. This
elimination can be done after the homogenized operator is produced. Thus we need
not track the effect of the boundary condition through the homogenization process.
Other type of conditions, such as Dirichlet boundary conditions in the non-periodic
case or integral conditions can be handled in a similar fashion.
3.4 The homogenized coefficient matrix
Let us consider a discretization on the whole real axis, i.e., the case where the
matrices are infinite. The coarse-scale projection of L J+1 is
L J is the "wrong" operator for an obvious reason: the average coefficient is obtained
using only the even components of the the fine-scale coefficient a
L J is insensitive to variations of the odd-components in the original problem. Even
if the fine-scale is not present in a(x), i.e. e a = 0, L J still has the wrong coefficient
We build the homogenized operator as the Schur complement L
Proposition 4 The operator L J has a natural structure 1
a) (7)
Definition 1 We call H the homogenized coefficient matrix of the operator
The natural question to ask is if there is any connection between the homogenized
coefficient matrix H and the classical homogenized equations.
Proposition 2 gives that the Schur complement of the diagonal matrix a is the
diagonal matrix ff containing the harmonical averages of neighboring values. This
would then agree exactly with the classical homogenization theory, if the Schur
complement of \Delta could be expressed in terms of the Schur complement of the
middle factor a. Unfortunately, this is not the case, so we have to use the form given
in (7).
We look at the extreme case when is the sum of a constant and
the highest frequency represented on the grid, i.e., a(xm We have
that a and e a are represented as constant vectors in the bases of V J and W J . The
fact that a(x) ? 0 implies je aj ! a.
Since a and e a are constant vectors, we have
a)
where
Simple computations yield
and then
The homogenized coefficient matrix defined by (7) is
a)
Classical homogenization theory yields the effective equation ff d 2
where the effective
coefficient is given by the harmonical average:
Z 2ha(x)dx
a 0
In the rest of this section, we will be looking only at the coarse grid function space
J . For simplicity, we will let denote the grid-size of V J .
The following theorem shows that the numerically homogenized operator 1
equals the discrete form ff 1
of the classically homogenized equation, apart
from a second-order term in h.
Theorem 1 Let J+1 be such that a 2 V 0 is a constant and the
oscillatory part e
a 2 W J has constant amplitude and satisfies the condition j e aj ! a.
Let L
and ff be the harmonical average in (9). Then there exists
a constant C independent of the grid-size h such that if v is the discretization of a
function v(x) with a continuous and bounded fourth derivative, then
Proof: Let us show first that the high-frequency operator A J is invertible by showing
that it is diagonal dominant. We have
and the tridiagonal structure of A J is clearly seen. The ellipticity of L J+1 implies
that a. The diagonal entries of A J are larger then 4a while the sum of the
off-diagonal terms is smaller then the same amount. The diagonal dominance of A J
gives a rapid decay of the entries of A \Gamma1
J away from the diagonal. Indeed, we have
e a \Gamma a
1=2, the Neumann expansion for A \Gamma1
J is convergent and (10) reveals the
size of the off-diagonal entries:
A
I
Next we compute the row-sum of H. Note first that since A J is circulant, it has an
and the corresponding eigenvalue is 8a. A \Gamma1
J shares
the eigenvector c, which shows that all its row-sums are 1=(8a). Note that c is also
an eigenvector of I with the corresponding eigenvalue 2. Thus we have
a)
p2a
Finally we estimate L J v. Note that since
I
Assuming v is a discrete smooth function, Taylor expansion around v
Let us estimate the j component of Hv. Applying H to the first term in (12) produces
just ffv j . Due to symmetry, we have that
\Gamman ). Applying
H to the odd-order terms of (12) shifts in the j component quantities with opposite
signs and then adds them. The even-order terms contribute such that
show later that the coefficients fl n have exponential decay
and thus
is convergent for any k. Applying 1
comparing to
which in its turn gives the desired estimate with
It remains to be shown that the constant C is independent of the grid-size h. The
expansion (11) shows that A \Gamma1
J is generated infinite long stencil with exponential
decay rate 1. To build H from A \Gamma1
J , we first apply I+S 1 and I+S \Gamma1 , which
has the effect of adding together neighboring diagonals. Indeed, if A \Gamma1
P a n S n ,
we have
a
(a
, the elements of the product (I
are bounded
by 4K ae n . H is then found by multiplication with
a) 2 and the addition of a
diagonal term. The decay away from the diagonal of the terms fl n is
The exponential decay in fl n dominates the growth of n 2 and thus we find the
constant C:
ae
(log ae) 2
CRemark: The fact that Hv - ffv for smooth functions v can be also seen from
the Fourier analysis of H. By doing a discrete Fourier transform of H, we obtain a
diagonal matrix diag(-g). The diagonal -
g is given by the symbol of H which is
Note that -
g is just the Fourier transform of any row of H. It is therefore no surprise
that -
It turns out that d-g
d!
The approximation error is indeed quadratic in ! since -
If the Fourier coefficients of v decay sufficiently fast, then we have - g-v - ff-v, and by
the inverse transform, Hv - ffv. Note in Figure 1 that - g(!) has a moderate growth
even for large !.
Figure

1: The Fourier components of H and ffI (dashed line). - g(!) behaves like
multiplication with -
boundary conditions are assumed.
In practice, we want to approximate the homogenized operator L J by a sparse
approximation. Due to the diagonal decay, we can approximate L J by a band-
diagonal matrix L J;- where - is the band-width. Let us consider the operator band
defined by
ae
We have in fact two obvious strategies available for producing L J;- : We can set
directly or use the homogenized coefficient form and build
produce small perturbations of
L J . However, important properties, such as divergence form, are lost in the first
approach and numerical experiments show that - needs to be rather large to compensate
for this. The second approach produces L J;- in divergence form. Moreover,
the approximation error can be estimated, as in the following result:
Theorem 2 If the conditions of Theorem 1 are valid, then
If v is the discretization of a smooth function v(x), then
Proof: The exponential decay from the diagonal in H, given in (13), yields
If v is a smooth function, using the commutation property of H (and band(H)), we
have
where - is some point in R. Therefore we have
Taking the supremum over all - and then the maximum over all j yields the desired
estimate. 2
Remark: The above estimates hold also for Dirichlet boundary conditions. In the
case of periodic boundary conditions, the meaning of "away from the diagonal" is
different because the wrap-around effect. The diagonal band of width - is then
defined by 2(ji \Gamma jj ( mod is the size of the matrix.
3.5 Numerical experiments
We test the homogenization procedures on some examples.
ffl With periodic coefficients, wavelet and classical homogenization produce the
same discrete solution. With non-periodic variations of the coefficients, the
effective equations cannot extract the local features of the solution. Due to
the localization of the wavelet basis elements, such local features are preserved
by wavelet homogenization.
ffl Solution with several different scales. The test problem is (a(x; x="
1. We project the solution on spaces that resolve either both the scales "
or just the finest scale " 1 .
ffl Comparison of the solutions of the homogenized forms using the two truncation
strategies, band(L J ; -) and 1
different values for - We
see that truncation of the homogenized coefficient matrix H performs much
better.
3.5.1 Non-periodic variable coefficients
First we compare the exact, classical-homogenized, and wavelet-homogenized solutions
to a periodic problem. We consider the two-point boundary problem
The exact solution solves the discrete equation
We take a(x)
to have alternating values 1 and 100 on a fixed grid. The classical and wavelet
homogenized solutions are pictured in Figure 2.
Exact solution
Wavelet homog.
Classical homog.
solution
Wavelet homog.
Classical homog.

Figure

2:
Exact, classical homogenization and Haar basis homogenization solutions in the
periodic case. grid-points. The plot on the right is a detail of the left
image.
The wavelet solution is computed using 3 levels, i.e. the coarse scale contains eight
times fewer grid-points. The effective coefficient is 200=101 - 1:9802 and thus
classical homogenization yields the approximation
x:
Note the detail in Figure 2 where the wavelet based solution u is essentially a shift
of u eff , i.e. u contains no high frequencies.
Now we take a(x) to be uniformly distributed in the interval [1 100], as plotted
in

Figure

3 (left). The classical homogenized coefficient (effective coefficient) is
computed as
a
dx
solution
Wavelet homog.
Classical homog.
Figure

3:
coefficients a(x) (left) and a comparison of the exact solution u, effective
equations solution u eff and Haar basis homogenization solutions u.
grid-points in these plots.

Figure

3 (right) compares the exact solution u with the wavelet homogenized u and
the result of classic homogenization u eff , where the effective coefficient is a
18:8404. The fine grid has 256 points. Both u eff and u are represented on the
coarse grid using 32 points. However, the wavelet homogenized solution u captures
much more coarse-scale detail then the classic solution u eff .
3.5.2 Homogenization over multiple scales
We test a problem that contains three different scales: Let
The coefficient has three scales, The solution of the equationh 2
contains all the three scales if h resolves the finest scale of a(x). Put
resolve all the scales of the problem. Then we project the exact solution onto V 6 .
Exact sol. on V9
Projection on V3
Projection on V6
-0.06
-0.02Exact sol. on V9
Projection on V3
Projection on V6
-0.06

Figure

4:
Homogenization of several scales. Coefficient a Plot of u 9 , u 6 and
(left). Details of plots (right) shows that u 6 averages the finest scale only and
resolves the coarser scales. u 3 resolves only the coarsest scale.

Figure

4 shows that the finest scale contribution is averaged out, but the coarser
scales are resolved. Projection onto V 3 averages both the finer scales
and the solution has the characteristics of a constant-coefficients
problem.
3.5.3 Banding strategies
We test the accuracy of approximating the homogenized operator by banded matrices
using the two strategies described in Section 3.4. The coefficients a(x) are chosen
at random, uniformly distributed in the interval (0:1 2). The boundary conditions
are
Exact homog.
diagonals
diagonals
diagonals
-0.4
-0.3
-0.2
-0.1Exact homog.
3 diagonals
5 diagonals
7 diagonals
-0.4
-0.3
-0.2
Figure

5:
The homogenized operator approximated by banded matrices. Banding the exact
homogenized operator L J (left) needs a much larger band-width - as compared to
banding the homogenized coefficient matrix H (right). 512 grid-points on the fine
grid, 64 grid-points on the coarse grid.

Figure

5 (left) is the plot the solutions of band(L J ; -)u To
obtain even better accuracy, using the approximation of the homogenized coefficient
considerably fewer diagonals are needed. Figure 5 (right)
plots the solutions of 1
diagonals.
4 2-D Problems
Numerical homogenization for multi-dimensional problems is of great interest since
the analytic methods can only handle periodic micro-structures, see e.g., Bensoussan
et al. [1]. The aim of this section is to show that if a 2-D fine-scale operator is
in discrete divergence form
then the homogenized operator L J acting on the coarser space has the same form. As
we saw in the one-dimensional case, this property is important for efficient truncation
strategies.
2 The operator L J+1 is called discrete elliptic if
1. L J+1 is symmetric, i.e., A
2. The spectrum of L J+1 lies in f0g [ [ffi; +1), where ffi ? 0, and 0 cannot be a
multiple eigenvalue.
4.1 2-D tensor product wavelet spaces
Let us make the notations precise. We consider the tensor product space V
generated by the canonical basis
The coarse space is V
J\Omega V J and it is generated by '
J;k\Omega ' J;l . The orthogonal
complement of V J in V J+1 is the wavelet space
The wavelet transform maps the standard basis of V J+1 into the union of the standard
bases of V J and the three components of W J . If L J+1 is the matrix of a linear
operator on V J+1 , then the orthogonal basis transformation W J yields
The operators A J , B J , C J and L J operate on subspaces:
By elimination, we have that the homogenized operator is
Note that in the finite case, dim(W J
We can continue with the decomposition of V obtain in this
manner a multi-resolution analysis on the product space.
The product of the orthogonal transformations is the
(orthogonal) wavelet transform that maps V J+1 into (\Phi 0-j-J W j
4.2 Invariance of divergence form
The operator
acts on V J+1 and is defined by \Delta x
f)\Omega g, where
is the 1-D forward difference operator. \Delta y
are defined in a similar
manner. We regard the operators A (ij) as multiplication by the discrete functions
a (i;j) (x; y), i.e., A (i;j) ('
l (y). In general, A (i;j) can
be any operator on V J+1 , but then L J+1 is may no longer be a discretization of a
differential operator.
Let us formulate the result:
Theorem 3 Let L J+1 be a discrete elliptic operator in divergence form (14). Assume
periodic boundary conditions in the x and y directions and let L J be the homogenized
operator using the Haar transform. Then L J is also in divergence form.
Proof: We begin by observing that the orthogonal transform W
V J can be written as W is a the corresponding 1-D transform
in the x-direction, and W y is defined analogously. Remark also that W x W
W y W x .
Next we observe that \Delta x
+\Omega I and \Delta y
This gives that \Delta x
and \Delta y
.
The next step is to compute the decomposition of \Delta x
in (W
Using the standard inner-product on tensor-product spaces,
we apply \Delta x
to a basis function and test it against another basis function:
can be any ' J;k or / J;k . Note that the second inner-product is 0 if g 1 6= g 2 .
The first inner-product gives the 1-D decomposition of \Delta + , as in Proposition 3.
Using the notations of Proposition 3, we can synthesis the decomposition of
in
the following table:
W \Theta W W \Theta V V \Theta W V \Theta V
W \Theta W
M\Omega I \Gamma\Delta
+\Omega I
M\Omega I \Gamma\Delta
+\Omega I
V \Theta W \Delta
I \Delta
+\Omega I
I \Delta
+\Omega I
In a similar fashion, we obtain the decomposition of \Delta y
I\Omega M
I\Omega M
I\Omega
and
\GammaM
I \Delta
\Gamma\Omega I
\GammaM
I \Delta
\Gamma\Omega I
\Gamma\Omega I \Delta
\Gamma\Omega I
\Gamma\Omega I \Delta
The essential point is that the last block-row of the decomposition of \Delta x
(or \Delta y
contains only \Delta
+\Omega I (or
entries. For the \Delta x
(or \Delta y
the analogous
holds for the last block-column.
Noting that \Delta
, on the coarse space V J , we have that the decomposition
of the product 1
\Gamma is of the form4h 26 6 6 4
A
are some arbitrary operators. Adding the contributions of
all the terms in the form (14) of L J+1 yields:4h 26 6 6 4
A
where D is in discrete divergence form.
Since L J+1 is elliptic, periodic boundary conditions imply it has a one-dimensional
null-space, spanned by the constant functions. This null-space is mapped by the
transform W J into V J . Since the operator L J+1 has non-negative eigenvalues and
A operates on the complement of V J , it follows that v ? Av ? 0 for any v 6= 0.
Therefore A is invertible and we can build the homogenized operator by block Gauss
elimination. This yields
where \Delta (1)
stands for \Delta x
We have that L J is in divergence form on the coarse
space V J . 2
Remark: The conservation of the divergence form of L J+1 under the 2-D Haar
transformation has important consequences. In the multi-dimensional case, it is
known that the problem
r
admits a homogenized equation but apart from the cell-periodic problem,
there is no general algorithm for deriving the homogenized operator L. In fact, the
nature of L is not known and numerical homogenization can therefore be used not
only as a practical tool, but also to find information about the structure homogenized
operator L.
4.3 A numerical example
We chose a(x; 1. The classical
homogenized equation is
is the harmonical average of a in a cell with the length of a period and
2 is the (arithmetical) average in the same cell:
The homogenized equation has constant coefficients but is strongly anisotropic. Figure
6 displays the exact and wavelet homogenized solutions. The domain is the unit
square and there are Dirichlet boundary conditions on the coordinate axes and Neumann
conditions on the other two sides.
-5
-5
y

Figure

Fine scale (left) and homogenized solution (right). Note that the homogenized
solution captures the effect of the coarse-scale strong anisotropy, averaging only the
fine-scale variations.
Extensions
The homogenization procedure can be carried out on coarser and coarser levels to
produce a sequence of homogenized equations
If we solve the coarse scale problem exactly, then by block back-substitution
we produce the exact solution:
If no truncations are used in building the homogenized operators L j , the above strategy
describes an exact, direct solver, which compares to the reduction techniques
in computational linear algebra, see [8]. If truncations are used, the direct solver
contains an approximation error.
The homogenization procedure can be applied recursively on any number of lev-
els, provided that the initial operator is in discrete divergence form and is elliptic.
These two properties are sufficient for the existence of the Schur complement and
they are are inherited by the homogenized operator. It is not necessary that L J+1
approximates a differential operator as long as it is elliptic and in divergence form.
On coarser scales, the homogenized operator resembles the inverse of a differential
operator and is expected to be dense. The use of wavelets with a high number of
vanishing moments, known to compress well Calderon-Zygmund operators, could
have better compression effects then the Haar system, in the spirit of the ideas
presented in Beylkin, Coifman and Rokhlin's work [2].
In applications, if we want to use the homogenized coefficient matrices, we would
not invert A j , but rather LU-factorize it in the prescribed bandwidth -.



--R

Asymptotic Analysis for Periodic Structures.
Fast wavelet transform and numerical algorithms.
A multiresolution strategy for numerical homoge- nization
Ten Lectures on Wavelets.
Wavelets and Singular Integrals on Curves and Surfaces.

Numerical calculation of equivalent grid block permeability tensors for heterogenuous porous media.
Matrix Computations.
Ondelettes et Op'erateurs
--TR

--CTR
Shafigh Mehraeen , Jiun-Shyan Chen, Wavelet-based multi-scale projection method in homogenization of heterogeneous media, Finite Elements in Analysis and Design, v.40 n.12, p.1665-1679, July 2004
Giovanni Samaey , Ioannis G. Kevrekidis , Dirk Roose, Patch dynamics with buffers for homogenization problems, Journal of Computational Physics, v.213 n.1, p.264-287, 20 March 2006
Assyr Abdulle , E. Weinan, Finite difference heterogeneous multi-scale method for homogenization problems, Journal of Computational Physics, v.191 n.1, p.18-39, 10 October
Pingbing Ming , Xingye Yue, Numerical methods for multiscale elliptic problems, Journal of Computational Physics, v.214 n.1, p.421-445, 1 May 2006
Jiun-Shyan Chen , Hailong Teng , Aiichiro Nakano, Wavelet-based multi-scale coarse graining approach for DNA molecules, Finite Elements in Analysis and Design, v.43 n.5, p.346-360, March, 2007
wavelets;elliptic operators;homogenization