The 12th International Conference of

International Association for Computer Methods and Advances in Geomechanics (IACMAG)

1-6 October, 2008

Goa, India

2’D Non-Orthogonal Spline Wavelets and Schneider’s Leveldependent

Scheme for 3’D Boundary Elements Method

M.Hooshmand

Candidate of PhD, Civil and Structural Department, University Of Tehran-Iran

K.Bargi

Professor, Civil and Structural Department, University of Tehran-Iran

Key Words: matrix compression scheme, wavelet BEM, 2’D Non-orthogonal wavelet

ABSTRACT: 2’D Non-orthogonal spline wavelets are used as basis function in boundary elements

method(BEM).This kind of wavelet has compact supports and closed-formed expression that have been

proposed by authors. Besides one can choose the vanishing moments of the wavelets Independently of the order

of B-splines. The adaptive meshing for boundary elements makes it possible to reduce the degree of freedom

(DOF) required for a specified accuracy. Sparse coefficient matrices are obtained by truncating the small

elements a priori. The level-dependent schemes enable us to reduce the matrix entries. In the present paper we

investigate the matrix truncation using Schneider’s level-dependent algorithm. The level-dependent truncation

schemes select the truncated entries by comparing the predetermined threshold with the distance between the

supports of two basis function. Through numerical examples, the efficiency of compression scheme together with

Non-orthogonal surface wavelet is investigated.

1 Introduction

The main advantage of application of Boundary Element Method (BEM) is reduction of computational work.

Using BEM , we can decrease the computational space by one dimension,So the amount of computations will be

decreased greatly. Aplication of wavelet basis function is very suitable for truncation of the matrix

coeficients.Using wavelets as basis function enables us to utilize two important properties of wavelets. These are

the local support and vanishing moment.

The vanishing moments imply the orthogonality of the wavelet basis to all polynomials of certain degree or less.

The wavelet basis is originally developed for image processing, and hence the orthonormal wavelets have an

advantage which it can easily perform decomposition and reconstruction of signals or images. The orthogonality

of wavelets plays an important role in image processing and signal analysis ,whereas it is not always essential

property in boundary element analysis. In application of wavelets to BEM , the local support and vanishing

moments of wavelets are essential for reduction of computational cost. By this property the leading order of

integrals including wavelets shifts from the 0th -order term to the nth -order one where n is the order of

wanishing moments. As a result, the integrals have small values if their kernel functions are smooth. Since many

coefficients of boundary element equation are given by such integrals, we can obtain a sparse coefficient matrix

by truncation of these small entries.

The enhancement of wavelet BEM can be accomplished by evolving the wavelet basis. The orthonormal

wavelets have been constructed by Haar(1910),Stromberg(1982),Meyer(1986),Lemarie(1988),Battle(1987)

,Daubechies(1988) on real line,and Von Petersdorff et al.(1997) on a surface. In wavelet BEM , the orthonormal

wavelets are mainly employed as basis functions for descretization of a Boundary Integral Equation (BIE), in

early stage of the research.

Streinberg and Leviatan (1993) and Sabetfakhri and Kateki(1994) have attempted to use the Battle-Lemarie

wavelets in Galerkin BEM for 2Dscattering problems.Wang(1995,1997) has proposed boundary element analysis

using Daubechies orthogonal wavelets. Steinberg et al. and Sabetfakhri et al. have attempted to employ the

Battle-lemarie wavelet. Wang(1995,1997) has proposed the boundary element analysis using the Daubechies

wavelet. These wavelets are classified in orthonormal wavelets. Although the orthonormal wavelets were

employed in many works , they are disadvantages in application to BEM.

The orthonormal wavelets have infinite supports and they are not closed-form except Haar wavelet that is a

compactly supported wavelet with a closed-form.Goswami et al. have employed a semi-orthogonal wavelet, in

1

which bases in the same subspace do not have orthogonality.Kazuhisa Abe et al.(2003-2005) have proposed a

compact supported wavelet with arbitary vanishing moments. They developed a non-ortogonal wavelet that is

suitable for boundary element analysis.

In the present paper we express the non-orthogonal B-spline surface wavelet that was proposed by authors and

investigate the matrix compression scheme. The matrix compression for the proposed wavelet BEM enables us

to generate a sparse matrix. The matrix truncation scheme is applied using the Schneider level-dependent

method together with Non-orthogonal surface wavelet that was proposed by authors.

2 Non-orthogonal surface spline wavelet

The surface wavelet is defined on the plane (ξ ,η ) . The projection of the function f (ξ ,η) sholud be calculated on

the wavelet space (ξ ,η ) . The complete wavelet space is defined using surface scaling and wavelet function. The

surface scaling function is defined by the production of two 1'D scaling function in directions ξ ,η . Also the

