Yer Ming-Qua

Chen

Chyi Hwang

Yen-Ping Shih

THE COMPUTATION OF WAVELET-GALERKIN APPROXIMATION ON A BOUNDED INTERVAL

Keywords: wavelet orthogonal bases, wavelet-Galerkin method, Burgers' equation, numerical method, approximation

This paper describes exact evaluations of various finite integrals whose integrands involve products of Daubechies' compactly supported wavelets and their derivatives and/or integrals. These finite integrals play an essential role in the wavelet-Galerkin approximation of differential or integral equations on a bounded interval.

I. INTRODUCTION

In a recent paper, Daubechies 1 constructed a family of orthonormal bases of compactly supported wavelets for the space of square-integrable functions, L 2 (R). Due to the fact that they possess several useful properties, such as orthogonality, compact support, exact representation of polynomials to a certain degree, and ability to represent functions at different levels of resolution, Daubechies' wavelets have gained great interest in the numerical solutions of ordinary and partial differential equations. 2 -11 In each of these papers the wavelet discretization of differential equations is based on the Galerkin approach. As a result, the wavelet-Galerkin scheme involves the evaluation of connection coefficients 12 • 13 to approximate derivatives as well as non-linear terms. The connection coefficients are integrals with integrands being products of wavelet bases and their derivatives. Due to the derivatives of compactly supported wavelets being highly oscillatory, it is difficult and unstable to compute the connection coefficients by the numerical evaluation of integral. In order to overcome this problem, dedicated algorithms have been devised 12 -16 for the exact evaluation of connection coefficients.

We note that the connection coefficients and the associated computation algorithms developed in References 12-16 are essentially based on an unbounded domain. It is therefore not surprising that the above-mentioned applications of the wavelet-Galerkin method are limited to the cases where the problem domain is unbounded or the boundary condition is periodic. In order to apply the wavelet-Galerkin method to the solution of finite-domain problems, the authors 17 • 18 have derived algorithms for computing some finite integrals of products of wavelets and their derivatives or integrals. As motivated by the successful construction of orthogonal interval wavelets, 19 • 20 we present in this paper algorithms for computing useful finite integrals of wavelets for the wavelet-Galerkin method on a bounded interval. More precisely, let Q>(x) denote the scaling function of Daubechies' wavelets, we consider the computation of the following functionals:

On(X) = 1x 1Y" • • •1Yl Q>(yl )dyl • • • dYn-1 dyn n-tuple
Mf:'(x) = 1x ym</J(y-k)dy fZ(x) = 1x ¢<n>(y-k)</J(y)dy A;•n(x) = 1x ym</J(n)(y-k)</J(y)dy r;•n(x) = 1x ymOn(Y-k)¢(y)dy n'~/(x) = r ¢(y)¢(m)(yj)¢(n)(y-k)dy

1 lo (1) (2)
(3) (4) (5) (6) (7) In the above equations, j,k E Z, m,n,x E z+ + {0}, and Z and z+ denote the sets of integers and positive integers, respectively.

Before attempting to present the computational algorithms for the above integrals, we first give in the following section a brief description of the construction of Daubechies' class of orthonormal wavelets and the basic properties of these wavelets.

DAUBECHIES' ORTHONORMAL WAVELETS

The family of compactly supported orthonormal wavelets constructed by Daubechies 1 includes members from highly localized to highly smooth. Each wavelet member is governed by a set of L (an even integer) coefficients { Pk: k = 0, 1, ... , L -1} through the two-scale relation and the equation

L-1 ¢(x) = L Pi ¢(2x-J) }=0 I . r/f(x) = E (-1) 1 PI-J ¢(2x-j) }=2-L (8) (9)
where ¢(x) and r/f(x) are called scaling function and mother wavelet, respectively. The fundamental support of the scaling function ¢(x) is in the interval [O,L-1] while that of the corresponding wavelet r/J(x) is in the interval [1 -L/2,L/2].

The coefficients Pk in the two-scale relation (8) are called the wavelet filter coefficients. Daubechies 1 established these wavelet filter coefficients to satisfy the following conditions:

I L-1 L-1 ~Pi =2 i=O ~ Pi Pi-m = £5o,m }=0 ~ ( -1 ) 1 PI-J PJ-2m = 0 for integer m }=2-L L-1 ~ (-1) 1 r Pi= 0, m = 0, I, ... ,L/2-I i=O (10) (II) (12) (13)
where £5 0 ,m is the Kronecker delta function. Correspondingly, the constructed scaling function </>(x) and wavelet 1/J(x) have the following properties:

/_: </>(x)dx = 1 (14) /_: </>(x-j)</>(x-m)dx = £5i.m (15) /_: </>(x) 1/J(x -m) dx = 0 for integer m ( 16) /_: xk 1/J(x)dx = 0, k = 0, 1, ... ,L/2-1 (17)
It is noted that the property ( 17) is equivalent to that the elements of the set {I ,x, ... ,xL/ 2 -1 } are linear combinations of </>(x-k), integer translates of </>(x). The exact expression for such linear combinations is given by Reference 12:

E 1"</>(x-l)=xn+£:(-I)i(~)Mfxn-i, n=O,I, ... ,L/2-1 (18)
1=-oo i=l 1

In the above equation, M/' denotes the jth moment of </>(x ), which can be computed by the recursive relation: 13

M! = /_: xk </>(x)dx } L-1 k = 2k+l-2 i~O /~1 ( k) .f t/> I p;l Mk-t ( 19
)
with the initial condition M! = I.

Denote by L 2 (R) the space of square-integrable functions on the real line. Let ~ and W1 be the subspaces generated, respectively, as the L 2 -closure of the linear spans of

¢ 1 ,k(x) = 2 112 ¢(2 1 x-k) and 1/Ji.k(x) = 2il 2 1jJ(2ix-k),k E Z.
•••CVicV 1 +1 (20) (2I)
and (22) where EB denotes the orthogonal direct sum. For the Daubechies wavelets, we have the following orthogonal properties:

/_: ¢J,k(x)¢J,t(x)dx = lJk,t /_: t/1 1 ,k(x)t/J,,m(x)dx = lJJ,l{Jk,m /_: ¢J,k(x)t/l},m(x)dx = 0 (23) (24) (25)
It is noted that there are no explicit expressions for calculating the values of the scaling function l/J(x) and the corresponding mother wavelet t/J(x) at an arbitrary point of x. However, the function values of l/J(x) and t/J(x) at the dyadic points kj2i for integers j and k can be recursively computed from the two-scale relations ( 8) and ( 9) provided that l/J(l),l/J(2), ... ,¢(L-2) have been obtained.

The algorithm for obtaining l/J(k) for k = 1, 2, ... , L -2 will be given in the next section.

COMPUTING THE DERIVATIVES AND INTEGRALS OF WAVELETS

In this section, we present computational algorithms for evaluating the derivatives and integrals of the scaling function ljJ(x ). Once the values of scaling function l/J(x) are obtained, the mother wavelet t/J(x) can be computed from the relation (9).

Evaluation of the nth derivative of l/J(x)

Denote by ¢<n>(x) the nth derivative of the scaling function l/J(x):

(26) It follows from (18) that the derivatives ¢<n>(x), n = 0, l, ... ,L/2-l, exist. Hence, applying the two-scale relation (8) to the above equation, we have

L-1 ¢<n>(x) = 2n L Pk4>(n)(2x-k)dx k=O (27)
This is the two-scale relation for ¢<n >(x ), which is analogous to the two-scale relation ( 8) for l/J(x). Obviously, this two-scale relation can be used to compute the values of ¢<n>(x) at all dyadic points x = k/21, j = 1,2, ... , provided that the values ¢<n>(k), k = 1,2, ... ,L-2, are given.

To obtain the values ¢<n>(x) at integer points, we substitute x = 1,2, ... ,L -2 into the two-scale relation (27) to give the homogeneous linear system of equations ( 28) where (29) (the superscript T denotes transpose) and P is the (L-2) x (L-2) matrix (30) with j being the row index and k the column index. Equation (28) indicates that the unknown vector <I> is the eigenvector of the matrix P corresponding to the eigenvalue 2-n. The values of ¢<">(1 ), ¢<">(2), ... , ¢<">(£-2) can be determined uniquely by first finding the eigenvector of the matrix P which corresponds to the eigenvalue 2-n, and then normalizing with the condition

