
A. P. REDDY ET AL.1379
01
101
101
01123
10123
101
2
22 nn
hh
hhh
hhh
gg gg g
ggggg
ggg
W
Matrix W contains first 2n rows which are lowpass
filter coefficients and remaining 2nrows are highpass
filter coefficients. W can be derived for various
by symmetric extension of filters [6] and is any
natural number [3]. Here first half of is a represen-
tation of s at a lower resolution level. This represen tation
has to preserve average, first moment and so on of the
original signal s. Preservation of these moments depends
on the accuracy of the scaling function used [6,7].
and pp
n
Ws
To create wavelets on higher dimensional domains,
one of the approaches is to perform the wavelet trans-
form independently for each dimension. For two dimen-
sional cases, let
be a nn matrix then its wavelet
transform is
T
WAW
Here
contains four types of coefficients/subbands:
LL-lowpass in both the horizontal and vertical directions
(approximation/average coefficients), LH-lowpass in the
vertical, highpass in the horizontal direction, HL and HH
(detail coefficients). When iterated on the approximation
coefficients, the result is multiresolution decomposition
as shown in the Figure 1.
This LL subband contains lowpass information, which
is essentially a low resolution and represents a coarser
ver sion o f the o rigin al matr ix A very much. This concept
has been used in obtaining the hierarchy of matrices in
the algebraic multigrid (AMG) context.
3. Wavelet-Based AMG
Wavelet Transform will be used to generate the hierar-
chy of matrices in the AMG method. As a result, the
coarsening process is eliminated and the setup phase is
summarised by a simple choice of the lowpass filters and
assembly of the intergrid (restriction and interpolation)
operators. In the algebraic multigrid context it is not ne-
cessary to rebuild the matrix. Thus, the detail coefficients
produced by wavelet transform can be discarded [3,4]. In
other words, the transformation must produce only one
approximation of the original matrix in each decomposi-
tion level. Th erefore, on ly the lowp ass filters that cap ture
Figure 1. Two-dimensional wavelet transform: iteration on
the LL subbands (average coefficients).
the approximation are used in the construction of the
matrix W and it is used as a restriction operator for the
wavelet based AMG. Using CDF lowpass filters,
the restriction operator takes the following form:
2,2
01
101
101
/2
2
nn
hh
hhh
R
hhh
The prolongation operator and the next
matrix of hierarchy, in the corresponding level, are de-
fined by , where is transpose of .
T
PR
T
RAR T
R R
4. Cost of Orthogonal and Biorthogonal
Wavelet Transforms
Let
be a vector of length n and let an accuracy of
orthogonal (Daubechies) and biorthogoanal(CDF) scal-
ing functions used. One of the lowpass filter lengths of
CDF wavelets is
p
1p
, whereas for Daubechies it is
. Lowpass filtered version of wavelet transform ap-
plied to s is of length
2p
2n. Number of operations (mul-
tiplication and addition) to obtain this for Daubechies
filters is , where as for CDF filters it is of
pn
(1p)2n
. For large , we can save the number of
operations and setup time (performing WT) by using
biorthogonal scaling filters compared with that of or-
thogonal scaling filters. Similar arguments hold for cost
of individual wavelet transform in higher dimensions.
n
Grid complexity and operator complexity are two sim-
ple criteria used to provide a posterior cost estimates as
defined in [3] for AMG V-cycle. Here grid complexity is
same for both families of wavelets. The advantage of
reduction of the cost and setup time for biorthogonal
wavelet transform results into the reduction of operator
complexity compared with that of orthogonal wavelet
transform for fixed accuracy of scaling functions. Ope-
rator complexity indicates the total storage space re-
quired by the hierarchy of matrices over all levels and is
generally considered as a good indicator of the expense
of the AMG V-cycle.
We have calculated operator complexity and setup
time for both fa milies of wavelets for various un symmet-
ric matrices given in Table 1, from Tim Davis [8] col-
lection of sparse matrices. The number of levels chosen
Copyright © 2011 SciRes. AM