wavelet function is defined by the production of two 1'D wavelet function in directions (ξ ,η ) or a 1'D scaling

function and a 1'D wavelet function in directions ξ ,η . The projection of functtion f (ξ ,η ) on wavelet space is as

below :

( , ) ( , ) ( , ) ( , ) ( , ) 00 0 ' 0 , ' f ξ η P f ξ η P f ξ η P f ξ η Q f ξ η k k k k = + + + (1)

ΣΣ

= =

=

ns

j

n s

j

j j j j P f c

1

'

' 1

00 0 , ' 00, , ' (ξ ,η ) , φ (ξ ,η ) (2)

ΣΣ Σ

= =

∞

=

=

ns

j

nk

l

k j l j k l

k

k P f d

1

'

1

0 ' , 0 '

' 0

0 ' (ξ ,η ) , φ ψ (ξ ,η ) (3)

ΣΣ Σ

= =

∞

=

=

n s

j

nk

r

k j r j kr

k

k P f d

'

' 1

'

1

0 ', 0 '

0

0 (ξ ,η ) , φ ψ (ξ ,η ) (4)

ΣΣ Σ ∞

= =

∞

=

=

0

, '

, 0

', , , '

' 0

' ( , ) ( , )

k

nk nk

l r

kk r l k r k l

k

kk Q f ξ η d ψ ψ ξ η (5)

2.1 Surface scaling function

The surface scaling function is defined as below :

φ m,m' (ξ ,η ) =φ m (ξ )φ m' (η ) (6)

For the translated scaling function we have :

( , ) ( ) ( ) ', , ' , ', ' φ ξ η φ ξ φ η kk j j k j k j = (7)

Where m,m' are the order of piecewise polynomials. In this paper the value of mand m' is consider the same.

The surface scaling and wavelet functions behave as like as a telescope. The values of m,m' control the its

magnification and j, j' control its location.

φ 0,0 (ξ ,η )

Figure 1. Example of the surface scaling function.

(the number in the square is the value of function)

2

2.2 Surface Wavelet

Two kinds of wavelets are produced . The first type of them are produced by production of the scaling functions in

one direction and the wavelets in another direction,that are defined as below :

( , ) ( ) ( ) , ', , ', φ ψ ξ η φ ξ ψ η k j k l k j k l = (8)

( , ) ( ) ( ) ', , ', , φ ψ ξ η φ η ψ ξ k j k r k j k r = (9)

Another kind of surface wavelet is prduced due to production of the 1'D wavelet in each direction.

( , ) ( ) ( ) ', , , ', ψ ξ η ψ ξ ψ η kk r l k r k l = (10)

0

1

0

1φ ψ (ξ ,η ) 0

1

0

1ψ φ (ξ ,η ) 0

1

0

1ψ ψ (ξ ,η )

Figure 2. Example of Piecewise constant nonorthogonal

surface wavelets. (m = 0)

(the number in the square is the value of function)

3 Boundary element formulations for 3’D laplace problems

The boundary integral equation for 3-D Laplace problems is obtained by the direct approach as below :

∫ ∫ Γ Γ

( ) ( ) + *( , ) ( ) Γ = *( , ) ( ) Γ , y y c x u x q x y u y d u x y q y d (x, y ∈ Γ), (11)

Where u and q are the potential and the flux, respectively. u * And q * are the fundamental solutions

corresponding to u and q and c is the free term, and Γ is boundary.

To derive a boundary element equation from equation (11), we first define the following wavelet series u' and q'

as approximation of u and q :

Σ ΣΣ Σ ΣΣ Σ

= = = = = = =

= + +

nb ns

j

mr

k

nb nk

r

k j r k r j

nb ns

j j

nb ns

j

mr

k

nb nk

s

j j j j k j s j k s u u u u

.

'1 0

.

1

0, ', , 0, '

.

, ' 1

.

1 ' 0

. '

1

00, , ' 00, , ' 0 ', , 0, ', '(ξ ,η ) φ (ξ ,η ) φ ψ (ξ ,η ) ψ φ (ξ ,η ) +

Σ Σ

= =

mr

k k

nk nk

r s

kk r s kk r s u

, ' 0

, '

, 1

', , ', , ψ (ξ ,η ) (12)

Σ ΣΣ Σ ΣΣ Σ

= = = = = = =

= + +

nb ns

j

mr

k

nb nk

r

k j r k r j

nb ns

j j

nb ns

j

mr

k

nb nk

s

j j j j k j s j k s q q q q

.

'1 0

.

1

0, ', , 0, '

.

, ' 1

.

1 ' 0

. '

1

00, , ' 00, , ' 0 ', , 0, ', '(ξ ,η ) φ (ξ ,η ) φ ψ (ξ ,η ) ψ φ (ξ ,η ) +