L-2 L_(-kt<f><n>(k) = n! ( 31
)
k=l which is obtained by differentiating (18) n times and then letting

x = k.
Once the values of ¢<">(x) for x = 1,2, .. . ,L-2 are obtained, the relation (32) and the facts that ¢<">(x) = 0 for x ~0 and x?::-L-I allow one to determine the values of ¢<">(x) at x = k/2 1 for k = I, 3, 5, ... , 21 (L-l)-I and j = I, 2, ... Here, it should be pointed out that the above algorithm for generating ¢<">(k), k = 1,2, ... ,L-2, also holds for n = 0, which corresponds to the scaling function <f>(x) itself. For n = 0, ( 27) is exactly the same as the two-scale relation (8) for <f>(x). Moreover, the relation (18) with n = 0 is called the resolution of identity of the scaling function <f>(x ).

Evaluation of multiple integrals of <f>(x)

Denote by 0 11 (x) the n-tuple integrals of <f>(x ), i.e.

On(x) =fox 1Y•. The algorithm for computing 0 11 (x) at dyadic points k/21 has been derived by authors in a recent paper. [START_REF] Chen | A wavelet-Galerkin method for solving population balance equations[END_REF] For completeness, we repeat the derivation here.

Applying the two-scale relation ( 8) to (33 ), we have

On(x) = Ltl Pk r r ... r </>(2xl -k)dxl ... dxn k=O lo lo lo L-1 = T" "' L Pk On(2x -k) ( 34
)
k=O This is the two-scale relation for 0 11 (x), which is analogous to the two-scale relation (8) for <f>(x).

Hence, the values of 0 11 (x) at dyadic points kj2i can be computed recursively for j = I, 2, ... provided that the values of 0 11 (x) at integer points x = I, 2, ... , are pre-computed. Since the values of 0 11 (x) for x"";::;L-1 do not vanish, the computation of 0 11 (x) for x = 1,2, ... is quite different from that of <f>(x ).

Here, we first examine some properties of tMx) for x~L l. Let us recall the facts that ¢(x) vanishes for x~L 1, and that J:-1 rj>(x)dx = 1. Hence, for x~L-1, we can obtain from the last equation of ( 33) that lMx) = 1L-l ¢(y)dy + lx r/>(y)dy 1

(35) 0 L-t 82(x) 1L-I Bt(y)dy + lx Ot(y)dy 0 L-l =8z(L-1)+1x 1dy L-1 = fh(L -1) + (x-L + 1) (36) 83(x) 1L-I 82(y)dy + lx [82(L-1) + (y L + 1)]dy 0 L-1 1 83(L-l)+8 2 (L-l)(x-L+1)+ 21 ot(L l)(x L+1) 2 (37)
By induction, we can write lln{x) for x ~ L -1 as follows:

e,(x) ="I:

(x-~,+I )i On-J(L-1) j=O J. ( 38
)
where Ot (L-1) = 1, but the values of 0,_ 1 (L-1) for j = 0, 1, ... , n 2 are still to be determined. For determining O,(L-I) for n 2, 3, ... , we go back to the two-scale relation (34) for On(X ). Substituting x = L -1 into the equation yields

L-1

On(L -1) = rn 2:: Pk On(2L -2k) (39) k=O Since 2L 2-k~L-1 fork 0, l, ... ,L-1, from (38) it follows that

0,(2L-2-k) n-1 (L-1 k)l 2:: On-iL-1) . 1 j=O ]• (40)
As a result, O,(L 1) can be expressed as O,(L-1)

L-1 n-1 (L-l k)i rn I: Pk E On-AL-1)
.,

k=O j=O J. L-1 n-1 L-1 (L k)i = rn [O,(L -1) E Pk + E E Pk On-j(L-1) ,.;__-.,-.:...-] k=O J=l k=O (41)
Applying the relation ( 10), we then have the recursive formula

1 n-1 (L-1 (L 1 _ k)l) O,(L 1) = -2 , 2 E E Pk . 1 On-j(L -1) J=l k=O J. ( 42
)
for computing O,(L-1) for n = 2, 3, ... , starting with O, (L-1) = 1. Having obtained On(x) for an integer x~L-1, the values of On(x) for x = 1,2, ... ,L-2 can be determined from the following linear system of equations:

where

8n = [On{l) On(2) • • • On(L-2)]T C = (cl C2 • • • CL-2]T C; = L Pk On(2i -k) 2i-k~L-1 k~.I... . .L-1 (44) (45) (46)
and the matrix Pis defined by (30). The equations of the linear system (43) come from (34) by letting x = 1,2, ... ,L-2.

COMPUTING THE CONNECTION COEFFICIENTS OF WAVELETS OVER A BOUNDED INTERVAL

In solving a differential-integral equation of the form (47) defined on a bounded interval x E [a, b] by the wavelet-Galerkin method, the dependent variable y(x) is approximated by the wavelet series

Nb y(x) = L Yk</JJ,k(x) (48) k=N.
By the Galerkin approach, the coefficients Yt are determined from the following equations:

1 b ( dji d2y !"' ~ j"'jx' ~ ) a </JJ,k(x )f x, dx, dx 2 , .•• , ydx1. ydx2dx1.... = 0 (49)
for k = Na, Na + 1, ... , Nb. The construction of these equations involves the computation of finite integrals in (3 }- (7). As x-+oo, these integrals are called the connection coefficients of the wavelets. [START_REF] Latto | The evaluation of connection coefficients of compactly supported wavelets[END_REF] In this section, algorithms will be derived for computing the connection coefficients of wavelets over a bounded interval.

Evaluation of Mf(x) =fox ym</J(y-k)dy

Let the integral of the product of ym and </J(y -k) be denoted by

Mf(x) =fox ym</J(y-k)dy

Performing integration by parts successively m times on the above integral, we have

Mf(x) =fox ym</J(y-k)dy = xmO,(x-k)-m ~x-k (y + k)m-l</J(y)dy -k (50)
Hence, the integral MJ:'.(x) can be computed exactly in terms of Om(x), which is the multiple integral of the scaling function ¢(x) defined in Section 3.1.

Evaluation of integrals ff(x) = J; ¢<n>(y-k)¢(y)dy

Denote the integral of the product of the scaling function ¢(x) and its nth-order derivative ¢<n>(x-k) by ( 52)

The evaluation of ff(x) plays an important role in applying the wavelet-Galerkin method to solve differential equations. [START_REF] Chen | A wavelet-Ga\erkin method for solving Stefan problems[END_REF] Since there are no explicit expressions for representing the scaling function ¢(x) and its derivatives, the values of the integral r;(x) cannot be computed directly from ( 52). An algorithm has been developed by Beylkin 12 to compute fk'( oo ). The authors [START_REF] Chen | A wavelet-Galerkin method for solving population balance equations[END_REF] developed an algorithm for computing the values of the integrals ff(x) at dyadic points kj21 for positive integers j and k. To make this paper self-contained, we derive the algorithm in this subsection.

As we begin, we note that ff(x) has the following properties:

ff(x) = fk'(L-l) for x~L-1 ff(x) = 0 for lkl ~L-1 or x~O or x~k r~k(L-l)=(-l)nff(L-1) for k~O r~k(x)=(-1)nff(L-1) for x-k~L-1 (53) (54) (55) (56)
The properties (53) and (54) come from the fact that the support of ¢(x) is in the interval [0, L -1 ], which does not overlap with that of ¢<n>(x-k) for lkl ~L-1. The last two properties are derived from (52) by performing integration by parts for n times. Now, applying the two-scale relation ( 27) and ( 8) to (52), we have

L-1 L-1 rx ff(x) = 2n iE 1 ~0 PiPJ Jo ¢<n>(2y-2k-i)¢(2y-j}dy L-1 L-1 r2x-j = 2n-l iE j~O PiPJ Jo ¢<n>(y-2k-i + j)¢(y)dy (57)
This relation allows one to compute the exact values of ff(x) at dyadic points x = kj21 provided that the values of ff(x) at x = 1,2, ... ,L-1 are given. To determine the values of ff(x) for integers k and x, we first compute the values of ff(L-1) for k = 0, 1, ... , L-2. Letting x = L-1, we obtain from (53) and ( 57) that (58)

For n > 0, the equations obtained by substituting k = 0, 1, ... , L -2 into (58) constitute the following homogeneous system for unknowns ff(L-1 ), I= 0, 1, ... ,L-2:

f"(L-1) = Df"(L-I)

(59)

