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