Σ Σ

= =

mr

k k

nk nk

r s

kk r s kk r s q

, ' 0

, '

, 1

', , ', , ψ (ξ ,η ) (13)

Where j j j j k j s k j s k j r k j r kk r s kk r s u q u q u q u q 00, , ' 00, , ' 0 ', , 0 ', , 0, ', 0, ', ', , ', , , , , , , , , are the expansion coefficients concerning

u and q . In the present scheme, the boundary equation solution can be yielded by solving the boundary element

equation with respect to their unknown components. In equations (12,13), nb is the number of finite intervals on

boundaries. ns and nk are the number of basis φ and ψ . Substituting equations (12,13) into equation (11),

the residual r ≠ 0 is obtained as below :

∫ ∫ Γ Γ

= + Γ − Γy y r(x) c(x)u'(x) q *(x, y)u'( y)d u *(x, y)q'( y)d (14)

3

Using the Galerkin conditions we obtain the following equation :

∫Γ

r.w dΓ = 0, (i =1,2,...,N), i (15)

Where w (i 1,2,....,N) i = are the basis functions that include the scaling and wavelet functions and N is the

Degree Of Freedom (DOF) which is the number of points that the functions u and q are calculated at them.

Consequently the boundary element equation is obtained as below :

Az = b, (16)

Where b is the known vector and z is the unknown vector. Matrix A is the coefficient matrix which entries are

defined by i j g , and i j h , as follows :

g w u *w d 2 w (ξ ,η ) u *(ξ ,η ,r, s)w (r, s)J (r, s)drdsJ (ξ ,η )dξdη , j i

i j

ij ∫i i∫j j ∫∫ i ∫∫ j

Γ Γ

Γ Γ

= Γ = (17)

= − ∫ Γ +∫ ∫ Γ = Γ Γ Γ

h 1/ 2 w w d w q *w d 2

ij i i j i i j j

1/ 2 w (ξ ,η )w (ξ ,η )J (ξ ,η )dξdη w (ξ ,η ) q * (ξ ,η , r, s)w (r, s)J (r, s)drdsJ (ξ ,η )dξdη , j i

i j

i j

i

∫∫ i j j ∫∫ ∫∫

Γ Γ Γ

− +

(18)

Where (i, j =1,2,...,N) and i J is the jackobian matrix in (ξ ,η ) plane and Jj is the jackobian matrix in

(r,s) plane. i Γ , j Γ are the surface elements on the boundary that are the supports of basis functions.

4 Matrix compression algorithm

In wavelet boundary equation analysis, most of coefficients and have small values because of the vanishing

moment property of the wavelets. This allows us to generate a sparse coefficient matrix by truncation of its small

entries. The matrix in wavelet boundary element method is usually constructed by application of Galerkin method

to the boundary integral equation. This discretization method is adopted in view of computational cost: Galerkin

discretization leads to a higher compression rate of the matrix and more rapid convergence of iterative process

than those of collocation scheme. To avoid such an increase in computational effort that is fatal to enhancement

of the performance, we assemble the sparse matrix by omitting computation of its small entries.To select these

small entries without calculation of the integrals, the Schneiders level-dependent.

4.1 Schneider‘s level-dependent Truncation scheme

Schneider’s truncation scheme has the distance based truncation criterion.The truncated entries, which are

choosen before calculation of Equations (17,18) are associated with the basis functions satisfying the geometrical

condition r >δ where is the distance between the supports of the two basis functions. Alsoδ is the threshold for

truncation which is dependent on the degree of basis function polynomial,vanishing moment.

.max{ 2 , (2 1) ) 2( 2 1 ( )}

2