rn(L-1) = [f 0 (L-1) rr(L-1) • • • ff_ 2 (L-l)]T (60) D = [d!,m]O,;/,m,;L-2 dr,m = 2"- 1 ( 0 ~~-~ p;pj + (-1)" 0 ~~-~ P;Pj) O~i~L-1 O:!i:>J'liii:L-1 2/+i-j"=:lll 2/+i-1= -m
It is noted that in the formulation of (59) the property (56) has been used. As indicated by (59), the vector r n ( L-1 ) is the eigenvector of the matrix D that corresponds to the unity eigenvalue. However, the homogeneous linear system of equations in (59) does not admit the vector f"(L-1) to be determined uniquely. The required additional constraint or normalization condition can be derived from (18). The derivation of such a normalization condition is given below.

The nth-order derivative of ( 18) is

CXl L knq/nl(x-k) = n! (63) k=-CXl
Multiplying both sides of this equation by ¢(x) and then taking integration from x = -oo to oo, we obtain

k=~CXJ kn i: ¢<nl(x-k)¢(x)dx= k=~CXJ k"ff(L-1) = n! /_: ¢(x)dx =n! (64)
Substituting the relations ff(L-1) = 0 for lkl ~L-1 and r~k(L-1) = ( -1 )" rf(L-1) into the above equation, we have

L-2 n' L k" rf(L-1) = _: for n > 0 k=l 2 (65)
which is the desired normalization condition for the eigenvector of the matrix D associated with the unity eigenvalue.

Once the values of ff(L -1) are obtained, we can determine the values of ff(x) for x = 0, l, ... ,L-2 and lki~L-2. To this end, we note from (53}-{56) that there are only (L-2) 2 independent members in the set {ff(x): x = 1, 2, ... ,L -2; x -L + 2 ~k ~xl }. Let the independent members be packed in the vector Then the equations obtained from (57) by substituting k by x-L + 2, x-L + 3, .. . ,x-1 and x by 1, 2, ... , L -2 can be put into the following matrix-vector form:

(68) where [ Q, .• Ql,2 Q2,1 Q2,2 Q= QL~2.1 QL-2,2 ~~:~=~ ] (69) QL-~.L-2 Qi,j = [q;,j,k,m] 1 .;;,k,m.;;,L-2 (70) q;,j,k,m = P2i-j Pt-l-2k+m (71) d = [d(l) d(2) • • • d((L-2i)J (72) d(mL-2m+k)= I: p;pjrUc+i-j(L-1) (73) i,jEp(k,m,L)
and the index set Jl.(k,m,L) is given by

JL(k,m,L) := {(i,j): (L-1 ~2m-2k-i or L-1 ~2m-j),O~i,j~L-1} (74)
It is important to note that the eigenvalue set of the matrix Q includes 2-m, m = 0, 1, ... , L-2 with multiplicities L/2 -I((L-2)/2)-ml, but does not include 2. Hence, the vector r 0 can be obtained by solving the linear system (68). For n > 0, however, the matrix (2 1 -ni-Q) is singular and the rank deficiency is n. To have a linear independent system of equations for the unknown vectors r n' n = 1' 2, ... ' we seek in the following for additional relations among the members of r n.

Multiplying both sides of ( 63) by cf>(y) and then taking integration from y =0 to y =x, we obtain where lh (x) is defined in Section 3.2. The above equation can be written in the form

[(m-L + 2)n (m-L + 3t .. • (m-l)n]rn(m) = n! 9 1 (m) (75) (76) (77) (78)
Hence, the linear independent system of equations for rn can be finally obtained as follows: (i) Fori= l,2, ... ,n, replace the mth row (mE {1,2, ... ,£-2}) of the submatrix Q;,; in (69) by

[(i-L + 2f (i-L + 3f .. • (i-If]
and the mth row of Q;,j,j =I= i by a zero row vector, (ii) Replace the mth element of the subvector of d that corresponds to the submatrix Q;,; by n! 9 1 (i).

Evaluation of integrals A~•n(x) = J; ymcf><n>(y-k)cf>(y)dy

In solving a differential equation with non-constant coefficients by the wavelet-Galerkin method, it is required to compute the following integral:

A~.n(x) = 1x ymcf><n>(y-k)cf>(y)dy, m,n~O

In this subsection, we devote an effort to the evaluation of this integral.

(79) Since q,<n>(x) = 0 for x ~ L -1 or x ~ 0, it is easy to verify that the integral A;•n(x) has the following properties:

A;•n(x) = A;•n(L-1) for x~L-1 or x-k~L-1 (80) A;•n(x) = 0 for x~O or x~k or lki~L-1 (81)
Applying the two-scale relations ( 8) and (27) for tj>(x) and q,<n>(x), respectively, to the integral (79), we obtain the following two-scale relation for A;•n(x):

A;•n(x) = 2n-m-l Ltl Ltl t Pi Pi (7)/ A~k~~~;(2x-j) i=O i=O 1=0 (82)
Since A~•"(x) = r;(x), the above relation allows one to recursively calculate A;•n(x) for m = 1, 2, .... However, for fixed integers m and n, the values of A;•"(x) at various integers k and x have to be determined simultaneously. The formulation of a linear system of equations for solving A:•"(x) at integer points of k and x is given below.

Substituting x = L-1 into (82), we obtain

L-1 L-1 21+m-nAm,n(L-l)=" "p•p•Am,n . . (£-1) k L.., L.., I } 2k-J+I i=O }=0 L-1 L-1 m (m) + ;~o ~0 1 'f 1 xp; Pi I / A~-=_J~;(L -1) (83)
It follows from (81) that A;•n(L -1) vanishes for lkl ~L -1. Then, substituting k = 2-L, 3 -L, ... , L -2 into (83 ), we have the following linear system of equations for the unknowns A;•n(L-1):

(2l+m-ni-A) Am,n(L-l) = b
Here I is the (2£ -3) x (2£ -3) identity matrix, and Am•"(L -1) = [A~.:.."r(L-1) A;'..:.~(L-1) • • • A'f:..:." 2 (L-l)f

[ :2-L.2-L :2-L.3-L 3-L.2-L 3-L.3-L A= . . . . . . QL-2.2-L QL-2.3-L ar,s = L Pi Pi i-j =.~-21• 0'-'.i.,i~L-I :2-L.L-2] 3-L.L-1 . . . . . . • • • QL-2.L-2 (84) (85) (86) (87) ( 88
) ( 89
)
Since the matrix A has the eigenvalues 2 1 -i for i = 0, 1, ... , L -1, the matrix (2 1 +m-n I -A) is singular for O~n-m~L-1. Hence, for the case of n~m, we can directly solve the linear system (84) to find A;•n(L-1) fork = 2-£,3-L, ... ,L-2. As for the case of n > m, we have to look for an additional equation which allows, along with (84 ), one to determine the vector A m.n(L -1 ). To this end, we apply the relation ( 18) to obtain k=~oo e-m i:ymq,<n>(y)tj>(y-k)dy= :t:(-1)i(n~m)Mf i:yn-Jq,<n>(y)dy (90)

By performing integration by parts on the last integral of (90) for nj times, we have This is the desired additional relation for the vector Am•n(L-1 ). Hence, the non-singular system of equations for Am•n(L-1) can be formed by replacing any equation in ( 84) by (93 ).

I: xn-JcfJ(n)(x)dx = ( -l)n-J (n-j)! I: cfJ(J)(x)dx _ { ( -1 t-1 (n ~j)! [¢U-t>(oo)-¢U-t)( -oo)], j~ 1 - (-l)n n! Ioo cfJ(x)dx, j = 0 { 0, j~l (91)
Having obtained the values of A;•n(x) for x = L-1, we are to determine the values of A:•n(x)

for x = 1, 2, ... ,L-2 and lkl ~L-2. If m and n are specified, there are only (L-2) 2 independent unknowns to be determined simultaneously. These independent unknowns are packed into the vector The matrix Q is defined by (69) and the index set vx,n(k,x) is given by

Vm,n(k,x) := {(i,j): (L-1 ~2x-2k-i or L-1 ~2x-j),O~i,j~L-1} (96) (97)
(98)

As mentioned before, the eigenvalue set of the matrix Q contains 2 -i, i = 0, 1, ... , L -2, with multiplicities L/2 -I((L-2)/2)-il. Hence, for n > m the matrix (2 1 +m-nl-Q) is singular and its rank deficiency is n-m. To have a linear system of independent equations for Am,n, we seek in the following for additional relations among the elements of A m,n.

Multiplying both sides of ( 63) by ym ¢(y) and then taking integration from y = 0 to y = x, we obtain (100)

For integer x = i, the above equation can be written as i-1

L kn A;•n(i) = n! Mg'(i) (101) k=i-L+2
The equations in (101) with i = 1,2, ... ,n-m can be used together with (96) to construct a linear system of independent equations for the unknown vector Am,n. The procedure of constructing such a system has been described in Section 4.2. At this point, we have derived algorithms for computing the values of A;•n(x) at integer points x. Once these values are obtained, the values of A;•n(x) at dyadic points x = k/2j can be recursively obtained from the two-scale relation (82).

Evaluation of integrals T;:''n(x) = J; ym6n(Y-k)¢(y)dy

In solving an integro-differential equation with non-constant coefficients by the wavelet-Galerkin method, it is required to compute the integral T;,n(x) =lax ym6n(Y-k)¢(y)dy, n > 0 (102) Since ¢(x) = 0 for x ~ L-1 or x ~ 0, it is easy to verify that the integral T ;;•n(x) has the following properties:

(103) i;:''n(x) = 0 for x~O or x~k or k~L-1

With the substitutions of the two-scale relations (34) and (8) for 6n(x) and ¢(x), respectively, into ( 102 ), we obtain

L-1 L-1 m ( ) T;:''n(x) = 2-(m+n+1) L L L PiPj ml / T;l.~7~;(2x-j) i=O j=O 1=0 ( 105)
It is noted that fork~ 1-Land x~O. we have that x-k = x + L-1 ~L-1 and the integral On(x-k) is explicitly given by (42). As a result, the integral T;:''n(x) fork~ 1-L can be explicitly evaluated by

r;•n(x) = nE Bn-iL-I) [ t ( 1 ) (1 -_,L) 1 M({'+j-1 (x)] j=O 1=0 I 1• (106)
Having derived formulas for computing T;:''n(x) for x > L-I, we can solve the independent unknown i;:''n(x),x = 1,2, ... ,L-I, from (105). For fixed integers m and n, the independent unknowns of r;;•n(x) are packed in the vector The total number of elements of the vector ym,n is (3L-4 )(L-l )/2. It is noted that the required linear system of equations for solving this unknown vector is formed from ( l 05 ), and the system matrix is full rank. In constructing such a system of equations, the values of the integral 1;'-i,n(x) in (105) for i < m are known. Hence, the vectors rm,n can be computed recursively for m = 0, l, ... and n = l, 2, ... starting from 1°• 1 .

Evaluation of three-term connection coefficients

The integrals

n~k"(x) = [" cfJ(y)cfJ(m)(y-j)c/J(n)(y-k)dy 1 ' lo ( 109
)
for O~m~n~L/2-1 andj,k,m,n,x E Z, play an important role in solving non-linear differential equations with the wavelet-Galerkin method. [START_REF] Latto | Les ondelettes a support compact et Ia solution numerique de !'equation de Burgers[END_REF] In Reference 13, n;kn ( oo) is called the three-term connection coefficient of wavelets. In order to extend the wavelet-Galerkin method to finite-domain problems, we devote an effort to compute the values of n~t(x) at dyadic points x = kj21.

As we begin, we note that 0 1 ~t(x) has the following properties:

nj~t(x) = 0 for IJI, lkl, or li-kl ~L-l (110) O~k•n(x) = 0 for x-j,x-k, or x~O j, n~,t"(x) = Oj,kn(L-I) for X-j,x-k, or x~L-I (Ill) (112)
The formal properties ( 110) and ( 111) come from the fact that the supports of cfJ(i>(x) for i = 0, l, 2 .. . are all in the interval [ 0, L -l]. Now, substituting two-scale relations ( 8) and ( 27) into (109), we have

Since n 1 ~,k"(x) = O~,k"(L-1) for x~L-I, the values of O~icn(L-1) for integers j,k,m,n can be first computed. For this purpose, we note from (110)-(112) that, for fixed integers m and n, there are 3L 2 -9L+1 unknown n;kn(L-1), where k E [j+2-L,j-2+L]n[2-L,L-2] and j = 2 -L, ... , 0, ... , 2 -L. The equations in ( 113) associated with these unknowns constitute a linear homogeneous system as follows:

(114)

where

V = (v2-L VJ-L '' • VL-2 )T ( 115
) V• = [Om,n(L-1) n~•n (L-l) ... O".'•n(L-1)] J ;,v ;,v+l J,p (116) v = max(} + 2 -L, 2 -L ), Jl. = min(} + L -2, L -2 )
, and the elements of matrix S involve the triple products of the form p;.p;bPic• It is found by computation that the matrix S has eigenvalues 2 1 -k, k = 0, 1, ... , L -2, and that the multiplicity of the eigenvalue 2 1 -k is k + I. Obviously, ( 114) indicates that the vector v is the eigenvector of the matrix S corresponding to the eigenvalue of 2(1-m-n>. However, since the rank lost of S at this eigenvalue is m + n + 1, it is not sufficient to determine the vector v uniquely from (ll4). To have a system of linearly independent equations for solving the unknown elements of the vector v, we need extra equations. As before, the required extra equations can be derived from the moment equation (63). By first multiplying both sides of (63) by cp<m>(yj) and cp<n>(yk), respectively, and then taking integration from y = 0 to y = x, we have

Er n~t<x> = m! r:<x> j ), ( 117
) (118)
For fixed integers m and n, we can form an independent system of equations by deleting the equations of ( 114) which correspond to the unknowns 07,•;, j = 2 -L, 3 -L, . .. , 2 -L + n, and to the unknowns {}~•;, k = l, 2, ... , m, and then adding the equations in ( 117) for j = 0, 1, ... , n, and the equations in' ( 118

) for k = 1, 2, • • • , m, with x = L -l. It is noted that such a replacement
of equations is by no means unique, and a rigorous validation of this rank remedy is difficult. In practice, however, the rank of the resultant system of equations can be checked by a numerical computation, and the obtained values of n;:;<Ll) can be verified by using equations in ( 117) and ( 118) for 2-L~j,k ~L-2.

Having obtained the values of 0.7,~(L -1) for j, k E Z, we can proceed to determine the values of O_M 11 (x), for X= 1,2, ... ,L-2 and j,k E z. It can be shown from the properties of n;,•t in (110)-{112) that, for fixed integers m and n, there are only (L-2) 3 independent unknowns among n;,k"(x),x = l,2, ... ,L-2,j,k E Z. These (L-2) 3 independent unknowns are given by O.j,~(x) with x-L+2~j,k~x-1, and x = 1,2, ... ,L-2. The linear system of(L-2) 3 equations constructed from (113) by letting x-L + 2~j,k~xl, and 1 ~x~L-2 has the form

w = Rw+f ( 119
)
where w is the vector formed by the independent unknowns 07,•;(x), x-L + 2~xl,x = l, 2, ... ,L-2, the vector f contains elements 07,•;(L-l ). We have found by numerical computation that the matrix R has a unity eigenvalue with multiplicity K given by

K = { ~;,. (3L •) (L+2)L E --2, + ..:.._____.:~ i=L/2+1 2 8 if m + n~L/2 (120) if L/2 < m + n ~L -2
In other words, ( 119) is singular and it cannot be used to determine the unknown vector w without adding extra equations. To remedy the rank deficiency of the linear system ( 119 ), we again need the moment equations in (1I7) and (II8). Instead of using the approach of equation replacement in Sections 4.2 and 4.3 or the approach of equation argument in Reference 13, we propose here to combine moment equations to some equations in ( Il9 ). The moment equations in ( II 7) for j = 0, I, ... , x-I and x = I, 2, ... , L-2 are respectively combined with the equations in (li9) that correspond to unknowns {}7,j(x ), and the moment equations in ( 118) for k = x -L + 3, ... , x -2 and x = 1,2, • • • ,L -2 are respectively combined with the equations in ( II9) corresponding to the unknowns n;:' 1 ,k(x). Although the rank lost of R is K, we combine 2K moment equations with (II9) to ensure the resultant system is of full rank. As illustrated by numerical computation, this manner of equation combination indeed allows us to form a system of linear independent equations for the unknown vector w. In addition, the moment equations in ( ll 7) and ( 118) can be used to verify the computational results.

X 0•0 0•5 1•0 1•5 2•0 2•5 3•0 3•5 4•0 4•5 5•0
0•4 70467207784E + 00 0•114111691583E+01 0•650365000526E + 00 -0• 190934415568E + 00 -0•12083220831 OE + 00 0•498174997316E-O 1
Table II. The values of f/J(x) l/J< 1 l(x) and llt(x)

L=6 ¢(x) ¢<ll(x) Ot(X) O•OOOOOOOOE + 00 O•OOOOOOOOE + 00 O•OOOOOOOOE + 00 0•60517847E+00 0•15416762E+Ol 0•14131460E+OO 0•12863351E+Ol O•l6384523E+Ol 0•60074157E+OO 0•44112248E+00 -0• 24468283E + 0 I 0•10529082E+Ol -0•38583696E+00 -0•22327582E+Ol 0•10967114E+Ol -0•14970591E-OI 0• 12730265E + 0 I 0•98506614E+OO 0•95267546E-Ol 0•55015936E+00 0•98548673E + 00 -0•31541303E-Ol -0•37227297E+00 0•10033183E+OI 0•42343456E-02 0•44146491E-Ol 0•99965909E+OO 0•21 094451E-03 0•43985356E-02 0•99999151E+OO O•OOOOOOOOE + 00 O•OOOOOOOOE + 00 O•IOOOOOOOE+OI

NUMERICAL RESULTS

In this section we present computed values of functionals defined in ( 1 )-( 7) for the Six-coefficient Daubechies scaling function. For L = 6, the coefficients Pt. k = 0, l, ... , 5, are listed in Table I.

Table II lists the values of the scaling function ¢(x ), the derivative of ¢(x ), ¢(! l(x ), and the integral of ¢(x), 0 1 (x), for x = 0, 0•5, 1•0, 1•5, ... , 5•0. Table III lists the values of Mf'(x) fork = 0, m = 1,2,3 and x = 1,2, ... ,5. The values of non-vanishing functionals of fk(x),Ak' 1 (x), 1' k' 1 (x) and nJ:!<x) atx = 1,2,3,4,5, are listed in Tables IV-VII, respectively. It is noted that in computing the values in Tables II-VII, the 12 decimal digits of Daubechies' wavelet coefficients are used. We have verified the obtained values by using the moment equations that are not employed to remedy the rank deficiency, and the equation residues are all in the order of 10-9 • Moreover, the computed three-term connection coefficients nJ:!<S) agree with those listed in Reference 13.

AN APPLICATION EXAMPLE

The non-linear parabolic equation

ou ou 1 o 2 u -+ u -= -- ot ox Re o2x (121)
is known as the Burgers equation, [START_REF] Fletcher | Burgers' equation: a model for all reason[END_REF] which is one of the simplest partial differential equations describing both non-linear propagation and diffusive effects. It represents a first step in the hierarchy of approximations of the Navier-Stokes equation. Depending on the magnitude of the viscous term,

I 0•40662888E + 00 0•30755931 E + 00 0•24746348E+00 2 O•I0138604E+OI 0•10542175E+OI 0•11618193E+OI 3 0• 77363652E + 00 0•53674234E + 00 0• 52903635E-O I 4 0•8160348IE+00 0•66267182E + 00 0-42355381 E+OO 5 0•81740117E+00 0•66814467E+OO 0•44546004E + 00
Table IV. The values of f}(x) for L = 6

X k rf(x) X k rf(x) X k rf(x) -3 -0•96071829E-02 3 -1 -0•74488223E+00 5 -4 -0•34246575E-03 -2 0•24682915E + 00 0 0•45379527E-02 -3 -0•14611872E-OI -I -0•10642085E+OI I 0•73437630E+OO -2 0•14520548E+00 0 0•82732896E+OO 2 -0•12428316E + 00 -2 -0• 74520548E + 00 2 -2 0•14376046E+00 3 -1 0•89648439E-05 0 -0•11162444E-16 -1 -0•77113404E+OO 0 0•74528563E+00 I 0• 74520548E + 00 0 0•74435080E-01 I -0•14539422E + 00 2 -0•14520548E + 00 I 0•56789284E+OO 2 0•15053970E-OI 3 0•14611872E-01 4 0•34246575E-03 Table V. The values of A!" 1 (x) for L = 6 X k A!• 1 (x) X k A!• 1 (x) X k A!• 1 (x) -3 0•61238997E-02 3 -1 -0•33884086E+00 5 -4 -0•39622225E-05 -2 0•16013363E+OO 0 -0•48571617E+00 -3 -0•67621931 E-03 -1 -0•74526083E+00 I 0•10513436E+Ol -2 0•19212883E-01 0 0•57900506E + 00 2 -0•26736083E+00 -2 -0•121 04326E + 00 2 -2 0• 36873826E-O 1 4 0 -0•49996340E + 00 0 0•10224223E+01 -1 -0•39613509E+OO I 0• I 0853692E + 0 I I -0•12104326E+00 0 -0•33492810E+00 2 -0•33106420E +00 2 0•19212883E -01 I 0•69350982E + 00 3 0•44926126E-0 I 3 -0•67621931 E-03 4 -0•39622225E-05 Table VI. The values of T!• 1 (x) for L = 6 X k T!• 1 (x) X k T!• 1 (x) X k T!• 1 (x) -4 0•40660602E + 00 3 -4 0• 77363681 E + 00 4 I -0• 76349559E-0 I -3 0•40660225E + 00 -3 0• 77388859E + 00 2 0•58249586E-02 -2 0•40271563E+00 -2 0•76364511E+00 3 -0•14233365E-03 -1 0•44173660E + 00 -1 0•83517453E+00 5 -4 0•81740146E+00 0 0•1 0494506E + 00 0 0•40735866E + 00 -3 0•81749716E+ 00 2 -4 0•10146510E+Ol I -0•48100476E-01 -2 0•80964464E+00 -3 0•10080259E+01 2 -0•16157050E-02 -I 0•87377189E+00 -2 0•10401149E+01 4 -4 0•81603510E+00 0 0•46400092E + 00 -I 0•10491431E+Ol -3 0•81613080E+00 I -0•13185340E+00 0 0• 56252533E + 00 -2 0•80824884E+00 2 0•28977257E-01 I 0•17523787E-Ol -1 0•87069022E + 00 3 -0•11265687E-02 0 0•50032473E+00 4 -0•81106612E-05
Table VII. The values of oJ:~(x) for L = 6

X j k f20,1(x) j,k X j k OO,I(x) j,k X j k OO,I(X) j,k v I -3 -3 -0•71559141E-03 3 -4 0•31710703E+OO 5 -I -2 0•87462277E-01 -2 0•13550268E -02 -3 -0•13345958E + 00 -I -0•24844590E+00 -I 0•78711878E-05 2 -2 0• 52989782E-02 0 0•31358775E+OO 0 -0•61485IOIE-03 -I -0•11566110E-01 I -0•12527255E + 00 -2 -3 0•52989782E-02 0 0•25492658E-01 2 -0•61773222E-02 -2 -0•11566110E-01 I -0•19359467E-01 3 0•32901969E-04 -I 0• 25492658E-0 I 4 0 2 0• 25336150E-07 0 -4 0•24592627E-OS 0 -0•19359467E-OI -4 0•49689213E + 00 -3 0•23763642E-02 -1 -3 -0•22426219E-01 -3 0•329019IOE-01 -2 0•93548371E-01 -2 0•60684150£-01 -2 0•14542464E-02 -I -0•62717551 E + 00 -I -0•17563529E + 00 -I -0•24844521E+OO 0 0• 29322842E-I 0 0 0•13782300E+00 0 0•31359528E+00 I 0•49689180E + 00 0 -3 0•82360955E-02 -4 -0•12529008E + 00 2 0•32902689E-01 -2 0•19635413E+00 -3 -0•61351029E-02 3 0•14522972E-02 -I -0•91407419E+OO 2 -2 -0•16454414E-OI 4 0•15241273E-05 0 0• 70948150E + 00 -I 0•37778887E-01 -3 -0•4456481 OE-03 2 -2 -2 -0•16454414E-01 0 -0•46700711E-01 -2 -0•20741515E-01 -I 0• 3 7778887E -0 I I 0•20316776E-OI -I 0•87462280E-01 0 -0•46700711E-Ol 3 2 -0•71559141E-03 0 -0• 24844590E + 00 I 0•20316776E-01 -4 0•13550268E-02 I 0•31358775E+00 -I -2 0•87355550E-0 I -3 0•78711888E-05 2 -0• 12527255E + 00 -I -0•24981584E + 00 -2 -0•614851 OlE-03 3 -0•61773222E-02 0 0•31710703E+00 5 -4 -I -0• 76206365E-06 4 0• 3290 1969E-04 I -0•13345958E + 00 0 -0•44639911 E-06 2 -2 0•13394071E-03 0 -2 0•94031790E-0 I -4 0•19493567E-05 -I 0•49255216E-02 -I -0•62003156E + 00 -3 0•48873854E-06 0 -0•16451344E-OI 0 -0•19146537E-01 -2 -0•12296325E-05 I 0•37810269E-01 I 0•54276748E+00 -3 -I -0•32455570E-04 2 -0•46774186E-01 -2 -0• 22426219E-0 I 0 -0• 72614859E-03 3 0•20491688E-01 -I 0•60684150E-OI I 0•12518005E-02 4 -0•13589007E-03 0 -0•17563529E + 00 2 0• 24982636E -03 3 -I -0• 32455570E-04 I 0•13782300E+OO -4 -0•11881821E-02 0 -0• 72614859E-03 3 -I -I -0•24844521E+00 -3 0•44515936E -03 I 0•12518005E-02 0 0•31359528E + 00 -2 -2 0•13394071 E-03 2 0•24982636E-03 I -0•12529008E + 00 -I 0•49255216E-02 3 -0•11881821E-02 2 -0•61351029E-02 0 -0•16451344E-01 4 0•44515936E-03 0 -1 -0•62715213E+00 2 0•37810269E-Ol 4 0 -0• 76206365E-06 0 0•28821311E-03 -4 -0•46774186E-0 I I -0•44639911 E-06 I 0•49612985E+OO -3 0• 20491688E -0 I 2 0• 19493567E-05 2 0• 34806875E-0 I -2 -0•13589007E-03 3 0•48873857E-06 -I 0•87355550E-0 I -1 -I -0•4456481 OE-03 4 -0•12296325E-05 0 -0•24981584E+OO 0 -0•20741515E-01
the Burgers' equation behaves as an elliptic, parabolic or hyperbolic partial differential equation. Therefore, Burgers' equation has been widely used as a model equation for testing and comparing computational techniques. When the viscous coefficient 1/ Re in ( 121 ) is small, Burgers' equation involves phenomena that change rapidly from point to point. Problems of this type require mathematical representations that can respond to a local variation. The compactly supported wavelets derived by Daubechies 1 are good bases for 'local' problems. They have been used successfully to solve Burgers' equation with periodic boundary condition. 22 • 24 Due to the lack of accurate finite-domain connect coefficients, the wavelet bases have not been used to solve finite-domain problems with non-periodic boundary conditions. In the following, we apply the proposed interval wavelet-Galerkin approximation scheme to find the solution of the finite-domain Burgers' equation.

Consider the Burgers' equation (121) with the following boundary conditions:

u( -l,t) = 1 (122) u( 1, t) = 0 (
~-• = Re "2: c,_.u 1 _.(t), 1=2-L-2J,3-L-2J, ... ,2J -1 (125) k=2-L-2 1
In the above differential equations, the coefficients a"' b,_u and c~.~ are given by a,_. = j' </>J,(x)<f>.~ .

• (x)dx = rf_/(2J -I)-rf-t< -l-2J) -I (126) b = 1 1 ,~. (x),~. (x)d¢ 1 _,(x) dx = 23J/ 2 [f2°• 1 . (2J-I)-0°' 1 . ( -/ -2J)] (127) '•'-' '+'1.1 '+'u dx k-1,<-1 k-1,<-1 -1 c = j' ,~. (x)d 2 ¢ 1 _.(x) dx = 2v[r 2 (2J-I)-r 2 (-l-2J)] 1.. '+'1.1 dx2 k-/ k-/ -I (128)
where rf(x) and omk,n(x) are defined by ( 4) and ( 5), respectively. For u(x,t) to satisfy the j, boundary conditions (122) and (123), the expansion coefficients U 1 _,_L-2 1 (t) and u1.2 1 _,(t) must satisfy the following relations:

1 L-3 u./.2-L->'(t) = ¢(L-2)[2-J/2-~ </>(i)uJ _,_c,(t)] (129) -1 L-2 uJ.ll_,(t) = ¢(1) t; <f>(i)u 1 ,.~jt) (130)
As a result, there are 2J+l + L-4 independent expansion coefficients

U 1 • 1 (t), k = 3-L-2J, 4
I: a,.tuu(O) = 2 (l-x)</>,,(x)dx k=2-L-2.! -1 = - 1 -[e 1 (2J -/)-e~(-1-2J)-rJM/(2J) + rJM/(-2J)l 2J/2+1 1=3-L-2J,4-L-2J, ... ,2J-2 (134)
where a,.P 8n(x) and M;(x) are defined in (126), ( 2) and (3), respectively. Hence, the initial conditions u '• t ( 0 ), k = 2 -L -2J, 4 -L -2J, ... , 2J -1, can be obtained from solving the linear equations of ( 134) with the additional relations of ( 129) and ( 130 ).

Having obtained the differential equations and initial conditions for UJ,k(t), we can utilize a numerical integration scheme to find the expansion coefficients UJ,k(t). In actual computation, we have invoked the subroutine DIVPAG in IMSL mathematical library2 [START_REF] Zhiqian | Hierarchical method for elliptic problems using wavelet[END_REF] to solve the initialvalue problems. In calling this subroutine, the tolerance parameter and the initial time step are respectively set to 10-6 and 0•1, while all the other parameters are set to their default values. By choosing J = 5 and L = 6, the time evolutions of the waveforms of the wavelet-series solution of Burgers' equation are plotted in Figures 1234. Figures 1 and2 show the solutions of Burgers' equation with a linear initial condition for Re = 1 and Re = 100, respectively. The results shown in Figures 3 and4 are the solutions evolved from a discontinuous initial condition. From Figures I and 3, it can be observed that for a low Reynolds number or high viscous coefficient, the solution to Burgers' equation evolves to a smooth steady state, irrespective of continuous or discontinuous initial conditions. As can be seen from Figures 2 and4, the solution evolutions of Burgers' equation with low viscous coefficients are quite different from those with high viscous coefficients. For the discontinuous initial condition, the solution of Burgers' equation with Re = 100 is a shock wave. Before the shock wave touches the right boundary, its penetration is just like in an infinite domain. However, when the shock wave touches the right boundary, its action like the billow beats the reef and generates the spray. In this situation, we cannot find the steady-state solution since the problem becomes singular.

It is noted that there is no exact solution for the finite-domain Burgers' equation. In order to verify the numerical solution, it is often compared it with that of the infinite domain. For the purpose of demonstrating that the solutions shown in Figures 1234are true approximate solutions of the finite-domain Burgers' equation, we compare in Table VIII the wavelet-series solutions u(x, 0 • 92) with the solution u p(x, 0 • 92) obtained by Galerkin approximation using a ninth-degree polynomial as a trial solution [START_REF] Fletcher | Burgers' equation: a model for all reason[END_REF] and the solution u 00 (x, 0•92) of the infinite-domain Burgers' equation. Obviously, the local bases used in this paper can respond well to the sharp change of the shock wave.

CONCLUSIONS

The wavelet-Galerkin method has been shown in the literature to be a powerful tool for the numerical solution of partial differential equations. The computation of wavelet-Galerkin approximation relies heavily on the evaluation of connection coefficients, which are integrals with their integrands

  e 0 cf>(y)cf>(n)(y-k)dy = n! 0 cf>(y)dy or 00 I: knfk'(x)=n! 61(x) k=-oo For an integer x = m, the above equation can be written as m-1 I: e r;(m) = n!lMm) k=m-L+2

= 2 I

 2 (-l)nn!, j=O Substituting (80), (81 ), and (91) into (90), we have L-2 m . I: I: kn-m+J A~k''n(L-1) = (-l)n n! for n~m : kn-m A~_':(L-1) = ( -1 r n! -I: I: kn-m+J A~~J,n(L-1) (93) k=2-L J=l k=2-L

2 ( 95 )

 295 (x) = [A;.:_"L+ 2 (x) A;.:_nL+ 3 (x) .. • A;.:_" 1 (x)], x = 1,2, ... ,L-By letting k = x-L+2,x-L+3, ... ,x-1 and x = 1,2, . .. ,L-2 in (82), we obtain the following sy~tem of equations for the unknown vector Am,n: I where I e = [e(l) e(2) .. • e((L-2) 2 )]T e(xL-2x + k) = I: p; Pi A~ic:;-/L-1) i,)Evm.n(k,x) L-l L-l m (m) +I: I: I: P;PJ I / A~k-=_!j~;(2xj) i=O }=0 l=l

  Tm,n = [Tm,n(l) Tm,n(2) ... Tm,n(L-

  -L-2J, ... ,2J-2, that are described by the differential equations in (125) with u.~_ 2 _L_ 2 .~(t) and uJ:P_,(t) being replaced by (129) and (130}, respectively.The initial conditions for the differential equations in ( 125) are derived from the initial condition u(x, 0) of the problem. Here, we consider the discontinuous initial condition{ 1 for -1 ~x ~ 0 u(x,O) = 0 for 0 < x~l ( 131)and the continuous initial condition1 u(x,O) = 2 (1-x) (132)For the case of the discQntinuous initial condition specified by (131), the initial conditions u.~.t(O) satisfy (133) From these equations and relations in (129) and (130), we can obtain the initial conditions u.~.t(O), k = 3 -L -2 J, 4 -L -2 J, ... , 2 J -2. Similarly, for the case of the continuous initial condition given by (132), the initial conditions uu(O)

Figure 1 .Figure 2 .

 12 Figure 1. Numerical solutions of Burgers' equation with Re = I and linear initial condition (132)

  Then the condition (16) implies thatThe above relation further implies

  [START_REF] Mallat | Multiresolution approximation and wavelets[END_REF]

Table I .

 I Daubechies' wavelet filter coefficients forL=6

	p;
	0
	1
	2
	3
	4
	5

Table Ill .

 Ill The values of M 0 (x) form= I, 2, 3

			L=6
	X	MJ(x)	MJ(x)	MJ(x)

Table VIII .

 VIII Numerical solutions of finite-domain Burgers' equationRe = 100, t = 0.92

	X	W -G,J =4	W -G,J =5	PA23	ES23
	-1•0	1•0000	1•0000	1•0000	1•0000
	-0•9	0•8508	0•8122	0•9956	1•0000
	-0•8	0•8809	0•8727	1•0456	1•0000
	-0•7	0•8810	0•8727	1•0672	1•0000
	-0•6	0•8811	0•8728	1•0402	1•0000
	-0•5	0•8817	0•8737	0•9831	1•0000
	-0•4	0•8860	0•8781	0•9303	1•0000
	-0•3	0•8981	0•8913	0•9128	1•0000
	-0•2	0•9204	0•9157	0•9444	1•0000
	-0•1	0•9487	0•9465	J.0159	1•0000
	0•0	0•9752	0•9742	1•0963	1•0000
	0•1	0•9920	0•9914	1•1411	1•0000
	0•2	0•9989	0•9983	1•1057	1•0000
	0•3	0•9948	0•9980	0•9613	0•9998
	0•4	0•9260	0•9610	0•7099	0•9764
	0•5	0•1090	0•1156	0•3933	0•1861
	0•6	-0•0270	0•0029	0•0905	0•0015
	0•7	0•0063	0•0000	-0•1017	0•0000
	0•8	0•0000	0•0000	-0•1154	0•0000
	0•9	0•0000	0•0000	0•0091	0•0000
	1•0	0•0000	0•0000	0•0000	0•0000

W-G: wavelet-Galerkin; PA: polynomial approximation; ES: exact solution

ACKNOWLEDGEMENT

This work was supported by the National Science Council of the Republic of China under Grant NSC-82-0402-E-006-24 7.

being the product of wavelet bases and their derivatives or integrals. We have described the algorithms for the exact evaluations of connection coefficients for Daubechies' compactly supported orthonormal wavelets on a bounded interval. These algorithms extend the application scope of the wavelet-Galerkin method to finite-domain problems. They also play an essential role in applying the newly developed interval wavelets 19 • 20 to the numerical solution of partial differential equations. This role has been demonstrated by a numerical example.


Sadek Labib

Terrissa
email: terrissa@univ-biskra.dz

Radhia Bouziane

Jean-François Brethé
email: jean-francois.brethe@univ-lehavre.fr

Towards a new approach of Robot as a Service (RaaS) in Cloud Computing paradigm

Keywords: Robots, Cloud Computing, SOA, Cloud Robotics, Robot as a Service. I

For many years, robots appear in most fields. At times, we approach closer to create intelligent robots due to success in computer technology. Current developments in Cloud Computing introduce this concept in robotics field.

Many projects have taken initiatives towards Cloud

Robotics that allow the robots to outsource computing capabilities over the Cloud, like communication resources, storage, and computing power. The aim of our work is to define a kind of service in the direction of Cloud Robotics, which is 'Robot as a Service' (RaaS). This concept is based on the functions of SOA, and means the use of robots features in the Cloud Computing as a demand service.

INTRODUCTION

Robotics is a field of science and technology dealing with the issues of design, control, applications and maintenance of robots [START_REF] Jovovic | Development and some examples of robots in agriculture[END_REF].Robots are now used widely in scientific research, manufacturing technology, civil engineering, as well as in medicine, underwater investigations and space research. An important challenge in this domain is to make robots able to operate and adapt with an autonomous way to their environment.

Cloud Computing is a generic term that involves delivering hosted services over the Internet. The name Cloud Computing was inspired by the Cloud symbol that is often used to represent the Internet [START_REF] Mahmood | Cloud Computing for Enterprise Architectures[END_REF].

Cloud Computing has potential to speed up many computationally-intensive robotics. In 2010, James Kuffner coined the term "Cloud Robotics" and described a number of potential benefits [START_REF] Kuffner | Cloud-Enabled Robots[END_REF]. This approach would allow robots to offload compute-intensive tasks like image processing and voice recognition and even download new skills instantly [START_REF] Kopacek | Development trends in robotics[END_REF].This paper presents our research on the related concepts of the purpose of this work that is 'Robot as a Service' (RaaS), and an illustration of our design to implement this kind of service.

II. RELATED CONCEPTS

A. Cloud Computing

Cloud Computing is the latest paradigm that involves delivering hosted services over the Internet, based on a pay-as-you-go approach. According to NIST (National Institute of Standards and Technology), Cloud Computing is on-demand access to a shared pool of computing resource. It is an all-inclusive solution in which all computing resources (hardware, software, networking, storage, and so on) are provided rapidly to users as demand dictates [START_REF] Mahmood | Cloud Computing for Enterprise Architectures[END_REF].

The concept of Cloud services development encompasses several three different types of development: Software as a Service (SaaS), Platform as a Service (PaaS), Infrastructure as a Service (IaaS) [START_REF] Fehling | Cloud Computing Patterns : Fundamentals to Design, Build, and Manage Cloud Applications[END_REF], and even X as a Service (XaaS), where X can be any Items such as: Robot as a Service (RaaS) [START_REF] Du | Design of a Robot Cloud Center[END_REF].

B. Service-Oriented Architecture

Service-Oriented Architecture or SOA is way to design, implement, and assemble services to support or automate business functions [START_REF] Barry | Web Services,Service-Oriented Architectures, and Cloud Computing[END_REF]. An SOA is built using a collection of services that communicate with each other. The communication can involve either simple data passing or it could involve two or more services coordinating some activity [START_REF] Barry | Web Services,Service-Oriented Architectures, and Cloud Computing[END_REF]. Figure 1 shows the collaborations in a Service-Oriented Architecture. The collaborations follow the "find, bind and invoke" paradigm where a service consumer performs dynamic service location by querying the service registry for a service that matches its criteria. If the service exists, the registry provides the consumer with the endpoint address for the service [START_REF] Endrei | Patterns: Service-Oriented Architecture and Web Services[END_REF]. Cloud Computing extends the scope of SOA to include the development platform and the execution infrastructure [START_REF] Du | Design of a Robot Cloud Center[END_REF].The services provided in the Cloud come from multiple organizations. These organizations are referred to Cloud providers. As a result, the Cloud has multiple services provided by multiple Cloud providers [START_REF] Barry | Web Services,Service-Oriented Architectures, and Cloud Computing[END_REF].

C. Robot Operating System (ROS)

ROS is an open-source, meta-operating system for your robot. It provides the services you would expect from an operating system, including hardware abstraction, low-level device control, implementation of commonly-used functionality, message-passing between processes, and package management [START_REF] Ros | [END_REF]. With the aid of ROS, it is possible to command the robot to walk from place A to place B without thinking about which walking algorithm will be used. This meta operating system is extendable with modules, called stacks. There are modules for many robots like Nao, TurtleBot or PR2 [START_REF] Johannben | Nao Robots in the Cloud[END_REF].

In ROS, processes are called nodes which are organized in a Peer-to-Peer network without a central point of communication. The master node provides name registration and lookup for all custom nodes. Without the master node, it is not possible to communicate with nodes, services, messages, and others [START_REF] Johannben | Nao Robots in the Cloud[END_REF].

D. Cloud Robotics

In 2010, James Kuffner has introduced the topic "Cloud Robotics" [START_REF] Kuffner | Cloud-Enabled Robots[END_REF]. This idea combines the computational power of the Cloud Computing and the availability of internet-connected devices in robotics [START_REF] Lorencik | Cloud-Based Object Recognition: A System Proposal[END_REF].The advantage of this concept is that it enables robots to carry just a minimum set of hardware resources, and access all knowledge and resources available on the Cloud. Cloud Robotics pushes the idea of Inaba "remote brained robots" (1997) [START_REF] Kehoe | A Survey of Research on Cloud Robotics and Automation[END_REF] with the aid of unbounded computation power on demand [START_REF] Johannben | Nao Robots in the Cloud[END_REF].

III. RELATED WORK

The following projects are some currently working on the topic of Cloud Robotics.

A. RoboEarth

RoboEarth represents a World Wide Web for robots [START_REF]RoboEarth Project[END_REF].Through RoboEarth robots are able to share data and learn from each other [START_REF] Kehoe | A Survey of Research on Cloud Robotics and Automation[END_REF]. This project is part of the Cognitive Systems and Robotics Initiative founded by the European Union. It provides a distributed database to store information like object descriptions, maps and task specifications [START_REF] Johannben | Nao Robots in the Cloud[END_REF] created by humans in a format that is readable by the robots. RoboEarth offers a Cloud Robotics infrastructure, which includes everything needed to close the loop from robot to the Cloud and back to the robot.

B. Rapytua

Rapytua is an open source Platform-as-a-Service (Paas) framework designed specifically for robotics applications [START_REF]RoboEarth Project[END_REF]. It is based on an elastic computing model that dynamically allocates secure computing environments for robots [START_REF] Rapyuta | The RoboEarth Cloud Engine[END_REF]. Furthermore, this project is also called "the RoboEarth Cloud Engine" because Rapyuta's computing environments allow robots to easily access the RoboEarth knowledge repository [START_REF]RoboEarth Project[END_REF].

Figure 3 shows that by extending the RoboEarth database, robotic specific data and processing units are both settled in the Cloud [START_REF] Johannben | Nao Robots in the Cloud[END_REF].

C. Cloud-based robot grasping

It is a project which goal has been to determine the optimal way to grasp a newly encountered object for robots [START_REF] Kehoe | A Survey of Research on Cloud Robotics and Automation[END_REF], with the aid of the Google object recognition engine, which is established by the Google Goggles [START_REF] Johannben | Nao Robots in the Cloud[END_REF], a free image recognition service for mobile devices [START_REF] Kehoe | A Survey of Research on Cloud Robotics and Automation[END_REF]. The project is structured into two phases [START_REF] Kehoe | Cloud-Based Robot Grasping with the Google Object Recognition Engine[END_REF]:

 The offline phase which aims to train the recognition server by storing semantic information about objects.  The online phase where robots upload images about objects to receive a possible grasping policy by matching sensor data against 3D CAD models in an online database. IV.

DESIGN OF RaaS

In this section, we will clarify a global view of our design to implement the RaaS, the use of robots features on demand, as a service, by the research of available services in different Clouds, where a robot would be able to accomplish a specific task with a simple connection to the Cloud, and regardless of hardware or software.

The general architecture of our system is illustrated as follows in Figure 5.

To determine the composition of a RaaS system, we have identified four components in this architecture:

1. The Cloud Administrator: A Cloud side administrator, used to deploy new services (executable packages) in the Cloud, available to a Client. 2. The Client: The Client RaaS benefits of the characteristics of Cloud Computing. It represents two main actors:  Robot: this is the main actor. It benefits of all the services necessary to perform its required task.

The relationship between these two components is inspired by SOA (Figure 6). 3. The Cloud: For Cloud Robotics solution, the Cloud is the part that provides the software, and the infrastructure necessary for the applications of a robot. In our system, we propose here the storage of executable packages, and the use of infrastructure. We have defined a virtual robotic layer which contains virtual robot systems (VRS).The VRS is a robotic operating system which is virtually executed in the cloud environment. In our experiment it is composed by an operating system (Ubuntu), a robot operating system (ROS) and stacks. It represents a robotic platform. 4. The network: The set of protocols and technics used to ensure the connection and the communication between the Client and the Cloud.

The idea of a RaaS system is to use an executable plan as a service from internal or external repertories in the Cloud. If the plan does not exist in the local plan, we start a research task in the other Clouds.

V. SCENARIO

We can propose a several scenario for our approach but the most typical scenario is when the robot needs packages to perform a specific task, it will be able to connect to the Cloud and retrieves these packages. In the Cloud side, the provider should offer the requested package. The functioning of the system is described in Figure 7.

 An administrator Client can send a request to a Cloud service for a package (already published by the Cloud Administrator) compatible with a particular robot.  The only requirement is to have a connection so that the robot can execute the associated program in its virtual machine.

Figure 7. Functioning of the system  The program manages a set of Nodes, and also the publication of Messages in associated Topics. These notions of ROS can perform a set of operations on the robot.

The following sequence diagram shows the interaction between the system components. The "Administrator" Client, after an authentication, sends a request to the Cloud service, asking for an executable plan which delegates the commands to the particular robot. After exploring the database the plan will be stored, if exist, in the private robotics platform for execution.

VI. IMPLEMETATION

To test our approach we are simulated the robot service oriented architecture. Figure 9 is a descriptive scheme of the application.

The idea is to recover an executable package compatible with ROS from the machine 2 to run it on the machine 1, so that the robot connected to this latest machine could accomplish its assigned task, that simulates the behavior in a Cloud Computing architecture, where the package is a service that is described in the registry, and is generally in the Cloud.

This reflects the concept of 'Robot as a Service' (RaaS) that we have defined. We have also developed two interfaces for the PC and smart-phone users (under android). These interfaces are hosted in the Web server of free virtual machine offered by the provider. Through these interfaces the customer is able to manage its robots (add, delete or change a robot). He can also supervise and monitor these robots. After authentication, the client can get the desirable package (See Figure 10).

VII. CONCLUSION

In this paper, we have defined a new approach in Cloud Robotics. It's Robot as a Service. It's an architecture based on SOA paradigm and ROS as a robotic middleware. This solution allows robots to perform several tasks by connecting to Clouds and do not care about robots features or hardware. We have also tested our approach using PR2 and Care-O-Bot robots with different environment for a first validation. The next step of this work will be to test our architecture on real Cloud infrastructure like Amazon EC2 (public Cloud) with a real client (e.g., industrial client).

Figure 1 .

 1 Figure1. Collaborations in a Service-Oriented Architecture[START_REF] Endrei | Patterns: Service-Oriented Architecture and Web Services[END_REF]

Figure 2 .

 2 Figure 2. Core concepts of ROS[START_REF] Johannben | Nao Robots in the Cloud[END_REF]

Figure 3 .

 3 Figure3. The Cloud Engine "Rapyuta"[START_REF] Johannben | Nao Robots in the Cloud[END_REF]

Figure 4 .

 4 Figure 4. Online phase of Cloud-based robot grasping[START_REF] Kehoe | Cloud-Based Robot Grasping with the Google Object Recognition Engine[END_REF]

Figure 5 .

 5 Figure 5. System Architecture  Client Administrator: He intervenes in the client side, he is responsible of the management and the local robots configuration through a Web interface that provides the following operations : 1. Adding a new robot: by adding its identifier, physical logical address, the robot type, the system used packages and

Figure 6 .

 6 Figure 6. SOA and System components

Figure 8 .

 8 Figure 8. Sequence diagram

Figure 9 .

 9 Figure 9. Illustration of the application

Figure 10 .

 10 Figure 10. Main interface

Figure 11 .

 11 Figure 11. The behavior of PR2 in gas station