Contoh Skripsi,Tesis, Jurnal, Bahan Kuliah, Artikel, dll

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

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