δ = a − min( ki + kr ,kj + ks ) m + ( n1+ r m+ − ki + kj + kr + ks (19)

For p +1= n + r , and

.max{2 ,(2 2 }

(2 1)(2 ' ') ( )

min( , ) n r

m p r ki kj ks kr

a ki kr kj ks +

+ − − + + +

δ = − + + (20)

For p +1 < n + r ,
where p is the degree of polynomials which form the wavelet, r = −1 for matrix G and r = 0 for matrix H .
The matrices G,H ∈ RN×N have the entreis i j g , , i j h , that are defined in equations (17,18). The parameter p'
satisfies p +1< p'< n + r and a >1.

4

5 Numerical results

The numerical tests were undertaken to investigate the the capability of this method for using in Solution of 3'd

problems.The present method was applied to 3’d Laplace problems with boundary conditions and exact solution

as shown in Figure 3. In this example, the boundary was divided into six finite intervals, and the piecewise

constant and the piecewise linear non-orthogonal surface wavelets were employed for the bases.The order of

vanishing moments of them was set to n =1 or 3 in each direction for piecewise contant wavelets, and n =2 in

each direction for piecewise linear wavelets.

Figures 4,5 show the show the storage requirement of the compressed coeficient matrix A , equivalent to matrix

H .

The piecewise constant and linear wavelets mentioned above, were used for shape functions. In general,

wavelet BEMs show highly compression at a part of the coeficient matrix associated with fine-scale bases.

It is obviously understand from Figure 4 and Figure 5 that the number of stored entries is very small relative to all

of entreis. So we can cancel the great amount of calculations without any decreasing in accuracy.The

performance of this method depends on the degree of basis function polynomial and the value of magnification

numberm Increasing the value of m and the order of polynomial increase the performance of the truncation

scheme.

Figure 3. Test example for 3'D domain

(Neumann problem for an external domain. B.C.: q = 0 , U = y ∞ )

Figure 4. Memory requirements for the matrix entries.

5

Figure 5. Memory requirements for the matrix entries.

6 Acknowledgements

We have presented the compactly supported non-orthogonal B-spline surface wavelets with arbitrary order of

vanishing moments. Efficiency of the proposed wavelets in boundary element analysis has been discussed.

Unlike orthonormal or semi-orthogonal wavelets, any orthogonality is not required to these wavelets explicitly.

However, this property does not lead to any disadvantages in BE analysis. Through numerical results, it is found

that we can save both memory requirements by using the wavelets with higher order vanishing moments.

By increasing the order of vanishing moments, the number of knots of the spline wavelets is increased, and then

the computational cost for construction of the coefficient matrix becomes expensive. Hence, it seems to be a

drawback in the application of the wavelets with higher-order vanishing moments.

7 References

Battle, G.: A block spin construction of ondelettes, Part I: Lemari´e functions. Comm.Math. Phys., Vol.110, pp.601-615, 1987.

Beylkin G., Coifman R. & Rokhlin V.1991. Fast wavelet transforms and numerical algorithms I. Comm. Pure Appl. Math.,

Vol.44, 141-183.

Cohen A., Daubechies I. & Feauveau J.C. 1992. Biorthogonal bases of compactly supported wavelets. Comm. Pure Appl.

Math., vol.45, 485-560.

Daubechies I. 1988. Orthonormal basis of compactly supported wavelets. Comm. Pure Appl.Math., Vol.41, 909-996.

Haar A.1910. Zur theorie der orthogonal funktionensysteme. Math. Ann., Vol.69, 331-371.

Koro K. & Abe K. 2003. A wavelet method for reducing the computational cost of BE-based homogenization analysis. . Eng.

Anal. Bound. Elems., Vol.27, 439-454.

Koro K. & Abe K. 2003. A practical determination strategy of optimal threshold parameter for matrix ompression in wavelet

BEM. Int. J. Numer. Meth. Eng., Vol.57,169-191.

Lemaire´e P.G. 1988. Ondelettes `à localisation exponentielle. J. Math. Pure et Appl., Vol.67, 227-236.

Meyer Y. 1985. Principe d’incertitude, bases hilbertiennes et alg`ebres d’op´erateurs. S´séminaire Bourbaki, No.662.

Steinberg B.Z. & Leviatan Y. 1993. On the use of wavelet expansions in the method of moments. IEEE Trans. Antennas

Propagat., vol.41, No.5, 610-619.

Sabetfakhri K. & Katehi L.P.B. 1994. Analysis of integrated millimeter-wave and submillimeter-wave waveguides using

orthonormal wavelet expansions. IEEE Trans. Microwave Theory Tech., Vol.42, No.12, 2412-2422.

Stromberg J.O. 1982. A modified Franklin system and higher order spline systems on Rn as unconditional bases for Hardy

spaces. in: Conference in Honor of A. Zygmund, Vol.II, Beckmer, W. et al. eds., 475-493, Wadsworth Math. Séries,

Belmont, California.

Von Petersdor T., Schwab C. & Schneider R. 1997. Multiwavelets for second-kind integral equations. SIAM J. Numer. Anal.,

Vol.34, No.6, 2212-2227.

6

Wang G. 1995. A hybrid wavelet expansion and boundary element analysis of electromagnetic scattering from conducting

objects. IEEE Trans. Antennas Propagate., Vol.43, No.2,170-178.

Wang G.1997. Application of wavelets on the interval to numerical analysis of integral equations in electromagnetic scattering

problems. Int. J. Numer. Meth. Eng., Vol.40, 1-13.

7

Home »
article »
2’D Non-Orthogonal Spline Wavelets and Schneider’s Leveldependent Scheme for 3’D Boundary Elements Method

# 2’D Non-Orthogonal Spline Wavelets and Schneider’s Leveldependent Scheme for 3’D Boundary Elements Method

Subscribe to:
Post Comments (Atom)

## 0 comments:

## Post a Comment