*íllK MASARYK UNIVERSITY I IUI I Faculty of Science Construction of Wavelets Habilitation Thesis Václav Finěk 2015 Contents List of Symbols 3 Introduction 5 1 Wavelets on the Real Line 8 1.1 Riesz Bases................................... 8 1.2 Wavelets..................................... 10 1.3 Biorthogonal wavelets.............................. 11 1.4 Oblique projections............................... 13 1.5 The Discrete Wavelet Transform........................ 15 1.6 Polynomial exactness.............................. 16 1.7 B-Splines .................................... 17 2 Wavelets on the Bounded Interval 19 2.1 Wavelet Basis.................................. 19 2.2 Multiscale Transform.............................. 22 2.3 Riesz Bases in Sobolev Spaces......................... 23 2.4 An Application of Riesz Basis Property.................... 26 3 Selected Results 28 3.1 On the Exact Values of Coefficients of Coiflets................ 28 3.2 Construction of Optimally Conditioned Cubic Spline Wavelets on the Interval ........................ 29 3.3 Cubic Spline Wavelets with Complementary Boundary Conditions.............................. 30 3.4 Wavelet Basis of Cubic Splines on the Hypercube Satisfying Homogeneous Boundary Conditions................ 31 3.5 On a Sparse Representation of a n-dimensional Laplacian in Wavelet Coordinates....................... 32 Preprints of articles 36 2 List of Symbols N the set of all positive integers No the set of all nonnegative integers Z the set of all integers R the set of all real numbers the closure of the set | • | the absolute value 5i:J the Kronecker delta, 5l:l := 1, 5lJ := 0 for i ^ j span the linear span supp the support k (•) the spectral condition number of a matrix C < D means that C can be bounded by a multiple of D independently of param- eters on which they may depend Lp (0,1) the space of square integrable functions Hs (0,1) the Sobolev space of order s G R on (0,1) Hq (0,1) the Sobolev space of H1 functions satisfying homogeneous Dirichlet boundary conditions Cm (R) m G No, the space of m-times continuously differentiable functions I2 (J) I2 (J) := {v : J -)■ R, EAeJ |vA|2 < oo} Ilm (0,1) the space of all algebraic polynomials on (0,1) of degree less or equal to m G N0 ||-|| L2-norm a norm on some space H the seminorm on Hs (0,1) (•, •) L2-inner product or a dual form (•, •)H an inner product in H Wh \hs(o,i) 3 jo the coarsest level in a multiresolution analysis in a given context A a wavelet index A := (j,k) ■ H be defined by T : {ck}k fcez ffcez ^ Z^i Cfe6fe' Then The series ^2k€Zckek converges unconditionally in H, i.e. its terms can be arbitrarily permuted without affecting the convergence, if and only if {ck}k€Z g I2 (Z). 8 • Any x G H can be decomposed in a unique way according to x = ^2 ckek with {ck}k€Z G I2 {%) ■ fceZ • T is an isomorphism from I2 (Z) to H. • There exists a unique biorthogonal Riesz basis {ek}k€Z in H, i.e. {ek}k€Z is a Riesz basis and {ek, et)H = 5kj. This basis is defined by ek = (TT*)"1 ek, where T* denotes the adjoint mapping to T. • There exists constants 0 < c < C such that c \ \x\\h — ^ ] | (xi ek)h | ^ C ||x|\H Vx G H. fcGZ Further details can be found in [18]. The next theorem gives equivalent conditions for {efc}fcGZ to be a Riesz basis. Theorem 3. For a sequence {efc}fceZ spanning a Hilbert space H, the following conditions are equivalent: • {efc}fcez *s a Riesz basis for H. • The Gram matrix {(ek, e/)}fc /eZ defines a bounded, invertible operator on I2 (Z) . • {efc}fcez *s a Bessel sequence, and there exists a biorthogonal sequence {fk}k€Z which is also a Bessel sequence spanning H. The proof of this Theorem can be found in [15]. For completeness we provide also a definition of a Bessel sequence. Definition 4. A sequence {efc}fceZ in a separable Hilbert space H is called a Bessel sequence if there exists a constant C > 0 such that V{xfc} G I2 (Z). 9 1.2 Wavelets In this chapter, we consider H = L2 (R). A function

j,k, = 5i,j5k,i Vz, j, k, I G Z. The wavelet is called orthonormal if (^j,k, = Si:j5k,i Vz, j, k,l eZ. Example 6. The simplest example of orthonormal wavelet is the Haar wavelet. The Haar wavelet is the function defined on the real line as (1 VxG[0,i), H{x) = 1-1 Vx G [i, 1] , [ 0 otherwise. It is well-known [42, 43] that the system [2^2H{2°x — &)} -fcgZ is orthonormal in L2 (R). Wavelets are usually constructed with an assistance of a multiresolution analysis. Definition 7. A sequence {V^} .gZ of closed subspaces of L2 (R) is called a multiresolution analysis if it satisfies the following conditions: 1) The sequence is nested, i.e. Vj C Vj+1 Vj G z. 2) The spaces are related to each other by dyadic scaling, i.e. f(x)eVj^f(2x)eVj+1 VjgZ. 3) The union of the spaces is dense, i.e. \JV3=L2 (R). 4) The intersection of the spaces is reduced to the set containing only the null function, i.e. C\Vi = {0}. 10 5) There exists a scaling function x - k)}ki is a Riesz basis of V3 with Riesz bounds independent of j. 1.3 Biorthogonal wavelets Now, let have two different scaling functions (2x - n), ijj (x) = ^ gn(p (2x - n) \/x G R. (1.4) n£Z n£Z The function 0 is called a primal scaling function, the sequence {V^} -gZ is called a primal multiresolution analysis and ib is a primal wavelet, while d>, \ Vj\ , and ib are called dua/. I J 7GZ Let us define Wj = span {'0j)fc, A; G Z}, = span jV-^fc, k G z|. The following lemma describes basic properties of biorthogonal wavelets. Theorem 9. Let sequences {Vj}j€Z and j^jj. be two multiresolution analyses with mutually biorthogonal scaling functions 0 and 0 so that ^0 (x — k) , 0 (x — Z)^ = 5kj for all k,l G Z. Further let wavelet coefficients be defined by (1.3) and primal and dual wavelets be defined by (1-4). Then • ipix) G V\ and ipix) G V\. • ip is biorthogonal to ip, i.e. (ij){x- k),$(x-l)} = 6kti Vk,leZ. (1.5) (if; (x — k), (f> (x — l)^ = (^ijj (x — k), cf) (x — Z)^ = 5k,i V/€,/GZ. (1.6) • For any j G Z i/ie set {i/)j:k, k G Z} is a Riesz basis of Vj and for any J G Z the set |"0j,fc, k G zj is a Riesz basis ofVr • If moreover 0 and G R satisfy to| < c(i +^ < c(i + lei)-1, i/iera {i/}j,k} ■ and \ V^fc \ are Riesz bases of L? (R). For the proof of this theorem which relies on techniques based on the Fourier transform, we refer to [42]. The consequence of (1.5) and (1.6) is that the spaces Wj and W are orthogonal for all j ^ Z, the space Wj is orthogonal to Vi for all / < j and the space Wj is orthogonal to Vi for all I < j. Moreover Wj complements Vj in VJ+\ and similarly Wj complements Vj in VJ+\. Then the space Vj can be decomposed: Vj = VJ0 © Wj0 © Wj0+1... © Wj-! 12 and due to (1.5) any function / g Vj can be expanded into 3-1 f = S (/. fa*) j,k = (/> ho,*) j0,k + ^2^2(f> ^fe) V'j.fe. (i-7) fcez fcez j=jo feez The first part of the expansion (1.7) is called a singlescale representation of the function / while the second part of the expansion is called a multiresolution or multiscale representation of the function /. Many properties of wavelets can be formulated by equivalent or necessary conditions on its Fourier transform, on its symbols and its scaling coefficients. For instance, necessary conditions on symbols and scaling coefficient, which are useful for the construction of the dual scaling function or for the computation of scaling coefficients of orthonormal wavelets, are given in the following theorem proved in [18]. Theorem 10. If scaling functions ■ % 'j,k/(Pj,k, i',r ^--i'-"^ >j,k, fceZ '2 /T, fceZ and detail operators Q, : L2 (r) ->■ Q,- : L2 (M) ->■ by Since the spaces Vj are nested, we have PjPi = Pj for all j < I. Consequently the detail operator Q3 is also a projection on a space Wj and can be expanded into [18] fcez Then the space Wj can be also defined as the kernel of Pj in VJ+\. It is known from [33] that if 0 is a compactly supported L2-stable refinable function then there always exists a dual scaling function to h*) fa*) = fis, fe (f> h° ^) ■ 1.5 The Discrete Wavelet Transform For a computation with wavelets it is in the most cases more advantageous to work with a multiscale representation but in some case it is more efficient to work with a single scale representation (for example evaluation of scalar products with wavelets). Therefore we need an efficient tool which enables to change both representations easily. This tool is called the discrete wavelet transform (DWT). Its first part can be derived from the scaling equation (1.2) and the wavelet equation (1.4). We have from (1.2) 2j/2 {2?x -k)= 23'2 ^ hn4> {23+1x -2k-n) raGZ mGZ mGZ This implies that Cj,k — 2 ^2 hm-2kCj+l,m- (1-9) From (1.4) we obtain $3,k{x) = 2j/2ip {2?x -k)= 2J/2 Y 9n4> (2j+1x -2k-n) raGZ = 2-1'2 Y ~gm-2k2U+m4> (2j+1x -m)= 2-1'2 ^ 9m-2k4>3+i,m. It follows that dj,k = 2 ^2 9m-2kCj+l,m- (1-10) mGZ The equations (1.9) and (1.10) represent the decomposition algorithm. We can also reconstruct coefficients cJ+\^ from coefficients Cj:k and dj:k- From the relation Vj = V3-\ + Wj-i, it follows that ^2 cj,k4>j,k = ^2 cj-l,k4>j-l,k + ^2 dj-l,ki)j-l,k fcGZ fcGZ fcGZ _ 2 V2 ^2 Cj-l^k ^2 hn-2k4>j,k + 2 1^2 Y] dj-l,k Yl 9n-2k4>j,k- fcGZ nGZ fcGZ nGZ 15 By matching coefficients, we obtain the reconstruction algorithm: 'k—2nCj — l,n + 2-1/2^2gk_2nd (1.11) The reconstruction algorithm is the second half of the discrete wavelet transform. The first part of (1.11) can be also used to obtain an approximation (prediction) of the coefficients Cj:k from the data at coarser scale j — 1. In practice, we deal with functions with compact support. Then there exist k\ g Z, n g N such that Cj^ = 0 for k > k\ and k < k\ + n. In this case the discrete wavelet transform can be performed in Oin) operations. 1.6 Polynomial exactness The rate of decay of the approximation error of a function / defined by \\Pjf — f\\ is given by the polynomial exactness of the primal scaling basis and by the regularity of /. In the next theorem, equivalent conditions for the polynomial exactness are given. Theorem 12. Let 0, 0 g /^(R) be a compactly supported functions satisfying JR0(x) dx = 1. Then the following properties are equivalent: •

0 Vx £ (0,N+1). • The function B^ is symmetric with respect to the point ^y^-, i.e. BN (^P1 -xj =BN( + x ) ViGM. • JKBN (x) dx = 1. N+l fc=0 fc=0 v 7 where x+ = (max{0, x})N. The set {Bn(23x — k)}k(-z generates the multiresolution spaces v3 = {/gl2 (r) n cN-x (r): /l[^,*±i] e nw, vfc e zj Bn is L2-stable. 17 • Bn is a refinable function, i.e. it satisfies (1.2), and nonzero scaling coefficients are given by hn = 2-N(N+1^j Vn = 0,...N. The proof of statements of this theorem and other interesting properties of splines can be found in [4, 16, 18, 43]. Now, we can define the primal scaling function as N, such that N + N is even, there exists a compactly supported dual scaling function, which is exact of order N. 18 Chapter 2 Wavelets on the Bounded Interval Wavelets on the real line are not usually suitable in applications which are defined on bounded domains. Therefore it is necessary to adapt them first on the bounded interval. The main idea is to retain most of the inner functions, i.e. the scaling functions and wavelets whose supports is contained in the interval, and to treat boundary scaling functions and wavelets separately. In some cases it is possible to take restrictions of some of the overlapping functions but in the most cases it is necessary to construct so called boundary functions. During their construction the important properties of wavelets should be preserved such as a Riesz basis property, a smoothness, a local support of basis functions and a polynomial exactness of the wavelet basis. The main disadvantage of some existing constructions is a large condition number of wavelet bases resulting in a bad numerical stability and bad spectral properties of the corresponding stiffness matrices when solving differential equations numerically. This chapter provides an introduction to wavelets on the bounded interval and unlike the previous chapter we consider here wavelet systems generated by many wavelets and by many scaling functions. Wavelets can be even different at different decomposition levels. All these facts complicate not only notation but also a theory. 2.1 Wavelet Basis We start with a definition of a wavelet basis. We consider here families \I> = A G J} C L2(0,1) of functions where J is an infinite index set and J = J<$, U J7$, where J7$ is a finite set representing scaling functions living on the coarsest scale. Any index A G J is of the form A = (j, k), where |A| = j denotes a scale and k denotes spatial location. The above notation enables us to write wavelet expansions as 19 Further, we will use the following shorthand notations for two collections of functions ^, § G L2(0,1): := lib, ib Thus, the biorthogonality condition can be written as Definition 16. The family \I> = {ifj\, A G J} C L2(0,1) is called a wavelet basis of Hs for some 7, 7 > 0 and s G (—7, 7), if • \I> normalized in is a Riesz basis of Hs; it means that \I> forms a basis of and there exist constants cs, Cs > 0 such that for all b = {b\}X€j G /2 (J7") holds °s \\b\\p(j) < IIV'aIIh- < C„ llbl where supcs, inf Cs are called Riesz bounds and cond := infCs sup cs is called the condition number of The functions are local in the sense that diam (supp-0^) < 2~IAI VA G J. Functions A G J^, have cancellation properties of order m, i.e., v{x) i/)\(x) dx < 2_mlAl lffm(0,l) Vt> G #m (0,1). It means that integration against wavelets eliminates smooth parts of functions. It is equivalent with vanishing wavelet moments of order m and with the polynomial exactness of dual multiresolution analysis of order m — 1. The wavelet system \I> is usually constructed with the assistance of a multiresolution analysis. Definition 17. A sequence V = {Vj}-gN. of closed linear subspaces Vj C Hs is called a multiresolution or multiscale analysis, if the subspaces are nested, i.e., l/J0cVc..c^c^c...cF and is dense in H, i.e. -h3 UjGN, K- =HS. 20 We now assume that Vj is spanned by set of scaling functions := {fa^kelj}, where Xj is a finite index set. Furthermore, the collections will always be assumed to be uniformly stable, uniformly bounded and uniformly local in the sense that V/c G Xj and Vx G (0,1) diam (supp^-fc) < T3 and # {k G Xj, B(x, 2~j) n supp<^-fc ^ 0} < 1, where B(x, 2~3) is the ball with radius 2~3 centered at x. The nestedness of V and the uniform stability of the Riesz bases imply the existence of a bounded linear operator M, n = (mi'?) such that Viewing $j as a column vector, above refinement relations can be expressed in a matrix form as = Mjfi^+1. (2.1) As a consequence of uniform locality, the matrices M^o are uniformly sparse i.e. the number of entries per each row and column is uniformly bounded. Similarly as in the previous chapter, the nestedness of V further implies the existence of the complement spaces Wj. Let ■= {ipj,k, k G Jj} , Jj := Xj+1 \Xj, j > j0, be a Riesz basis of Wr Functions in ^ are called wavelets. Since ^ C VJ+i and forms a Riesz basis of its span, we have a unique representation which can be again expressed in a matrix form as Vj = (2.2) where M,-1 is a bounded linear operator given by M,-i = (mfl) . Further, we assume that collection ^ is uniformly local and then M^i is also uniformly sparse. The refinement relations (2.1) and (2.2) lead to refinement equations in a matrix form with a refinement matrix Mj := (M^o, M^i). Matrices 1VL, are invertible and let inverse matrices be defined by 21 Inverses of sparse matrices are not in the general case sparse. However, when we require uniformly local dual wavelets then the inverses of these matrices have to be uniformly sparse. In this case, wavelets are usually constructed by a method of stable completion proposed in [6]. Definition 18. Any M^i G [I2 (J3), I2 (Zj+i)] is called a stable completion of M^o, if k(Mj), k(Mj1) = 0(1), j^oo, where Mj := (Mji0, M^i). It is known that U ^ is uniformly stable if and only if M^i is a stable completion of M,-,o, see [6]. However, it does not imply the Riesz stability over all levels. 2.2 Multiscale Transform The multiscale basis of Vj is given by = *,. U U (2-3) 3=30 Since the union of subspaces Vj is dense in Hs, a multiscale basis of Hs is given by oo j-l 3=30 and we can split J into two index sets J* :={(jo-^,k),ke X3} , := {{j, k),j> j0, k G J3} . From (2.3) it follows that any v G Vj has a single-scale representation v = cTj$> = Y^ chk(f>hk, as well as a multiscale representation j-i v = cl®3o + dJo*;o + • • • + dJ-i^j-l = Yl cio,kio,k + EE d^3-k- k€lj0 3=30 k£jj The corresponding vectors of the single-scale and multiscale representations are related by the multiscale transformation Tj : I2 {Xj) —> I2 (Ij): cj = Tj (cj,dj,...dj_1)r. 22 From refinement relations (2.1) and (2.2), it follows that cj^ + d;'\l/; = (MjflCj + ,.: = <.•,. : and then the multiscale transform Tj is given by: T/ ''"./../ :-..T/.,.. where T,; I ^ J. To determine the inverse multiscale transform Tj1, note that Thus, the inverse multiscale transform Tj1 can be obtained by applying inverses of the matrices Tjj in the opposite order: T,; T,;. ...T,.- ;. where Tj] = If refinement matrices 1VL, and G0 are uniformly sparse then both the multiscale transform Tj and the inverse multiscale transform T}"1 can be performed in O (Nj) operations, where Nj is the dimension of the space Vr The next theorem shows a relation between properties of the multiscale basis \I> and the multiscale transform Tj. Theorem 19. Assume that are uniformly stable. Then Tj are well-conditioned or stable in the sense of k(Tj), /{(Tj1) = O (1) if and only if ^ is a Riesz basis in a Hilbert space H. For further details, we refer to [23]. 2.3 Riesz Bases in Sobolev Spaces As was already mentioned in the previous chapter, any wavelet compression algorithm based on removing small coefficients can be reasonable only when wavelets form a Riesz basis. The following theorem from [40] gives useful characterization of Riesz bases. Theorem 20. Let jo be the coarsest level and let Vj0 C Vj0+1 G...GH, VjoG Vjo+1 G...GH be sequences of closed subspaces of H such that with dimVj = dimVj, then the following statements are equivalent: • There exist uniform Riesz bases and for V3 and V3 such that is invertible and the inverses are uniformly bounded. 23 inr mr sup > 0. 3€Xo(#v€VJO+jOj:veVJO+j I Ml \\v\\ ~ ± There exist unique uniformly bounded projections Pj : H —>■ Vj with Im(7 — Pj) = Vj and these projections are given by I'r'- ('••/) 'I'/- • To any uniform Riesz basis for Vj there exist a unique uniform biorthogonal Riesz basis in Vr Let any of the above conditions be satisfied and moreover let the following minimum angle condition hold I (w, v) I sup cos Z(Vj0+j, Wj0+j) < 1 where cos /.(Vj, Wj) := sup -— , jGN0 0^v€Vj,0^w€Wj \ \w\\ \\v\\ then (I — Pj)\wj '■ W0 —> V0+\ Pi is invertible and the inverses are uniformly bounded. The first part of the previous theorem enables to formulate prior results from [25] without explicit knowledge of some biorthogonal bases while the second part was used in [40] to a construction of biorthogonal wavelets on non-uniform meshes. In this construction both primal and dual wavelets are known in explicit form, have a compact support and are piecewise polynomials. The following two theorems state how Riesz bases for a range of Sobolev spaces can be created. The first theorem describes the case, when we have two mutually biorthogonal bases, while the second one describes the case, when a dual biorthogonal basis in not known. Theorem 21. Let jo be the coarsest level and let Vj0 C Vj0+1 C ... C L2(0,1), Vj0 C Vj0+1 C ... C L2(0,1) be sequences of primal and dual spaces which are mutually biorthogonal and which are equipped uniform L2(0,1)—Riesz bases $j and $j for V0 and Vj, respectively. In addition, for some 0 < 7 < d, let inf \\v - ^||L2(0,i) < 2-''d|M|H«(o,i) V« G Hd(0,1), Vj G Vj (Jackson or direct estimate) and 11^11^(0,1) ~ 2JS||^||L2(0>1) Vvj G Vj, s G [0,7), (Bernstein or inverse estimate) and let similar estimates be valid at the dual side with Vj, d, 7, Hs(0,1) reading as Vj, d, 7, Hs(0, 1). And let ^>0 be uniform L2(0,1)—Riesz bases for Wj := Vj+i Pi Vj±L (0,1\ then for s G (—7,7) the collection jGN0 is a Riesz basis for Hs(0, 1), where Hs(0,1) := (H~s(0, 1))' for s < 0. 24 This theorem is a consequence of results from [25, 40]. The following theorem from [29] summarizes results from [23, 25]: Theorem 22. Let j0 be the coarsest level and let Vj0 C Vj0+1 C ... C L2(0,1), Vj0 C Vj0+1 C ... C L2(0,1) be sequences of primal and dual spaces with dim Vj = dim Vj such that for uniform L2(0, 1)—Riesz bases <&j and <&j for Vj and Vj, respectively, \ v 31 I? (0,1) exists with a uniformly bounded spectral norm. In addition, for some 0 < 7 < d, let inf \\v - ^||L2(0,i) < 2-^||«||^(o,i) Vv G Ud(0,1), Vj G Vj (Jackson or direct estimate) and (Bernstein or inverse estimate) 11^11^(0,1) ^ 2JS||^||L2(0>i) Vvj G Vj, s G [0,7), where, for s G [0, d], Hs(0,1) = [L2(0,1), Hd(0,1) n H%(0, l)]a/d , and let similar estimates be valid at the dual side with Vj, d, 7, Hs(0,1) reading as Vj, d, 7, Hs(0,1). v4n V0 and 0 < /i < 7 such that I\Pm ■ ■ ■ Pn-i 11 < 2^n~m) Vm, n G N with j0 < m < n. And let ^>0 be uniform L2(0,1)—Riesz bases for W0 := Keri^, then for s G (^,7) the collection jeN0 is a Riesz basis for Hs(0, 1). Some sufficient conditions for to be a Bessel sequence are given in [35]. 2.4 An Application of Riesz Basis Property We show here that condition numbers of stiffness matrices arising from discretization of elliptic partial differential equations by wavelets depend on Riesz constants of a wavelet basis. Therefore it is necessary construct wavelet bases which are well-conditioned in the sense that their Riesz condition number is as small as possible. We consider here the following Dirichlet problem d Pft u ~ V tt4 = / m n = (0, l)d with u = 0 on dn (2.4) ^—f oxf 1=1 1 for given / G H~x (tt). A Riesz wavelet basis for Hq (tt) can be constructed by a tensor product of univariate Riesz wavelet bases. Indeed, let \I> = {ifj\, A G J} be after appropriate normalization a Riesz wavelet basis for spaces L2(0,1) and Hq(0, 1) then yJ=l'^Amllff1(Sl) is a Riesz basis for Hq (tt) (see [31]) with the Riesz constants (see [28]) 2 < max min(c0,ci)cQ 1 ||b||22^ < (Cq,Ci)Cq 1\\b\\p^jd^ (2.5) Vb G I2 , where constants cq, Cq, ci, C\ are Riesz constants with respect to spaces L2 and Hi, respectively, and the index set Jd is defined by Jd := {A = (Ai,..., A^), Aj G J} = uT* := ^ uxil>x and f = (f(t/jx))\€jd, Writing u 26 then an equivalent formulation of (2.4) is Au with A = D"1/2 (M(g)...(g)M + S(g>...(g>M + -- - + M(g)...(g)S) D"1/2, where D = diag <8>^=1'i/'. 0d , and S=(/1^^^) and M=[l^dx '0 OX OX / \^€J \Jo / \,n€J are the one-dimensional stiffness and the mass matrices, respectively. Then (2.5) implies , . A. max (C0, Ci) Ct1 cond(A) <-v 01 ; ° . mm (c0,ci)c0 In general case, let us assume, that we have the following variational problem: for given /GH' find u G T~L such that a{u,v) = f{v) \/v G H, (2.6) where H is a Hilbert space and a is a continuous bilinear form. Then, we define the operator A : T~L —> H' by A(u)(v) = a(u,v) \/v G H, and then (2.6) is equivalent to A(u) = f. If a is H—elliptic, then there exist positive constants cA, C4 such that ca\\v\\h < \\A(v)\\w N. • Smoothness. Certain smoothness for primal and dual wavelet basis functions. • Closed form. Primal scaling functions and wavelets are known in the closed form. • Well-conditioned bases. Constructed wavelet bases have improved condition numbers in comparison with previous constructions of the same type. The primal scaling functions are B-splines, which have been used also in [37]. Then we constructed a dual multiresolution analysis which is generated by three types of scaling functions. Inner scaling functions are the same as in [21] and there are two types of boundary scaling functions. Scaling functions of the first type are defined to preserve the prescribed polynomial exactness in the same way as in [22]. Scaling functions of the second type are constructed to be as similar as possible to restrictions of inner scaling functions. Consequently we computed refinement matrices and constructed wavelets by a method of stable completion. The construction of initial stable completion is along the lines of [24]. Furthermore, we showed that the constructed set of functions are indeed a Riesz basis for the space L2 (0,1) and for the Sobolev space Hs (0,1) for a certain range of s. Finally, we adapted primal bases to homogeneous Dirichlet boundary conditions of the first order and we compared quantitative properties of the constructed bases and the efficiency of an adaptive wavelet scheme for several spline wavelet bases to demonstrate a superiority of our construction. Numerical examples were presented for one-dimensional and two-dimensional Poisson equations where the solution has a steep gradient. 3.3 Cubic Spline Wavelets with Complementary Boundary Conditions In the paper "Cubic Spline Wavelets with Complementary Boundary Conditions" [8], we constructed a new stable cubic spline wavelet basis on the interval satisfying complementary boundary conditions of the second order i.e. the primal wavelet basis is adapted to 30 homogeneous Dirichlet boundary conditions of the second order, while the dual wavelet basis preserves the full degree of polynomial exactness. Primal wavelets have six vanishing moments. Moreover, we proposed further decomposition of the scaling basis at the coarsest level. We decomposed the scaling basis $4 into the scaling basis $3 and the wavelet basis ^3. These new wavelets from ^3 have four vanishing moments while supports of new boundary scaling functions from $3 overlap in contrast to boundary scaling functions from $4. This modification leads to improved Riesz condition numbers of the proposed basis. The primal scaling functions are B-splines satisfying homogeneous Dirichlet boundary conditions of the second order. Then in the similar way as in [7], we constructed a dual mul-tiresolution analysis which is generated by three types of scaling functions. Inner scaling functions are the same as in [21] and there are two types of boundary scaling functions. Scaling functions of the first type are defined to preserve the prescribed polynomial exactness while scaling functions of the second type are constructed to be as similar as possible to restrictions of inner scaling functions. Consequently we computed refinement matrices and constructed wavelets by a method of stable completion. We proposed a new construction of the initial stable completion because the standard construction from [24] led to singular matrices. Finally, we presented quantitative properties of the proposed basis and we compared them with some other cubic spline wavelet bases to show superiority of our construction. Numerical examples were presented for the two-dimensional biharmonic equation where the solution has a steep gradient. 3.4 Wavelet Basis of Cubic Splines on the Hypercube Satisfying Homogeneous Boundary Conditions In the paper "Wavelet Basis of Cubic Splines on the Hypercube Satisfying Homogeneous Boundary Conditions" [12], we constructed new cubic spline wavelet basis on the hypercube that is well-conditioned, adapted to homogeneous Dirichlet boundary conditions and the wavelets have two vanishing moments. Proposed wavelets have the same properties as wavelets in the construction [7] with one exception. We do not require compact support for dual functions which enables to construct primal functions with better properties. Dual functions are not in fact used in some applications of wavelets such as numerical solution of linear differential equations. The advantage of our construction in comparison with similar cubic spline wavelets with local dual functions [7, 8, 24, 37] is that the support of wavelets is shorter, Riesz condition numbers are smaller and another advantage is also a simple construction. Then stiffness matrices arising from discretization of elliptic problems using proposed wavelets have uniformly bounded condition numbers and these condition numbers are small. It leads in combination with shorter support to more efficient numerical solvers. The primal scaling functions are B-splines, which have been used also in [7]. Then we constructed a primal wavelet basis generated by one inner and two boundary wavelets. Inner wavelets are generated by a single function supported in the interval [0, 5] and there 31 are at each side two boundary wavelets. The first one is supported in the interval [0,4] and the second one is supported in the interval [0, 3]. All three types of wavelet are constructed to be orthogonal to continuous piecewise linear functions which are linear on pieces [|, -^p-] for k G N. A space generated by these continuous piecewise linear functions forms a dual multiresolution space which is consequently used in the proof of the Riesz basis property. Moreover from the construction immediately follows that constructed wavelets have two vanishing wavelet moments. Finally, we presented quantitative properties of the constructed basis and we also provided a numerical example to show an efficiency of Galerkin method using constructed basis. 3.5 On a Sparse Representation of a n-dimensional Laplacian in Wavelet Coordinates A general concept for solving of operator equations by means of wavelets was proposed by A. Cohen, W. Dahmen and R. DeVore in [19, 20]. It consists of the following steps: transformation of the variational formulation into the well-conditioned infinite-dimensional problem in the space I2, finding of the convergent iteration process for the I2— problem and finally a derivation of its computable version. The aim is to find an approximation of the unknown solution u which should correspond to the best iV-term approximation, and the associated computational work should be proportional to the number of unknowns. Essential components to achieve this goal are well-conditioned wavelet stiffness matrices and an efficient approximate multiplication of quasi-sparse wavelet stiffness matrices with vectors. In [19], authors exploited an off-diagonal decay of entries of the wavelet stiffness matrices and designed a numerical routine APPLY which approximates the exact matrix-vector product with the desired tolerance e and that has linear computational complexity, up to sorting operations. The idea of APPLY is following: To truncate A in scale by zeroing al:J whenever > k (5 represents the level difference of two functions in the wavelet expansion) and denote resulting matrix by Ak- At the same time to sort vector entries v with respect to the size of their absolute values. One obtains Vk by retaining 2k biggest coefficients in absolute values of v and setting all other equal to zero. The maximum value of k should be determined to reach a desired accuracy of approximation. Then one computes an approximation of Av by w := Akv0 + Ak_i(vi - v0) + ... + A0(vk - vk_i) (3.1) with the aim to balance both accuracy and computational complexity at the same time. Improvements of this scheme were proposed in [9, 28, 39]. Although the APPLY routine has optimal computational complexity, its application is relatively time consuming and moreover it is not easy to implement it efficiently. In the paper "On a Sparse Representation of a n-dimensional Laplacian in Wavelet Coordinates" [13], we constructed a wavelet basis based on Hermite cubic splines with respect 32 to which both the mass matrix and the stiffness matrix corresponding to one dimensional Poisson equation are sparse. This means that the number of nonzero elements in any column is bounded independently of matrix size while stiffness matrices in wavelet coordinates are usually only quasi sparse. Then, matrix-vector multiplication can be performed exactly with linear complexity for any second order PDEs with constant coefficients. Moreover, the proposed basis is very well-conditioned for low decomposition levels. Small condition numbers for low decomposition levels and a sparse structure of stiffness matrices are kept for any second order PDEs with constant coefficients, which are well-conditioned in the sense of (2.7), and moreover they are independent of the space dimension. Wavelets with similar properties were already proposed in [29]. Our wavelets generate the same multires-olution spaces as wavelets from [29] but have improved condition numbers. In comparison with wavelets from [29], we constructed two new wavelets (the first two wavelets are the same) and we also modified boundary scaling functions at the coarsest level as well as wavelets at the coarsest level. Our construction proceeded in this way. First, we constructed four wavelets in such a way that wavelets from the space Wn+\ are orthogonal to the scaling functions from the space Vn for n > 1. This property ensures that both the mass and stiffness matrices corresponding to the one-dimensional Laplacian have at most three wavelet blocks of nonzero elements in any column and, consequently, the number of nonzero elements in any column is bounded independently of matrix size. The first two wavelets have supports in [—1,1]. They are uniquely determined by their orthogonality to cubic polynomials and by imposing that the first one is odd and the second one is even. The other two wavelets have supports in [—2, 2]. We impose on them the above orthogonality condition again, which will be ensured by requiring that they are orthogonal to cubic polynomials on intervals [—2,0] and [0,2], respectively. Again, the first of them should be odd, and the second one even. There remains several free parameters. To obtain a more sparse stiffness matrix and a better conditioned wavelet basis, we use these free parameters to prescribe the orthogonality of the first derivative of constructed wavelets to the first derivative of the first two wavelets. In the next step, we modified boundary scaling functions at the coarsest level and also wavelets at the coarsest level to further improve condition numbers of the constructed wavelet basis and to preserve or improve a sparse structure of the stiffness matrix corresponding to the one-dimensional Laplacian, and a sparser structure of the mass matrix, respectively. A span of these new functions will be the same as the span of the original functions. In [13], we proved that the constructed basis is a Riesz basis and computed condition numbers for model problems and compared them with condition numbers for a similar wavelet basis proposed in [29]. 33 Bibliography [I] Beylkin, G.; Coifman, R. R.; Rokhlin, V.: Fast wavelet transforms and numerical algorithms I, Commun. Pure Appl. Math. 44, (1991), pp. 141-183. [2] Bittner, K.: On the stability of compactly supported biorthogonal spline wavelets, Approximation Theory XII, San Antonio, (2007), pp. 38-49. [3] Bramble, J. H.; Cohen, A.; Dahmen, W.: Multiscale Problems and Methods in Numerical Simulations, Springer-Verlag Berlin Heidelberg, 2003. [4] De Boor, C: A Practical Guide to Splines, Springer Verlag, Berlin, 1978. [5] Burrus, C.S.; Odegard, J. E.: Coiflet Systems and Zero Moments, IEEE Transactions on Signal Processing 46(3), (1998), pp. 761-766. [6] Carnicer, J.M.; Dahmen, W.; Peňa, J.M.: Local decomposition of refinable spaces, Appl. Comp. Harm. Anal. 6, (1999), pp. 1-52. [7] Černá, D.; Finěk, V.: Construction of optimally conditioned cubic spline wavelets on the interval, Adv. Comput. Math. 34(2), (2011), pp. 219-252. [8] Černá, D.; Finěk, V.: Cubic Spline Wavelets with Complementary Boundary Conditions, Appl. Math. Comput. 219, (2012), pp. 1853-1865. [9] Černá, D.; Finěk, V.: Approximate Multiplication in Adaptive Wavelet Methods, Cent. Eur. J. Math. 11, (2013), pp. 972-983. [10] Černá, D.; Finěk, V.: Quadratic Spline Wavelets with Short Support for Fourth-Order Problems, Result. Math. 66, (2014), pp. 525-540. [II] Černá, D.; Finěk, V.: Cubic Spline Wavelets with Short Support for Fourth-Order Problems, Appl. Math. Comput. 243, (2014), pp. 44-56. [12] Černá, D.; Finěk, V.: Wavelet basis of cubic splines on the hypercube satisfying homogeneous boundary conditions, Int. J. Wavelets Multi. 13(3), (2015), pp. 1550014/1-21. [13] Černá, D.; Finěk, V.: On a sparse representation of a n-dimensional Laplacian in wavelet coordinates, Result. Math., DOI 10.1007/s00025-015-0488-5, (2015). 34 [14] Černá, D.; Finěk, V.; Najzar, K.: On the exact values of coefficients of Coiflets, Cent. Eur. J. Math. 6(1), (2008), pp. 159-170. [15] Christensen, O.: An Introduction to Frames and Riesz Bases, Applied and Numerical Harmonic Analysis, Birkhäuser, Boston, 2003. [16] Chui, C.K.: An Introduction to Wavelets, Academic Press, Boston, 1992. [17] Ciarlet, P.: Finite Element Method for Elliptic Problems, Society for Industrial and Applied Mathematics. Philadelphia, PA, USA (2002). [18] Cohen, A.: Numerical Analysis of Wavelet methods, Studies in Mathematics and its Applications 32, Elsevier, Amsterdam, 2003. [19] Cohen, A.; Dahmen, W.; DeVore, R.: Adaptive Wavelet Schemes for Elliptic Operator Equations - Convergence Rates, Math. Comput. 70, (2001), pp. 27-75. [20] Cohen, A.; Dahmen, W.; DeVore, R.: Adaptive Wavelet Methods II - Beyond the elliptic case. Found. Math. 2, (2002), pp. 203-245. [21] Cohen, A.; Daubechies, I.; Feauveau, J.-C: Biorthogonal Bases of Compactly Supported Wavelets, Comm. Pure and Appl. Math. 45, (1992), pp. 485-560. [22] Cohen, A.; Daubechies, I.; Vial, P.: Wavelets on the Interval and Fast Wavelet Transforms, Appl. Comp. Harm. Anal. 1, (1993), pp. 54-81. [23] Dahmen, W.: Stability of Multiscale Transformations, J. Fourier Anal. Appl. 4, (1996), pp. 341-362. [24] Dahmen, W.; Kunoth, A.; Urban, K.: Biorthogonal Spline Wavelets on the Interval -Stability and Moment Conditions, Appl. Comp. Harm. Anal. 6, (1999), pp. 132-196. [25] Dahmen, W.; Stevenson, R.: Element-by-Element Construction of Wavelets Satisfying Stability and Moment Conditions, SIAM J. Numer. Anal. 37, (1999), pp. 319-352. [26] Daubechies, I.: Ten Lectures on Wavelets, SIAM Publ., Philadelphia, 1992. [27] Daubechies, I.: Orthonormal bases of compactly supported wavelets II, Variations on a theme, SIAM J. Math. Anal. 24(2), (1993), pp. 499-519. [28] Dijkema, T. J.; Schwab, Ch.; Stevenson, R.: An adaptive wavelet method for solving high-dimensional elliptic PDEs, Constr. Approx. 30, pp. 423-455 (2009). [29] Dijkema, T. J.; Stevenson, R.: A sparse Laplacian in tensor product wavelet coordinates, Numer. Math. 115, pp. 433-449 (2010). [30] Eirola, T.: Sobolev characterization of compactly supported wavelets, SIAM J. Math. Anal. 23, (1992), pp. 1015-1030. 35 [31] Griebel, M.; Oswald, P.: Tensor product type subspace splittings and multilevel iterative methods for anisotropic problems, Adv. Comput. Math. 4, pp. 171-206 (1995). [32] Lawton, W.M.: Necessary and sufficient conditions for constructing orthonormal wavelet bases, J. Math. Phys. 32(1), (1991), pp. 57-61. [33] Lemarie, P.G.: On the Existence of Compactly Supported Dual Wavelets, Appl. Comp. Harm. Anal. 3, (1997), pp. 117-118. [34] Monzon, L.; Beylkin, G.; Hereman, W.: Compactly supported wavelets based on almost interpolating and nearly linear phase filters (coiflets), Appl. Comp. Harm. Anal. 7, (1999), pp. 184-210. [35] Jia, R.Q.: Bessel sequences in Sobolev space, Appl. Comp. Harm. Anal. 20, (2006), pp. 298-311. [36] Jia, R.Q.; Zhao, W.: Riesz bases of wavelets and applications to numerical solutions of elliptic equations, Math. Comput. 80, pp. 1525-1556 (2011). [37] Primbs, M.: New stable biorthogonal spline wavelets on the interval. Result. Math. 57, pp. 121-162 (2010). [38] Ron A.; Shen, Z.: Sobolev regularity of refinable functions, Journal of Approximation Theory 106(2), (2000), pp. 185-225. [39] Stevenson, R.: Adaptive solution of operator equations using wavelet frames, SIAM J. Numer. Anal. 41, (2003), pp. 1074-1100. [40] Stevenson, R.: Locally supported, piecewise polynomial biorthogonal wavelets on nonuniform meshes, Constr. Approx. 19(4), (2003), pp. 477-508. [41] Villemoes, L.F.: Energy moments in time and frequency for two-scale difference equation solutions and wavelets, SIAM J. Math. Anal. 23, (1992), pp. 1519-1543. [42] Walnut D.F.: An Introduction to Wavelet Theory, Applied and Numerical Harmonic Analysis, Birkhauser, Boston, 2002. [43] Wojtaszczyk, P.: A Mathematical Introduction to Wavelets, Cambridge University Press, 1997. 36 CESJ 1 (2003) 1-15 Central European Science Journals On the exact values of coefficients of coiflets Dana Černá *12, Václav Finěk t1, Karel Najzar 1 Department of Mathematics and Didactics of Mathematics, Technical University of Liberec, Hálkova 6, Liberec 1, 4-61 17, Czech Republic 2 Department of Numerical Mathematics, Charles University, Prague Ke Karlovu 3, Prague 2, 121 16, Czech Republic Abstract: In 1989, R. Coifman suggested the design of orthonormal wavelet systems with vanishing moments for both the scaling and the wavelet functions. They were first constructed by I. Daubechies [16, 15] and she named them coiflets. In this paper, we propose a system of necessary conditions which is redundant free and more simple than the known system due to elimination of some quadratic conditions, thus a construction of coiflets is simplified and enables us to find the exact values of the scaling coefficients of coiflets up to length 8 and two further with length 12. Furthermore for scaling coefficients of coiflets up to length 14 we obtain two quadratic equations, which can be transformed to polynomial of degree 4 and there is an algebraic formula to solve them. © Central European Science Journals. All rights reserved. Keywords: orthonormal wavelet, coiflet, exact value of filter coefficients MSG (2000): 65T60 1 Introduction Approximation properties of multiresolution analysis and the smoothness of wavelet and the scaling function depend on the number of vanishing wavelet moments. In [14] Daubechies constructed orthonormal wavelets with arbitrary number A of vanishing wavelet moments and the minimal length of support 2A — 1. The filter coefficients were computed there by an analytical method and exact values could be found only for * E-mail: dana.cerna@tul.cz t E-mail: vaclav.finek@tul.cz * E-mail: knaj@karlin.mff.cuni.cz 2 D. Černá, V. Finěk / Central European Science Journals 1 (2003) 1-15 filters up to length 6. In [26] Shann and Yen calculated the exact values of filter coefficients of Daubechies wavelets of length 8 and 10. Other approaches for constructing Daubechies wavelets which enables to find exact values of some coefficients can be found in [9, 10, 23, 24]. In addition to the orthogonality, compact support and vanishing wavelet moments, Coifman has suggested that also requiring vanishing scaling moments has some advantages. In practical applications these wavelets are useful due to their 'nearly linear phase' and 'almost interpolating property', see [22]. Daubechies created comets by setting an equal number N of vanishing wavelet moments and vanishing scaling moments for even N and the length of support 3N, see [16, 15]. It was noticed in [4] that these comets has one additional vanishing scaling moment than is imposed. Tian constructed comets with N vanishing moments for odd N and the length of support 3N — 1 in [27, 29]. Burrus and Odegard constructed coiflets with N vanishing moments for odd N and the length of support 3N + 1 which has two additional vanishing scaling moments, see [7]. In this paper the computation of exact values of filter coefficients of coiflets up to filter length 14 is presented. There exist a number of coiflet filter design methods, such as Newton's method [16, 25] or iterative numerical optimization [7]. These methods enable to derive one particular solution for each system and the convergence and the obtained solution depends on the initial starting point, thus it is difficult to find all possible solutions. Moreover, the coefficients for length greater than 16 are given with less precision due to the roundoff error [15]. As an alternative one can use Grobner basis method [1, 6, 21]. This method is geared toward solving a polynomial system of equations with finite solutions. The idea consists of finding a new set of equations equivalent to the original set, which can be solved more easily. The advantage of such an approach is that solutions can be computed to arbitrary precision and that in some cases it gives all possible solutions for a given system of polynomial equations. In this paper we derive a redundant free and simplified system of equations and then aplly Grobner basis method. By this approach we are able to find some exact values of filter coefficients and to find all possible solutions for filters up to length 20. 2 Preliminaries The scaling function 0, which generates a coiflet, is constructed as the solution of scaling equation where scaling coefficients {h^} are determined so that the corresponding scaling functions and wavelets have required properties. D. Černá, V. Finěk / Central European Science Journals 1 (2003) 1-15 3 Definition 2.1. An orthonormal wavelet tp with compact support is called a comet of order N, if the following conditions are satisfied: /OO xntp (x) dx = 0 for n = 0,... N - 1, -oo /OO xn(f) (x) dx — 5n for n — 0,... N — 1, -oo where (p is scaling function corresponding to tp and 5n is Kronecker delta, i.e. 5q — 1 and 5n = 0 for n ^ 0. Since also a length of support plays a role, it is common to consider a wavelet satisfying i) and ii) which has the minimal length of support. The existence of coiflet for an arbitrary order N is still an open question. We rewrite this definition in terms of filter coefficients \hk~\- It is known that for orthonormal wavelet with compact support a number of filter coefficients is even number, we denote it by 2m. Lemma 2.2. Let {hk}^lN be the real coefficients, N2 — N\+2m — 1. If the orthonormal wavelet corresponding to the scaling function (fi(-) — 2 ^2^1 N (f>(2 • —k) is a coiflet of order N, then the following three conditions are satisfied: ^2-^1-2™ i) 5m = 2 ^2 hNl+jhNl+2m+j for 0 < m < M - 1, N2 ii) Y hkkn = 5n for 0 < n < N - 1, k=Ni N2 Hi) {-^fhkkn = 0 for 0 < n < N - 1. fc=ATl Condition i) is necessary but not sufficient for wavelet to be orthonormal. Conditions ii) and Hi) are equivalent to vanishing wavelet and vanishing scaling function moments, respectively. In summary, conditions in Lemma 2.2 are only necessary. It is known that they are not sufficient to generate a coiflet system. There exist functions given by (1) with filter coefficients satisfying i) — Hi) from Lemma 2.2 which are very rough. Hence after finding coefficients satisfying i) — in) orthonormality should be verified, for example using Cohen [11] or Lawton [20] condition. There are typically more than one wavelet satisfying these conditions and some of them, despite zero wavelet moments, are very rough. Likewise, in spite of zero scaling function moments, some are not at all symmetric. In practical applications the most regular wavelet or the wavelet with the most symetrical scaling function is typically chosen. 3 Construction It is well known that coiflets have more vanishing scaling moments than required in above definition. This was first noted by G. Beylkin at al. in [4]. In this paper, we derive 4 D. Černá, V. Finěk / Central European Science Journals 1 (2003) 1-15 redundant free and simpler definition of coiflets. The key component of our approach is formed by the following Theorem: Theorem 3.1. Let N2 = iVi + 2M - 1 then N2-2m 5m = 2 ^2 h3hJ+2m for 0 < m < M - 1 (2) is equivalent to 2 where 1 2" Í2n\ ö6n = Y( ■ (-l)'(aia2„_ť + 6ť62n-i) for 0 < n < M - 1, (3) m-l m-l fc=0 fc=0 ^ (iVi + 2k)lhNl+2k and 6S = ^ (JVi + 2k + l)ť^1+2fc+1. (4) Proof. Since the condition (2) is equivalent to condition \m(bS) |2 + \m(oj + vr) |2 = 1, (5) where w2 to (uS) — 'S^2 hke -ikuj k=Ni we can repeat the proof of Theorem 3.1 in [19] with some obvious changes. □ Due to Theorem 3.1 we are now able to impose necessary conditions on filter coefficients to generate a coiflet which are equivalent to conditions from Lemma 2.2 and the arising system is without redundant conditions. Corollary 3.2. Let {hk}^lN be the real coefficients, ^2 = ^1 + 2M — 1 and let at and bi be defined by (4). Then conditions i) — Hi) from Lemma 2.2 are equivalent to the following conditions: 2« /2n\ i*) 0 = J2 ( " ) (-l)sKa2n-s + &i&2n-i) for N < n < M - 1, in*) an — bn — 0 for 1 < n < N — 1, it;*) a2„ + b2n = 0 for N <2n<2N - 2. D. Černá, V. Finěk / Central European Science Journals 1 (2003) 1-15 5 Proof. It is clear that ii) and Hi) are equivalent to ii*) and in*). The rest follows from Theorem 3.1. □ The consequence of this Corollary is that the minimal length of support of comet of order N is 3iV for even N and 3iV — 1 for odd N and that some coiflets have more vanishing moments than is imposed. Thus, we have three classes of coiflets, see Table 1. Table 1 The length of filter 2M, the number of vanishing scaling and wavelet moments for coiflet of order N N 2M number of vanishing number of vanishing scaling moments wavelet moments set actual set actual even 3N N N+l N N odd 3N-1 N N N N odd 3N+1 N+l N+2 N N Now we further simplify the system by replacing some quadratic conditions by linear ones. Lemma 3.3. Let <2j, bi be defined by (4). Then <2j for i > M is linear combination of do,... om-i and bi for i > M is linear combination of bo,... &m-i- Proof. Coefficients h^, ■ ■ ■ ^iVi+2M-2 are solution of the system of linear algebraic equations (4). Since the matrix of this system is regular, the solution exists and is unique. <2j is a linear combination of h^, ■ ■ ■ ^iVi+2M-2 and thus <2j for i > M is a linear combination of a,- for 0 < i < M — 1: O-i — Q0a0 + CilO-l + ■ ■ ■ CiM-ldM-l, where the coefficients of this linear combinations are given by /1 iVi 1 iVi + 2 Nl (iVi + 2)2 tm-1 nm (Nt + 2)M-1 (iVi + 2)s \l Nl + 2M -2 (Nl + 2M -2)2 ... (Nt +2M - 2)M~l) \clM-iJ \;.V, +2M - 2)1 J The situation for 6,- is similar. □ Now we summarize the procedure of construction which enables us to find exact values of coefficients of coiflets up to length of support 14: 6 D. Černá, V. Finěk / Central European Science Journals 1 (2003) 1-15 1. For given N take the system of algebraic equations given by Corollary 3.2. 2. Replace cim, ■ ■ ■ &2M-2 by linear combinations of a0,... a^-i and 6m, ■ ■ ■ 62M-2 by linear combinations of 60,... &m-i- 3. Solve the arising system for ao,... clm-i, bo, ■ ■ ■ 6m-i- For greater N use Grobner basis method to simplify the system. 4. Compute filter coefficients h^,..., h^2 by solving the system of linear algebraic equations (4). 4 Examples At last we provide two examples to illustrate our approach based on Corollary 3.2. Example 4.1. For N = 4 and N\ — —5, the following system will be obtained ao — bo — — and a\ — a2 — as — b\ — b2 — 63 — 0, (i4 + 64 — 0 and ae + 66 — 0, (6) a8 + 68 + 140 b\ = 0 and aw + 610 + 840 64 h - 252(al? + bf) = 0. (7) Now a6, as, aw, 66, 68, bw are linear combinations of a0 ■ ■ ■ a5, b0 ... 65. We find these linear combinations and substitute them to (6) and (7). Then after simplification we obtain system -135 + 1264 + 8bj = 0, a4 + 64 = 0, 75 - io64 + 465 = 0, 32aj + 1230064 - 28575 = 0. In this case we can easily find both real solutions in closed form. See Table 2 and Table 3. Example 4.2. For N — 5 and Ni — —5, the following system will be obtained ao — bo — — and a\ — a2 — a3 — a4 — b\ — b2 — 63 = 64 = 0, ae + be — 0 and as + bs — 0, (8) a1o + b1o-252(a25 + b25) = 0 and ai2+ &12-1584 &567-1584 a5 a7 + 924(aj? + &j?) = 0. (9) Now a^, as, aw, a\2, 66, 68, bw, b\2 are linear combinations of a0 ■ ■ ■ a6, 60 ... 66. We find these linear combinations and substitute them to (8) and (9). Consequently we simplify arising system and finally we compute its Grobner bases. The following system is obtained: 11419648 6^ + 246374400 6^ - 13765248000 6^ - 497539800000 65 - 4303042734375 = 0, 298890000 a5 - 5709824 6f + 3945600 6^ + 6931764000 65 + 94943559375 = 0, D. Černá, V. Finěk / Central European Science Journals 1 (2003) 1-15 7 8 a6 + 64 65 + 525 = 0, -525 - 64 b5 + 8 66 = 0. Then by using an algebraic formula for the solution of polynomials of degree 4 we obtain two different real roots: 15 (Vl5u3/4 - 4010u1 ^ (n) feez i=j feez where ^>fe = 2'/2^ (2* • -fc), Vi.fe = (2* • -k) for Z, e Z. Let us further denote /^fe = supp (^j., J^fe = supp Wavelet coefficients satisfy /CO f (x) 2l'2i, (2lx - k) dx. (12) -00 k and if / G CN(Jik), then expanding / about — by Taylor's formula, it follows that for 2' all x G Jitk, (13) where £ depends on x and belongs to the interval J^. If ^ has N vanishing moments, i.e. condition i) in Definition 2.1 is satisfied, then the first N terms don't contribute and I X + E 1/>V>A>V>A, (16) A=(i,fc)eA; A=(*,fc)eA5 where A^ C {A = (J, k),k G Z}, A^ c {A = (Z, fc) , J N. - Smoothness. The smoothness of primal and dual wavelet bases is another desired property. It ensures the validity of norm equivalences, for details see below. - Closed form. The primal scaling functions and wavelets are known in the closed form. It is desirable property for the fast computation of integrals involving primal scaling functions and wavelets. - Well-conditioned bases. Our objective is to construct wavelet bases with improved condition number, especially for larger values of N and N. From the viewpoint of numerical stability, ideal wavelet bases are orthogonal wavelet bases. However, they are usually avoided in numerical treatment of partial differential and integral equations, because they are not accessible analytically, the complementary boundary conditions can not be satisfied and it is not possible to increase the number of vanishing wavelet moments independent from the order of accuracy. Moreover, sufficiently smooth orthogonal wavelets typically have a large support. Biorthogonal wavelet bases on the unit interval derived from B-splines were constructed also in [8] and [19] and they were adapted to homogeneous Dirichlet boundary conditions in [20]. These bases are well-conditioned, but have globally supported dual basis functions. Another construction of spline-wavelets was proposed in [4], but the corresponding dual bases are unknown so far. We should also mention the construction of spline multi-wavelets [15], [22], and [28], though the dual wavelets have a low Sobolev regularity. The paper is organized as follows. Section 2 provides a short introduction to the concept of wavelet bases. Section 3 is concerned with the construction of primal multiresolution analysis on the interval. The primal scaling functions are B-splines defined on the Schoenberg sequence of knots, which have been used also in [4], [8], and [24]. In Section 4 we construct dual multiresolution analysis. There are two types of boundary scaling functions. The functions of the first type are defined in order to preserve the full degree of polynomial exactness as in [1] and [10]. The construction of the scaling functions of the second type is a delicate task, because the low condition number and nestedness of the multiresolution spaces have to be preserved. Section 5 is concerned with the computation of refinement matrices. In Section 6 wavelets are constructed by the method of stable completion proposed in [18]. The construction of initial stable completion is along the lines of [16]. In Section 7 we show that the constructed set of functions is indeed a Riesz basis for the space L2 ([0,1]) and for the Sobolev space Hs ([0,1]) for a certain range of s. In Section 8 we adapt the primal bases to the homogeneous Dirichlet boundary conditions of the first order and the dual bases to the complementary boundary conditions. Quantitative properties of the constructed bases are presented in Section 9. Finally, in Section 10, we compare the efficiency of adaptive wavelet scheme for several spline-wavelet bases and we show the superiority of our construction. Numerical examples are presented for one-dimensional and two-dimensional Poisson equations where the solution has steep gradients. 3 2 Wavelet bases This section provides a short introduction to the concept of wavelet bases. Let us introduce some notation. We use N, Z, Q, and K to denote the set of positive integers, integers, rational numbers, and real numbers, respectively. Let Ny0 denote the set of integers which are greater than or equal to jo. We consider the domain 12 C Rd and the space L2 (12) with inner product (•, •} and induced norm ||-||. Let J? be some index set and let each index X 6 J? take the form X = (j,k), where |A| = j 6 Z is scale or level. Let I2 {J"~) be a space of all sequences b = {bx\x^jf such mat i , i |2 V^f J Definition 1. A family "P := {t/^ 6 J!} CL2 (12) is called a wavelet basis of L2 (12), if /) "P is a Riesz basis for L2 (12), it means that the linear span of "P is dense in L2 (12) and there exist constants c, C 6 (0, °°) such that < Cllbl \h[J) for all b = {bx}x^ €l2{f). (2) Constants := sup {c: c satisfies (2)}, Cv := inf {C : C satisfies (2)} are called Riesz bounds and cond "P = Cy//Cy, is called the condition number of "P. ii) The functions are /oca/ in the sense that diam(flA) < C2^IAI for all A 6 J', (3) where 12^ is the support of t/^, and at a given level j the supports of only finitely many wavelets overlap in any point x 6 12. By the Riesz representation theorem, there exists a unique family ^ = { %, A 6 J?} CL2 (12) biorthogonal to "P, i.e. (Wi,k,%,i) = Sij^i, for all (/,£) 6 (j,/) 6 (4) Here, 8,-j denotes the Kronecker delta, i.e. S,-^ := 1, 8,-j : = 0 for i =/= j. This family is also a Riesz basis forL2 (12). The basis "P is called primal wavelet basis, "P is called dual wavelet basis. In many cases, the wavelet system "P is constructed with the aid of a multiresolution analysis. Definition 2. A sequence 5 = {S;}^eM. of closed linear subspaces Sj C L2 (12) is called a multiresolution or multiscale analysis, if Sio CSJ0+1 C...cSjCSj+1 C...L2(I2) and (u;eN;oS;) = L2 (12). (5) The nestedness of the multiresolution analysis implies the existence of the complement spaces Wj such that SJ+i=Sj®Wj, (6) where © denotes the direct product. We now assume that Sj and Wj are spanned by sets of basis functions : [O...A-. / !• Vj:={Wj,k,keJj}, (7) where ,_?j, j are finite or at most countable index sets. We refer to as scaling functions and t^t as wavelets. The multiscale basis is given by ^ = *»U U */ (8) ;=;o 4 and the overall wavelet basis of L2 (12) is obtained by * = ^UU^ (9) The single-scale and the multiscale bases are interrelated by the wavelet transform TjtS: I2 (lj+s) —> I2 (lj+s), T... (10) The dual wavelet system "P generates a dual multiresolution analysis S with a dual scaling basis j0, (11) where J7m (12) is the space of all algebraic polynomials on 12 of degree at most m. 3 Primal Scaling Basis The primal scaling bases will be the same as bases designed by Chui and Quak in [8], because they are known to be well-conditioned. A big advantage of this approach is that it readily adapts to the bounded interval by introducing multiple knots at the endpoints. Let N be the desired order of polynomial exactness of primal scaling V+N-l k\ basis and let V = (t{ ) be a Schoenberg sequence of knots defined by k=-N+\ t'k:=0, k=-N+l,...,Q, (12) t' — — k—\ V -\ t{:=\, k = V,...,V+N-1. The corresponding B-splines of order N are defined by 4WW:=(C-'t)[i---.C]('-^)+_1. ^e(0,l), (13) where (x)+ := max{0,x}. The symbol [t/,, ■ ■ - tk+N]f is the N-th divided difference of / which is recursively defined as r, t -\ f [tk+l,---,tk+N\f-[tk,---,tk+N-l\f -f . Vk,---, h+N\ f =----- it h T h+N, 'k+N — 'k f{N){h) if h — tk+N, N\ with [tk]f = f{tk). The set 0. (14) Thus there are V — N +1 inner scaling functions and N—l functions at each boundary. Figure 1 shows the primal scaling functions for N = 4 and j = 3. Inner scaling functions are translations and dilations of one function j0 forms a multiresolution analysis ofL2 ([0,1]). ii) The spaces Sj are exact of order N, i.e. nN^([o,i])cSj, j>i. (16) The proof can be found in [8], [24], [29]. 5 0 0.5 1 Fig. 1 Primal scaling functions for N = 4 and j = 3 without boundary conditions. 4 Dual Scaling Basis The desired property of dual scaling basis

) = 0, i.e. its support is [-N+ 1,N + N— l]. In this case N >N and JV + JVhas to be an even number. It is known that there exist sequences {hk}keZ and {h/,}kez such that the functions 4> (2x-k), (x) = (2x — k), x £ '. The parameters hk and hk are called scaling coefficients. By biorthogonality of (j) and (j), we have 2 n2m+khk = 8o,m, m € Z. (17) (18) Note that only coefficients ho,..., and h_^+l,..., hN+^_x may be nonzero. In the sequel, we assume that j>j0:=\\og2(N + 2N-3)] (19) so that the supports of the boundary functions are contained in [0,1]. We define inner scaling functions as translations and dilations of 0: eM = 2J/2$ (2> ■ -k), k=N-l,...,2'-N-N+l. (20) There will be two types of basis functions at each boundary. In the following, it will be convenient to abbre- (21) (22) (23) (24) (25) and index sets by S? = {-n+i, ..,-n + n}, {-iV + iV + l,...,n-2}, {fl-i,.. ,2'-n-n+l}, {2>-n- n + 2,...2J-JV-l}, {V-N,. = {-N+l,...,N-2}, = {V-N-N + 2,...,V-1}, Jj = ^'U^U^U/^U/*'1 = {-iV+l,...,2'-l}. (26) (27) (28) 6 Basis functions of the first type are defined to preserve polynomial exactness by the same way as in [1], [10] BJ,k = 2>/2 E (pk+N-lA(--l))${2>--l)\m, k^jh\ (29) l=-N-N+2 where {po,... ,p$/_1} is a basis of ([0,1]). In Lemma 6 we show that the resulting dual scaling functions do not depend on the choice of the polynomial basis. In our case, pk are the Bernstein polynomials defined pk{x):=b-f,+1(^~1^Jk{b-xf-1-k, k = 0,...,N-l, xGK. (30) The Bernstein polynomials were used also in [16]. On the contrary to [16], in our case the choice of polynomials does not affect the resulting dual scaling basis XP, but it has only the effect of stabilization of the computation, for details see Lemma 6 and the discussion below. The definition of basis functions of the second type is a delicate task, because the low condition number and the nestedness of the multiresolution spaces have to be preserved. This means that the relation 9jtk CVj C Vj+ukG yf'2, should hold. Therefore we define 9jtk, k 6 yj1'2, as linear combinations of functions which are already in Vj+\. To obtain well-conditioned bases, we define functions 9jtk, k 6 yj1'2, which are close to fk := 2>l2§ {2> ■ -k), because 2, are biorthogonal to the inner primal scaling functions and the condition of {ij>fk, k G yf'2 U j is the same as the condition of the set of inner dual basis functions. For this reason, we define the basis functions of the second type by . N+N-l ^j,k = 2i £ hlH2'+l--2k-l)\m, k&,ff'2, (31) l=R-\-lk where h[ are the scaling coefficients corresponding to the scaling function 0. Then 9jtk is close to 0*j|[o,i]> because by (17) we have . N+N-l #M[o,i]=2* £ h,$(V+l--2k-l)\[Qiq, k€,yj-2. (32) k=-N+l Figure 2 shows the functions 9^k and for N = 4, N = 6, and j = 4. The boundary functions at the right boundary are defined to be symmetric with the left boundary functions: eM = e;,2/-*(l-0. kejrf. (33) It is easy to see that ^+lii = 21/2eM(2-), k€,yf (34) for left boundary functions and e;+i,i(i-0 = 21/2e;,i(i-2-), k&yf (35) for right boundary functions. Since the set ©j := {9jk, k 6 J^} is not biorthogonal to *;> = (*;> Qf&j) = QjQ? = (39) where the symbol # denotes the cardinality of the set and Im denotes the identity matrix of the size mxm. Lemma 4. i) Let W* ^ are independent of j, i.e. there are matrices Ql, Qr such that Qj,l = Ql, Qj,r = Qr- (41) Moreover, the matrix Qr results from the matrix Ql by reversing the ordering of rows and columns, which means that (Q*)*,, = (QiW-i,^-,, k,leyf. (42) ii) The following holds: (Q;)M = 5M, keSjjeSf. (43) Hi) The following holds: (Qj)kJ = 0, keS?,lejrj-u Jf. (44) Proof Due to (34) and by substitution we have for k, I 6 ,_?f = (2^a^42"°-) .2^eA,' (2"°-)) = <*A,*>- (45) Therefore, Qjti = Q;0,i = Ql, i.e. the matrix Q^i is independent of j. Due to (35) Qjtr is independent of j too. The property (42) is a direct consequence of the reflection invariance (33). 8 The property ii) follows from the biorthogonality of - -k)}keZ and {0 (• — /)}(eZ- It also implies (44) for k 6 ,y°, I 6 j^'1 u j^'1. It remains to prove (44) for k 6 J?f, I 6 Jff'2 u j^'2. By the definition of dual scaling functions of the second type (31), refinement relation (17) for the dual scaling function 0, and (18), we have for k 6 ,y?,l 6 J?*1'2, N+N-l -k),\/l £ kH2- ~21 - m=N-l-2k i [0,1] N N+N-l 2/ £M(2--2*-n), £ M(2--2/- \«=0 m=N-l-2k N N+N-l N+N-l = 2 £ £ hnhm82k+n,2l+m = 2 £ /l2f-n=0m=N-l-2k m=N-l-2k = 2 £ h2l-2k+mhm = 0. i [0,1] By (33), the relation (44) holds also for k 6 j^°, / 6 jf2. Thus, we can write (QlT 'i> ■= Q]T®j = V° (46) (47) (48) (49) (50) Since the matrix Qj is symmetric in the sense of (42), the properties (33), (34), and (35) hold for 0^ as well. ^— -1-1 1 fin I-1-1 mnl-.-1 cnl-!-.- 0 0.5 1 0 0.5 1 0 0.5 1 0 0.5 1 :ir—: 0 0.5 1 0 0.5 1 0 0.5 1 0 0.5 Fig. 3 Boundary dual scaling functions for N = 4 and N = 6 without boundary conditions. Remark 5. It is known that the scaling function (j) has typically a low Sobolev regularity for smaller values of N. Thus the functions Qj^ have a low Sobolev regularity for smaller values ofN, too. Therefore, we do not obtain the sufficiently accurate entries of the matrix Q j directly by classical quadratures. Fortunately, we are able to compute the matrix Q j precisely up to the round off errors. For k 6 u ,_fL^2'', I 6 yj''1 we have N-2 N-l (j,k,0j,i)= £ £ Q,«{(-)"^(--m))<^(--^)^(--m)>i2((0]i)), m=-N-N+2 «=0 (51) 9 with c[t„ given by (63). Since $_]1» P2 = |.Po> • • • >Pft-\} are two different bases of the space 17$ ([0,1]) andfori= 1,2 we define the sets @j = |SjiJ by N-2 12 I (pU_^(-l))f(2i-l)||0il|, ke,ff\ l=-N-N+2 °j,k ~ °j,2J-N-k> ' e;:i = eM, £e^'2u^Wf2. Furthermore, we define QJ = («fy0j), ^=(Q})~r0J, i= 1,2, (52) and we assume that Q'j is nonsingular. Then ?:={#-!,..., 3N + N- 5} such that -N+N 3N+N-5 °j,k= L mn,kQj+l,n+ £ m«,£0/+l,n, k & . (57) n=-N+l Proof Let©? = l&j^k^jH and ©J-'1'"""1 = {e?f ,fce be defined by N-2 9jon = 2il2 £ {(■)',/, (63) n = 0, otherwise. (64) Hence, the matrix C = {Q,«}( ^Nj^+\ is an upper triangular matrix with nonzero entries on the diagonal which implies that C is invertible. We denote ©j'1 = j 0^, k 6 J^1,1 j and we obtain &f = C©f^mon = C (Mmon)T (p0+{mO"^ = C (Mmon)T (^C0 1 ^®^ ^ . (65) Table 1 Condition numbers of the matrices N N mon. b = 4 b = 10 N N mon. £ = 4 £ = 10 2 2 6.68e+00 9.94e+00 3.16e+01 4 4 2.46e+04 6.75e+02 1.33e+04 2 4 4.66e+02 1.94e+01 9.48e+02 4 6 1.30e+07 2.94e+04 7.34e+04 2 6 1.40e+05 1.00e+02 4.47e+03 4 8 1.24e+10 6.24e+06 9.42e+04 2 8 1.03e+08 8.52e+03 5.81e+03 4 10 1.92e+13 2.26e+09 5.24e+04 2 10 1.48e+ll 1.67e+06 1.58e+03 5 5 5.34e+06 3.29e+04 1.26e+05 3 3 2.18e+02 1.07e+02 1.00e+03 5 7 5.62e+09 6.91e+06 3.73e+05 3 5 3.73e+04 1.88e+02 1.05e+04 5 9 9.39e+12 2.57e+09 3.47e+05 3 7 1.64e+07 1.20e+04 2.26e+04 6 6 1.20e+09 3.68e+06 6.81e+05 3 9 1.54e+10 2.90e+06 1.33e+04 6 8 2.97e+12 1.92e+09 1.81e+06 11 Therefore, the refinement matrix M = \m„ t \ ,u , „t i is given by M= (Cor i)Mm°"cr- (66) We define the dual multiresolution spaces by 5; := span jo. (68) Proof To prove i) we have to show the nestedness of the spaces Sj, i.e. Sj C Sj+\. Note that Sj = span ; = span 0j. (69) Therefore, it is sufficient to prove that any function from ©j can be written as a linear combination of the functions from @j+\. For the left boundary functions of the first type it is a consequence of Lemma 8. By definition (31) it holds also for the left boundary functions of the second type. Since the inner basis functions are just translated and dilated scaling function 0, they obviously satisfy the refinement relation. Finally, right boundary scaling functions are derived by reflection from the left boundary scaling functions and therefore, they satisfy the refinement relation, too. It remains to prove that (J Sj=L2 ([0,1]), (70) where M denotes the closure of the set M in L2 ([0,1]). It is known [26] that for the spaces generated by inner functions S°:={eM,£6J^0} (71) we have _ (J S° = L2([0,1]). (72) Hence, (70) holds independently of the choice of boundary functions. To prove ii) we recall that the scaling function 0 is exact of order N, i.e. 2i(r+1/2)xr = £ aktr2il2§(2>x-k), xeRa.e., r = 0,...,N-l, (73) where «*,,= ((•)*,* (•->•)). (74) It implies that for r = 0,... ,N— 1, x 6 (0,1), the following holds ft-2 V-N-N+l 2i(r+ll2)xr\m= £ aKr2il2HVx-k)\m+ £ aKr2''2^{2'x-k)\{Qtl) k=-N-N+2 k=N-\ V+N-2 + £ aKr2'l2^{2'x-k)\m. k=2i-N-N+2 By (29), (33), and (69), we immediately have ([0,1]) C span{#M,*e Jf'l U^U jf-1} C Sj. (75) 12 5 Refinement Matrices Due to the length of support of primal scaling functions, the refinement matrix Afyo corresponding to

o,-iV+2(2yV-3) V fc,-i(0) ^o,-i (1) ... (2tf-3) / /^1,-iv+i (0) ^1,-iv+i (1) ... 01,-Af+i (2AT-3)\ 0i,-iV+2(O) i,-iv+2(l) ••• 4>i,-iV+2(2JV-3) V i,iv-i (0) ^i,iv-i(l) ... 4>i,iV-i(2JV-3) / (78) (79) (80) (81) The solution of system (79) exists and is unique if and only if the matrix p2 is nonsingular. The proof of nonsingularity of p2 can be found [35]. To compute the refinement matrix corresponding to the dual scaling functions, we need to identify first the structure of refinement matrices M®0 corresponding to ®. / M^o = Mf V \ (82) where Mf and Mf are blocks (2JV + 3N-5) x (N + N-2) andA; is a matrix of the size (2'+l-N-2N+3) (V-N-2N+3) given by (kj)^n = -j=hm-2n, 0 h is called a stable completion of M ^0, if llM^I^MT11| = 0(1), 7->oo, (86) where My := (M;,o,M;,i). The idea is to determine first an initial stable completion and then to project it to the desired complement space Wj determined by {Vj}j>j0 - This is summarized in the following theorem [6]. Theorem 11. Let = <«P^> = 0. (89) (90) We found the initial stable completion by the method from [16], [18] with some small changes. The difference is only in the dimensions of the involved matrices and in the definion of the matrix Fy. Recall that Ay is the interior block in the matrix My:o of the form (h0 0 ... 0\ hi 0 h3 h0 hp/ hx-2 '■ 0 hN-i 0 0 hN ho (91) hNJ where ho,...,h^ are scaling coefficients corresponding to :=Ay. (92) In [16], it was proved for B-spline scaling functions that ^/2i'---'^-L'/2J '=1,---,n-Therefore, the ellimination is always possible. The elimination matrices are of the form ,(2i-l) ■ = diag i, U2l-1, • • •, U2l-1, In- i ) #|2,) := diag(Iiv_1-,L2,-,...,L2,-,I,--i) where U.-+1 := ä[«-/21+l ^0 1 . n-m\ h{i) N- L//2j — 1 (93) (94) (95) (96) 15 It is easy to see that indeed Aw=HwA('-i). After N elimination steps we obtain the matrix A^ which looks as follows /0 0 0\ Af> = H/A; = 00 bO 00 Ob : 0 with b=/=0. We define and Then, we have where Hy := Hy W H(i) Vo 6/ /0 ... 0 fc-1 0 0 0 0 ... 0 0 Ob-1 0 V 0 b-1 0 ... 0/ F;:= m 00 1 0 00 0 1 : 0 '■■ 1 0 V oj B;F; = 0. After these preparations we define extended versions of the matrices Hy, Ay, A^, and B y by (97) (98) (99) (100) (101) II : I' V kf := C"~\f> V (102) V V Ijv-i/ /Iiv-i \ [In-i \ kj:=\ \j , Bj := Bj . (103) Note that Hy, Ay, A^0, and By are all matrices of the size (#J^y+i) x Hence, the completion of A1, has to be a (#J^y+i) x V. On the contrary to the construction in [16], we define an expanded version of Fy as in 16 [5], because it leads to a more natural formulation, when then the entries of both the refinement matrices belong to \/2. The difference is in multiplication by \fl. I Ft:=V2 O V o The above findings can be summarized as follows. Lemma 12. The following relations hold: \ }N-1 }N-1 (104) B;Af =I# ^F; = I2, and B;F; = 0, FjAf)=0. (105) (106) The proof of this lemma is similar to the proof in [16]. Note the refinement matrix M^o can be factorized as M;,o = P/A/ = P/HT1Af) with Mi \ Mr Now we are able to define the initial stable completions of the refinement matrices M^o-Lemma 13. Under the above assumptions, the matrices M;,i:=P/HTlF/' j>j0, are uniformly stable completions of the matrices M^q. Moreover, the inverse G/,o o/M; = (M;o,M; i) is given by (107) (108) (109) (110) •J " I' = ^FjH.PT1 (111) The proof of this lemma is straightforward and similar to the proof in [16]. Then using the initial stable completion M^i we are already able to contruct wavelets according to the Theorem 11. 17 7 Norm equivalences In this section, we prove norm equivalences and we show that f and "P are Riesz bases for the space 1? ([0,1]). Furthermore, we show that \7rs^\^x, A G ^} is a Riesz basis for Sobolev spaceHs ([0,1]) for somes specified below. The proofs are based on the theory developed in [13] and [16]. Let us define y:=sup{s:GHs(M)}, y:= sup{s : G Hs (K)} . (112) It is known that y = N— \ . The Sobolev exponent of smoothness yean be computed by method from [21]. The functions in jo, have the Sobolev regularity at least y, because the primal scaling functions are B-splines and the primal wavelets are finite linear combinations of the primal scaling functions. Similarly, the functions in jo, have the Sobolev regularity at least y. Theorem 14. i) The sets {'Pj} '■= {^;}y>y0 and {■£/} := {^;}y>y0 are uniformly stable, i.e. j0. (113) ii) For all j > jo, the Jackson inequalities hold, i.e. inf || v — || <2^||v||HS([0]i]) for all vGHs ([0,1]) and s jo, the Bernstein inequalities hold, i.e. IIv/IIhs([o l]) ~ ^S>\\vj\\ for all Vj € Sj and s < y, (116) and IIv/IIhs([o 11) ~ ^S>\\vj\\ for all Vj € Sj and s < f. (117) £ bkj,k 18 Proof i) Due to Lemma 2.1 in [16], the collections {■?>/} := {^j} > and := > are uniformly stable, if <£>; and ; are biorthogonal, j0, and ; and ; are locally finite, i.e. and #{k 6 /j:%n%^0} < 1, for all £ 6 J^, j > jQ, #{k 6 /j:fl;ii/fl%^0} < 1, for all £ 6 J^, j > jo, (118) (119) (120) where njtk := supp ^ and £2jtk := supp 0^. By (39) the sets 3. Let , ^omp := < ^ P ^ - ^ ^' 1 l It r.nn K^i Anna K,. ilia maiVtnA rink' vTt"1'; ^ = 0,..., 2^ — 1 }•. It can be done by the method of stable completion as in Section 6. 9 Quantitative Properties of Constructed Bases In this section the condition numbers of scaling bases, the single-scale wavelet bases and the multiscale wavelet bases are computed. As in [24] it can be improved by the L2-normalization on the primal side. It will be shown that in the case of cubic spline wavelets bases the construction presented in this thesis yields optimal L2-stability, which is not the case of constructions in [16] and [24]. The condition numbers of scaling bases and wavelet bases satisfying the complementary boundary conditions of the first order are presented as well. The other criteria for the effectiveness of wavelet bases is the condition number of the corresponding preconditioned stiffness matrix. To improve it further we apply orthogonal transformation to the scaling basis on the coarsest level and then we use a diagonal matrix for preconditioning. It is known that Riesz bounds (2) of basis j0, (127) Vj!*=-y=^=, Y?,k = Yj,k*y/{Yj,k,Yj,k), kefj, j > j0. (128) \l {Wj,k,Wj,k) Then the new primal scaling and wavelet bases are normalized with respect to the L2-norm. As already mentioned in Remark 7, the resulting bases for N = 2 are the same as those designed in [24] and [25]. For quadratic spline-wavelet bases, i.e. N = 3, the condition of our bases is comparable to the condition of the bases from [24] and [25]. In [3], it was shown that for any spline wavelet basis of order N on the real line, the condition is bounded below by 2N~l. This result readily carries over to the case of spline wavelet bases on the interval. Now, the constructions from [24], [25] yields wavelet bases whose Riesz bounds are nearly optimal, i.e. cond "P^ ~ 2N~l for N = 2 and N = 3. Unfortunately, the L2- stability gets considerably worse for N > 4. As can be seen in Table 2, the column the presented construction seems to yield the optimal Instability also for N = 4. Note that the case N = 4, N = 4 is not included in Table 2. It was shown in [9] that the corresponding scaling functions and wavelets do not belong to the space L2. In Table 3 the condition of the multiscale wavelet bases f^0:J = , *7 «5 *; IpN 2 2 10 2.00 1.73 2.30 1.97 2.00 2.00 2.02 2.00 2 4 10 2.00 1.73 2.09 1.80 2.00 2.00 2.04 2.00 2 6 10 2.00 1.73 2.26 2.03 2.00 2.00 2.30 2.26 2 8 10 2.00 1.73 2.90 2.78 2.34 2.22 3.14 3.81 3 3 10 3.25 2.76 7.58 6.37 4.49 4.00 7.07 4.27 3 5 10 3.25 2.76 3.93 3.49 4.63 4.00 5.55 4.05 3 7 10 3.25 2.76 3.53 3.11 4.55 4.00 5.13 4.01 3 9 10 3.25 2.76 3.75 3.32 4.44 4.00 5.51 4.23 4 6 10 5.18 4.42 10.88 9.07 14.02 8.00 24.36 9.23 4 8 10 5.18 4.42 6.69 5.88 13.96 8.00 16.98 8.20 4 10 10 5.18 4.42 5.83 5.16 13.82 8.00 15.27 8.00 5 9 10 8.32 7.13 29.87 25.23 67.74 27.44 169.76 68.90 Table 3 The condition of the multiscale wavelet bases N N 30 ^0,2 IT/N ^0,3 IT/N IT/N ^0,2 IT/N ^0,3 III« rJoA III« 2 2 2 1.98 2.27 2.52 2.65 2.76 2.20 2.42 2.65 2.78 2.87 2 4 3 2.13 2.25 2.30 2.33 2.34 2.15 2.26 2.31 2.33 2.35 2 6 4 2.47 2.71 2.84 2.92 2.99 2.60 2.78 2.88 2.94 3.00 2 8 4 3.71 4.77 5.35 5.68 5.89 4.44 5.17 5.57 5.82 5.98 3 3 3 4.92 6.01 7.15 7.87 8.50 7.25 8.54 9.50 10.08 10.48 3 5 4 4.51 4.82 5.01 5.10 5.14 4.63 4.98 5.11 5.15 5.16 3 7 4 4.19 4.38 4.44 4.46 4.48 4.24 4.39 4.45 4.48 4.49 3 9 5 4.44 4.55 4.61 4.64 4.65 4.48 4.58 4.62 4.64 4.66 4 6 4 9.55 10.90 11.88 12.50 12.90 10.88 12.90 13.35 13.48 13.58 4 8 5 8.01 8.31 8.54 8.68 8.76 8.23 8.60 8.73 8.79 8.81 4 10 5 7.89 8.02 8.09 8.12 8.13 7.93 8.05 8.11 8.13 8.14 5 9 5 30.22 64.60 75.17 81.03 84.81 72.34 83.19 87.93 90.11 91.27 22 Table 4 The condition number of our multiscale wavelet bases *FN, and *PN, and multiscale wavelet bases from [91 and [241 Jo,5 Jo,5 1 J L J N N jo s mCDF 3 3 3 5 6.68 6.25 8.50 8.52 8.17 10.48 3 5 4 5 4.36 5.31 5.14 4.37 5.36 5.16 3 7 4 5 4.04 8.57 4.48 4.04 8.63 4.49 3 9 5 5 4.00 25.40 4.65 4.00 25.76 4.66 4 6 4 5 9.89 141.95 12.90 10.43 160.54 13.58 4 8 5 5 8.27 257.41 8.76 8.27 258.56 8.81 4 10 5 5 8.04 917.10 8.13 8.04 935.38 8.14 4 12 5 5 8.01 3971.65 8.44 8.01 3992.29 8.45 Example 15. We consider one-dimensional Poisson equation with homogeneous Dirichlet boundary conditions -«"=/, in 12 = (0,1), i/(0) = i/(l) =0, (131) whose solution u is given by "W=4"^o_r7(1-"^o_rYj+x(1-x)' xGn- (132) The solution exhibits steep gradient near the boundary, see Figure 8. Let us define the diagonal matrix D = diag((¥^,VM>1/2) (133) and operators A = D_1 (•?',«?') D_1, f=D"1{/,lf}. (134) Then the variational formulation of (131) is equivalent to AU = f (135) Table 5 The condition of scaling bases and single-scale wavelet bases satisfying complementary boundary conditions of the first order N N j *y IpN 3 3 10 2.74 2.74 4.49 4.34 4.00 4.00 4.13 4.00 3 5 10 2.74 2.74 4.94 4.58 4.00 4.00 6.68 6.27 3 7 10 2.74 2.74 8.61 8.33 4.84 4.27 12.11 16.05 3 9 10 2.74 2.74 17.94 17.78 8.16 6.25 25.17 46.10 4 6 10 4.53 4.31 7.90 6.83 9.47 8.00 16.46 8.00 4 8 10 4.53 4.31 11.16 10.04 8.46 8.03 25.40 15.32 4 10 10 4.53 4.31 17.90 16.97 8.39 8.42 37.78 35.93 Table 6 The condition number of the stiffness matrices A^ec, k°rts of the size m x m N N j 5 M \ on N N j 5 M 3 3 3 1 16 12.24 3.78 4 4 4 1 33 47.02 15.38 4 128 12.82 5.05 4 259 50.01 18.13 7 1024 12.86 5.37 7 2049 50.28 18.91 3 5 4 1 32 52.97 4.20 4 6 4 1 33 48.98 15.25 4 256 55.09 8.41 4 259 51.61 16.15 7 2048 55.24 9.47 7 2049 50.28 16.31 3 7 4 1 32 71.07 10.74 4 8 5 1 65 205.56 15.92 4 256 71.90 33.52 4 513 208.88 26.80 7 2048 71.91 38.66 7 4097 209.31 27.69 23 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 Fig. 8 The exact solution and the right hand side of (131). and the solution u is given by u = UD1 llF. We solve the infinite dimensional problem (135) by the inexact damped Richardson iterations. This algorithm was originally proposed by Cohen, Dahmen and DeVore in [10]. Here, we use its modified version from [30]. Figure 9 shows a convergence history for the spline-wavelet bases designed in this contribution with N = 4 and N = 6 denoted by CF and the spline-wavelet bases with the same polynomial exactness from [24]. We use also the algorithm with the stiffness matrix Aort which has lower condition number, see Table 6. Its convergence history is denoted by CFort. Note that the relative error in the energy norm for an adaptive scheme with our bases is significantly smaller even though the number of involved basis functions is about half compared with bases in [24]. -e-CF -^-■Primbs ■■*■ CFort -s-CF Primbs ■ ■•■ CFort o 10 ID o 10 ^ 10"" -•-CF ■-^Primbs ■■■•■■CFort degrees of freedom number of iterations number of iterations Fig. 9 Convergence history for Id example, comparison of our wavelet bases with and without orthogonalization and wavelet bases from [24]. Example 16. We consider two-dimensional Poisson equation -Au = /, in Q = (0, l)2, dQ, = 0, (136) with the solution u given by u(x,y) = u(x)u(y), (x,y) G (137) where u(y) are given by (137). We use the adaptive wavelet scheme with the cubic wavelet basis adapted to homogeneous Dirichlet boundary conditions of the first order. The convergence history for our wavelet bases with and without orthogonalization and wavelet bases from [24] is shown in Figure 10. Acknowledgements The research of the first author has been supported by the Ministry of Education, Youth and Sports of the Czech Republic through the Research Centers LC06024. The second author has been supported by the research center 1M06047 of the Ministry of Education, Youth and Sports of the Czech Republic and by the grant 201/09/P641 of the Grant Agency of the Czech Republic. 24 -e-CF -•■- ■ Primbs 8 V» <* >+«. V > V % ■■■*■■ CFort 12000 10000 E f 8000 o 6000 §, 4000 2000 -•-CF Primbs ■■■*■■ CFort -e-CF ■-•-Primbs ■■■•■■CFort Fig. 10 Convergence history for 2d example, comparison of our wavelet bases with and without orthogonalization and wavelet bases from [24]. References 1. Andersson, L.; Hall, N.; Jawerth, B.; Peters, G.: Wavelets on the Closed Subsets of the Real Line, in: Topics in the Theory and Applications of Wavelets, L.L. Schumaker and G. Webb (eds.), Academic Press, Boston, 1994, pp. 1-64. 2. Barsch, T.: Adaptive Multiskalenverfahren für Elliptische Partielle Differentialgleichungen - Realisierung, Umsetzung und Numerische Ergebnisse, Ph.D. thesis, RWTH Aachen, 2001. 3. Bittner, K.: A New View on Biorthogonal Spline Wavelets, preprint, Universität Ulm, 2005. 4. Bittner, K.: Biorthogonal Spline Wavelets on the Interval, in: Wavelets and Splines, Athens, 2005, Mod. Methods Math., Nashboro Press, Brentwood, TN, 2006, pp. 93-104. 5. Burstedde, C: Fast Optimized Wavelet Methods for Control Problems Constrained by Elliptic PDEs, Ph.D. thesis, Universität, Bonn, 2005. 6. Carnicer, J.M.; Dahmen, W.; Peňa, J.M.: Local decomposition of refinable spaces, Appl. Comp. Harm. Anal. 6, (1999), pp. 1-52. 7. Canuto, C; Tabacco, A.; Urban, K.: The Wavelet Element Method, Part I: Construction and Analysis, Appl. Comp. Harm. Anal. 6,(1999), pp. 1-52. 8. Chui, C.K.; Quak, E.:, Wavelets on a Bounded Interval, in: Numerical Methods of Approximation Theory (Braess, D.; Schumaker, L.L., eds.), Birkhäuser, 1992, pp. 53-75. 9. Cohen, A.; Daubechies, L; Feauveau, J.-C: Biorthogonal Bases of Compactly Supported Wavelets. Comm. Pure and Appl. Math. 45,(1992), pp. 485-560. 10. Cohen, A.; Daubechies, L; Vial, P.: Wavelets on the Interval and Fast Wavelet Transforms, Appl. Comp. Harm. Anal. 1, (1993), pp.v54-81. 11. Černá, D.: Biorthogonal Wavelets, Ph.D. thesis, Charles University, Prague, 2008. 12. Dahlke, S.; Fornasier, M.; Primbs, M.; Raasch, T.; Werner, M.: Nonlinear and Adaptive Frame Approximation Schemes for Elliptic PDEs: Theory and Numerical Experiments, preprint, Philipps-Universität Marburg, 2007. 13. Dahmen, W.: Stability of Multiscale Transformations, J. Fourier Anal. Appl. 4, (1996), pp. 341-362. 14. Dahmen, W.: Multiscale Analysis, Approximation, and Interpolation Spaces, in: Approximation Theory VIII, (Chui, C.K.; Schumaker, L.L, eds.), World Scientific Publishing Co., 1995, pp. 47-88. 15. Dahmen, W.; Han, B.; Jia R.Q.; Kunoth A.: Biorthogonal Multiwavelets on the Interval: Cubic Hermite Splines, Constr. Approx. 16, (2000), no. 2, pp. 221-259. 16. Dahmen, W.; Kunoth, A.; Urban, K.: Biorthogonal Spline Wavelets on the Interval - Stability and Moment Conditions, Appl. Comp. Harm. Anal. 6, (1999), pp. 132-196. 17. Dahmen, W.; Kunoth, A.; Urban, K.: Wavelets in Numerical Analysis and Their Quantitative Properties, in: Surface fitting and multiresolution methods 2 (Le Méhauté, A.; Rabut, C; Schumaker, L., ed.), 1997, pp. 93-130. 18. Dahmen, W.; Miccheli, C.A.: Banded Matrices with Banded Inverses, II: Locally Finite Decomposition of Spline Spaces, Constr. Appr. 9, (1993), pp. 263-281. 19. Jia, R.Q.: Stable Bases of Spline Wavelets on the Interval, in: Wavelets and Splines, Athens 2005, Mod. Methods Math., Nashboro Press, Brentwood, TN, 2006, pp. 120-135. 20. Jia, R.Q.: Spline Wavelets on the Interval with Homogeneous Boundary Conditions, Adv. Comput. Math. 30, (2009), no. 2, pp. 177-200. 21. Jia, R.Q.; Jiang, Q.T.: Spectral Analysis of the Transition Operator and its Applications to Smoothness Analysis of Wavelets, SLAM J. Matrix Anal. Appl. 24, (2003), no. 4, pp. 1071-1109. 22. Jia, R.Q.; Liu, S.T.: Wavelet Bases of Hermite Cubic Splines on the Interval, Adv. Comput. Math. 25, (2006), no. 1-3, pp. 23-39. 23. Pabel, R.: Wavelet Methods for PDE Constrained Elliptic Control Problems with Dirichlet Boundary Control, thesis, Universität Bonn, 2005. 24. Primbs, M.: Stabile biorthogonale Spline-Waveletbasen auf dem Intervall, dissertation, Universität Duisburg-Essen, 2006. 25. Primbs, M.: New Stable Biorthogonal Spline Wavelets on the Interval, preprint, Universität Duisburg-Es sen, 2007. 26. Primbs, M.: Technical Report for the Paper: 'New Stable Biorthogonal Spline Wavelets on the Interval', Universität Duisburg-Essen, 2007. 27. Raasch, T.: Adaptive Wavelet and Frame Schemes for Elliptic and Parabolic Equations, Ph.D. thesis, Marburg, 2007. 28. Schneider, A.: Biorthogonal Cubic Hermite Spline Multiwavelets on the Interval with Complementary Boundary Conditions, preprint, Philipps-Universität Marburg, 2007. 29. Schumaker, L.L.: Spline Functions: Basic Theory, Wiley-Inter science, 1981. 25 30. Stevenson, R.: Adaptive Solution of Operator Equations Using Wavelet Frames, SLAM J. Numer. Anal. 41, (2003), pp. 1074-1100. 31. Stevenson, R.: On the Compressibility of Operators in Wavelet Coordinates, S1AM J. Math. Anal. 35, (2004), no. 5, pp. 1110-1132. 32. Stevenson, R.: Composite Wavelet Bases with Extended Stability and Cancellation Properties, SLAM J. Numer. Anal. 45, (2007), no. l,pp. 133-162. 33. Grivet Talocia, S.; Tabacco, A.: Wavelets on the Interval with Optimal Localization, in: Math. Models Meth. Appl. Sei. 10, 2000, pp. 441-462. 34. Turcajova, R.: Numerical Condition of Discrete Wavelet Transforms. SLAM J. Matrix Anal. Appl. 18, (1997), pp. 981-999. 35. Weyrich, N.: Spline Wavelets on an Interval, in: Wavelets and Allied Topics, 2001, pp. 117-189. Cubic spline wavelets with complementary boundary conditions Dana Cernáa, Václav Finěka aDepartment of Mathematics and Didactics of Mathematics, Technical University in Liberec, Studentská 2, 461 17 Liberec, Czech Republic Abstract We propose a new construction of a stable cubic spline-wavelet basis on the interval satisfying complementary boundary conditions of the second order. It means that the primal wavelet basis is adapted to homogeneous Dirich-let boundary conditions of the second order, while the dual wavelet basis preserves the full degree of polynomial exactness. We present quantitative properties of the constructed bases and we show superiority of our construction in comparison to some other known spline wavelet bases in an adaptive wavelet method for the partial differential equation with the biharmonic operator. Keywords: wavelet, cubic spline, complementary boundary conditions, homogeneous Dirichlet boundary conditions, condition number 2000 MSC: 46B15, 65N12, 65T60 1. Int ro duct ion In recent years wavelets have been successfully used for solving partial differential equations [2, 11, 12, 16, 27] as well as integral equations [22, 24, 25], both linear and nonlinear. Wavelet bases are useful in the numerical treatment of operator equations, because they are stable, enable high order-approximation, functions from Besov spaces have sparse representation in wavelet bases, condition numbers of stiffness matrices are uniformly bounded and matrices representing operators are typically sparse or quasi-sparse. The Email addresses: dana.cernaStul.cz (Dana Černá), vaclav.finekStul.cz (Václav Finěk) Preprint submitted to Applied Mathematics and Computation July 17, 2012 quantitative properties of wavelet methods strongly depend on the choice of a wavelet basis, in particular on its condition number. Therefore, a construction of a wavelet basis is always an important issue. Wavelet bases on a bounded domain are usually constructed in the following way: Wavelets on the real line are adapted to the interval and then by tensor product technique to the n-dimensional cube. Finally by splitting the domain into overlapping or non-overlapping subdomains which are images of a unit cube under appropriate parametric mappings one can obtain a wavelet basis or a wavelet frame on a fairly general domain. Thus, the properties of the employed wavelet basis on the interval are crucial for the properties of the resulting bases or frames on a general domain. In this paper, we propose a construction of cubic spline wavelet basis on the interval that is adapted to homogeneous Dirichlet boundary conditions of the second order on the primal side and preserves the full degree of polynomial exactness on the dual side. Such boundary conditions are called complementary boundary conditions [18]. We compare properties of wavelet bases such as the condition number of the basis and the condition number of the corresponding stiffness matrix. Finally, quantitative behaviour of adaptive wavelet method for several boundary-adapted cubic spline wavelet bases is studied. First of all, we summarize the desired properties of a constructed basis: - Polymial exactness. Since the primal basis functions are cubic B-splines, the primal multiresolution analysis has polynomial exactness of order four. The dual mult iresolut ion analysis has polynomial exactness of order six. As a consequence, the primal wavelets have six vanishing moments. - Riesz basis property. The functions form a Riesz basis of the space L2 ([0,1]) and if scaled properly they form a Riesz basis of the space #o2([0,l]). - Locality. The primal and dual basis functions are local, see definition of locality below. Then the corresponding decomposition and reconstruction algorithms are simple and fast. - Biorthogonality. The primal and dual wavelet bases form a biorthogo-nal pair. - Smoothness. The smoothness of primal and dual wavelet bases is another desired property. It ensures the validity of norm equivalences. - Closed form. The primal scaling functions and wavelets are known in 2 the closed form. It is a desirable property for the fast computation of integrals involving primal scaling functions and wavelets. - Complementary boundary conditions. Our wavelet basis satisfy complementary boundary conditions of the second order. - Well-conditioned bases. Our objective is to construct a well conditioned wavelet basis. Many constructions of cubic spline wavelet or multiwavelet bases on the interval have been proposed in recent years. In [5, 17, 26] cubic spline wavelets on the interval were constructed. In [14] cubic spline multiwavelet bases were designed and they were adapted to complementary boundary conditions of the second order in [28]. In this case dual functions are known and are local. Cubic spline wavelet bases were also constructed in [1, 9, 20, 21]. A construction of cubic spline multiwavelet basis was proposed in [19] and this basis was already used for solving differential equations in [8, 23]. However, in these cases duals are not known or are not local. Locality of duals are important in some methods and theory, let us mention construction of wavelet bases on general domain [18], adaptive wavelet methods especially for nonlinear equations, data analysis, signal and image processing. A general method of adaptation of biorthogonal wavelet bases to complementary boundary conditions was presented in [18], but this method often leads to very badly conditioned bases. This paper is organized as follows: In Section 2 we briefly review the concept of wavelet bases. In Section 3 we propose a construction of primal and dual scaling bases. The refinement matrices are computed in Section 4 and in Section 5 primal and dual wavelets are constructed. Quantitative properties of constructed bases and other known cubic spline wavelet and multiwavelet bases are studied in Section 6. In Section 7 we compare the number of basis functions and the number of iterations needed to resolve the problem with desired accuracy for our bases and bases from [28]. A numerical example is presented for an equation with the biharmonic operator in two dimensions. 2. Wavelet bases This section provides a short introduction to the concept of wavelet bases in Sobolev spaces. We consider the domain Q C Md and the Sobolev space or its subspace H C Hs (Q) for nonnegative integer s with an inner product 3 (•, -)H, a norm \\-\\H and a seminorm \-\H. In case s — 0 we consider the space I? (Q) and we denote by (•, •) and ||-|| the L2-inner product and the L2-norm, respectively. Let J be some index set and let each index A £ J take the form A = (j, k), where |A| :— j £ Z is a scale or a level. Let 12{J):= Jv:i7^R,^|vA|2j0> °f closed linear subspaces Vj c H is called a multiresolution or multiscale analysis, if y, i;. i..... y, r,., • ••// (4) and Uj>j0V^- is complete in H. 4 The nestedness and the closedness of the multiresolution analysis implies the existence of the complement spaces Wj such that Vj+\ — Vj © Wj. We now assume that Vj and Wj are spanned by sets of basis functions $j := {jik, k G Xj) , *j := {V»j,fc, fc G J/} , (5) where Xj and are finite or at most countable index sets. We refer to (f>j^ as scaling functions and tpj^ as wavelets. The multiscale basis is given by ^j0!s — &j0 u Uj-^jo 1 and the wavelet basis of H is obtained by $ = J0 u Uj>jo ^he dual wavelet system $ generates a dual multiresolution analysis V with a dual scaling basis J0. Polynomial exactness of order iV G N for the primal scaling basis and of order iV G N for the dual scaling basis is another desired property of wavelet bases. It means that Pjv-i (fi) C P„(fi)c^, j>j0, (6) where Pm (Q) is the space of all algebraic polynomials on Q of degree less or equal to m. By Taylor theorem, the polynomial exactness of order N on the dual side is equivalent to N vanishing wavelet moments on the primal side, i.e. / P (x) Va (x) dx = 0, P G P^, Va G M (7) Jn 3>30 3. Construction of Scaling Functions We propose a new cubic spline wavelet basis with six vanishing wavelet moments satisfying homogeneous Dirichlet boundary conditions of order two. Six vanishing wavelet moments on the primal side is equivalent to the polynomial exactness of order six on the dual side. We choose polynomial exactness of this order, because the dual scaling function of order four does not belong to L2 (R) and the polynomial exactness of order greater than six leads to a larger support of primal wavelets which makes the computation more expensive. The first step is the construction of primal scaling functions on the unit interval. Primal scaling basis is formed by cubic B-splines on the knots t3k defined by 'V <>• *u:=i> *£:=4, & = 1, ■ ■ ■ 2>'- 1, (8) 5 2J + 1 ' 2J + 1 2J+2 The corresponding cubic B-splines are defined by B{ (x) := (ti+4 ~ ti) ft,..., ti+4] t (t - xf+ , x £ [0,1] , where [x)+ :— max{0, x} and [ii,... £jv]t / is the A-th divided difference of /. The set j : = {<^j,fe, & = —2,... , 2J — 2} of primal scaling functions is simply given by (f)Jtk:=2j/2Bl fc= -2,...,2J -2, j > 0. (9) Thus there are 2J — 5 inner scaling functions and 3 boundary functions at each edge. The inner functions are translations and dilations of a function

is the biorthogonality to and the polynomial exactness of order six. Let

- 2} , and uxl,2 = {_2)...)4}) TR,2 UZf'1 = {2J -8,... ,2J ■ -2}, -jL,\ ~ xj uxl)2u20uXfl)2uXfl)l = {-2,...,2J -2} (13) Basis functions of the first type are defined to preserve polynomial exactness and the nestedness of multiresolution spaces by the same way as in [17]: 4 ^(i) = 2J/2^(ft+2,^(.-/))^(2^-i), keXf'\ ie[0,l], (14) l=-8 where {p0,... ,p5} is a monomial basis of P5 ([0,1]), i.e. pt (x) = xs, x £ [0,1], « = 0,...,5. The definition of basis functions of the second type is a delicate task, because the low condition number and the nestedness of the multiresolution spaces have to be preserved. This means that the relation 6^4 £ Vj c Vj+\ should hold. Therefore we define 6^4 as linear combinations of functions that are already in Vj+\. To obtain well-conditioned basis, we define a function 9jt4 which is close to (p^A :— 2^2(p (2? • —4), because ^>*4 is biorthogonal to the inner primal scaling functions and the condition of |<^4, k £ Xf'2 UZ^| is close to the condition of the set of inner dual basis functions. 7 For this reason, we define the basis function of the second type by 9 0j>4 (x) = 2j/2 ~hi4> i23+lx - 8 - 0 > x G [0,1] , (15) Z=-3 where /ij are the scaling coefficients corresponding to the scaling function (p. Then 6^4 is close to (f^\ restricted to the interval [0,1], because by (10) we have 9 4>fA (x) = 2J'/2 E ^ (*+lx ~ 8 " 0 - x G [0,1] . (16) Figure 2 shows the functions 6^4 and (f^A. 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 Figure 2: The functions f 4 and #4^4. The boundary functions at the right boundary are defined to be symmetric with the left boundary functions: 0j,k (x) = 0ji2j_4_k (1-x), x G [0,1] , k G If. (17) It is easy to see that 6j+i,k(x) = y/2 0jtk(2x), x G [0,1] , k G if, (18) for left boundary functions and 0j+i>fc(l-x) = v^0J-fc(l-2x), ie[0,l], fee If, (19) for right boundary functions. Since the set Qj :— {6jtk, k G I,} is not biorthogonal to j, we derive a new set fee 2^} (20) 8 from Qj by biorthogonalization. Let Qi = (fe.MU' (21) We verify numerically that Qj is invertible. Viewing j and Qj as column vectors we define «1-; : Q; '<-';• (22) Then j is biorthogonal to Qj, because ($j, = QjT6j) = QjQj1 = (23) where the symbol # denotes the cardinality of the set and Im denotes the identity matrix of the size m x m. Remark 1. General approach of adapting wavelet bases to the unit interval was proposed in [18]. The idea is to remove certain boundary scaling functions to achieve homogeneous boundary conditions on the primal side. Then it is necessary to have the same number of basis functions on the dual side. Therefore an appropriate number of inner dual functions is used for the definition of boundary dual generators in formula (14). Applying this approach to cubic spline basis constructed in [5] and basis constructed in [26] we obtain the same resulting basis, because these constructions differs in the definition of some functions which are discarded during adaptation to complementary boundary conditions of the second order. Unfortunately, this basis has large condition number, although the starting basis in [5] is well conditioned. Its quantitative properties are presented in Section 6. 4. Refinement matrices From the nestedness and the closedness of multiresolution spaces it follows that there exist refinement matrices M^o and M^i such that 'I'/ M!,,(IVi- «1-; Ml,'!"; i- (24) 9 Due to the length of support of primal scaling functions, the refinement matrix MJ)0 has the following structure: M where Aj is a (2J (A. ■3,0 1 — 5) x (2J — 5) matrix given by h (25) -l-2n J > m.n V2 0, n = 1,..., 2J - 5, 0 < m + 1 - 2n < 4, (26) otherwise, where ft,m are primal scaling coefficients (10), and M^, M# are given by 0 0 \ 7 8 1 8 0 1 4 3 4 0 0 3 5 2 5 0 3 29 20 40 0 0 1 2 \o 0 1 8 / MR = M (27) The symbol denotes a matrix that results from a matrix M by reversing the ordering of rows and columns. To compute the refinement matrix corresponding to the dual scaling functions, we need to identify first the structure re of refinement matrices Mf0 corresponding to ©: (28) 10 where and are blocks 21x7 and Aj is a matrix of the size (2J+1 — 13) x (2J — 13) given by Aj) = hm-2n-4 ^ n = ^ ... y - 13, -1 < m - 2n < 13, (29) v2 = 0, otherwise, where hm are dual scaling coefficients (10). The refinement coefficients for the left boundary functions of the first type are computed according to the proof of Lemma 3.1 in [17]. The refinement coefficients for the left boundary functions of the second type are given by definition (15). The matrix can be computed by the similar way. Since 1», = Qfe3 = Qf {M%)TQ3+1 = Qf (M%)T Qj+1$j+1, (30) the refinement matrix M3 0 corresponding to the dual scaling basis j is given by M,-,o = QJ+1M%Qj\ (31) 5. Construction of wavelets Our next goal is to determine the corresponding single-scale wavelet bases It is directly connected to the task of determining an appropriate matrices Mj i such that = Ml^J+1. (32) We follow a general principle called stable completion which was proposed in [3]. This approach was already used in [5, 17, 26]. In our case, however, the initial stable completion can not be found by the same way, because it leads to singular matrices. Definition 1. Any M^i : I2 i^Jj) —> I2 is called a stable completion of MJ)0, if IIMJ^ = O (1), \\MJ1\\ +i) = O (1), oo, (33) where Mj := (M3-0, Mjtl). The idea is to determine first an initial stable completion and then to project it to the desired complement space Wj. This is summarized in the following theorem [3]. 11 Theorem 2. Let j and j 6e a primal and a dual scaling basis, respectively. Let and M^o &e refinement matrices corresponding to these bases. Sup- pose that M^i is some stable completion of ~M.jp and Gj — M-1. Then Mm : (I M,AI;,JMm a/so a stable completion and Gj — Mj1 /ias the form G7-1 (34) (35) (36) (37) To find the initial stable completion we use a factorization M^o = HjCj, where Moreover, the collections form biorthogonal systems Hf H, / 0.25 0.875 0.25 0 0 0 V o (38) Hf H t (39) 1.2 0 1.8125 2 0 0 1.25 1 0 0 0.3125 0 / Matrix (Hj) has the size (2J+1 — 7) x (2J+1 — 9). Its elements are given by: (HO := 1, 1< n < 2J+1 - 9, n odd, m = n + 1 (40) :~ 1 — n — 2J+1 — 9, n even, —1 < m — n < 3, := 0, otherwise, 12 where = h{5 — 0.25, h\9 — h\A — 1, h\3 = 1.5, and 13 C,-: = /I 0 o\ 0 1 8 0 0 0 0 \o 0 5 / 6 := (41) (42) 6 8/ The factorization corresponding to inner and boundary blocks is not the same as the factorization in [15]. Therefore by our approach we obtain new inner and boundary wavelets. We define 10 0 0 ,BL := | 0 8 0 0 | ,BR := B 0 0 0 | (43) and / 0 0 b-1 0 0 0 0 0 0 0 b-1 0 o\ 0 0 0 J (44) (45) 13 /o 0\ /l o \ 1 O O O O O O 1 (46) \0 ij O V V The above findings can be summarized as follows. Lemma 3. The following relations hold: = I 0. (47) Now we are able to define the initial stable completions of the refinement matrices MJ)0. Lemma 4. Under the above assumptions, the matrices are uniformly stable completions of the matrices MJ)0. Moreover, the inverse of Mj = (Mj,o, Mj,i) is given by Gjfl = BjHj1, GJyl = FjHj1. The proof of this lemma is straightforward and similar to the proof in [17]. Then using the initial stable completion M^i we are already able to contruct wavelets according to the Theorem 2. Left boundary wavelets are displayed at the Figure 5. 5.1. Decomposition of a scaling basis on a coarse scale In the previous sections we assumed that the supports of the left and right boundary functions do not overlap and therefore the coarsest level was four. It might be too restrictive, especially in higher dimensions, because then there are many scaling functions. Here we decompose scaling basis 4 into two parts 3 and $3. It also improves the condition number of the basis. We construct wavelets on the level three to have four vanishing moments. Note that wavelets on other levels have six vanishing moments, but there the vanishing moments guaranties the smoothness of dual functions [10], and four M;i: H;F;. ./ •./„. (48) (49) 14 ^4,4 ^1 lr ^1 lr Figure 3: Left boundary wavelets for the scale j = 4. vanishing moments for wavelets are sufficient in the most of the applications. Scaling functions in 3 are defined by (9) for j — 3. Functions in $3 are defined by (5?J(4) (Bl)(4)\ fc = 1,...,8, xG [0,1], (50) 3f is a B-spline of order eight on the sequence of knots tj. and (4' denotes the fourth derivative. The sequences of knots tj. are given by: £1 = [0,0,1/32,1/16,1/8,2/8,3/8,4/8,5/8]; (51) t2 = [0,1/32,1/16,1/8,3/16,2/8,3/8,4/8,5/8]; £3 = [1/32,1/16,1/8,2/8,5/16,3/8,4/8,5/8,6/8]; £4 = [1/16,1/8,2/8,3/8,7/16,4/8,5/8,6/8,7/8]; £5 = [1/8,2/8,3/8,4/8,9/16,5/8,6/8,7/8,15/16]; £6 = [2/8,3/8,4/8,5/8,11/16,6/8,7/8,15/16,31/32]; t7 = [3/8,4/8,5/8,6/8,13/16,7/8,15/16,31/32,1]; £8 = [3/8,4/8,5/8,6/8,7/8,15/16,31/32,1,1]; Lemma 5. Functions from the set 3 U $3 generate the same space as functions from the set 4; i.e. span 3 U $3 = span $4. Functions ips^k, k — 1,..., 8; have four vanishing wavelet moments. 15 Proof. Since 4 is a basis of the space of all cubic splines on the knots t4 = [0, 0,1/32,1/16, 2/16,..., 15/16, 31/32,1,1]. Functions in $3 are cubic splines on the subsets of these knots. Functions in $3 are also cubic splines, because they are fourth derivative of the spline of order eight, and they are defined on the subsets of knots t4. Therefore $3 U $3 C span $4. Functions in $3 are linearly independent. Function ipsti cannot be written as linear combination of functions from $3 U f 3\ {ip3,i}, because it is a cubic spline on sequence of the knots tj containing an additional knot. Hence, $3 U 3 is a linearly independent subset of span $4, which proves the first assertion. To prove that the functions ips^k, k — 1,..., 8, have four vanishing moments, we use the integration by parts. We obtain for n — 0,... ,3: xn{Blp {x)dx nx"-1 (5t8J(3) (x)dx. (52) 0 Since (P>fk)is the spline of order 8 — n on the knots of multiplicity at most two in points 0 and 1, we have (5?J(n)(0)=(5?J(n)(l) = 0, n = 0, (53) and thus and (B?)^ (x)dx = 0 (54) xn{Blp {x)dx nx71-1 (Bfk)(3) (x) dx, n = 1,... , 3. (55) Using (53) and the integration by parts three times, we obtain: -{Blp{x)dx =(-!)»„! (5fJ(4-n)(l)-(5?Jl4-n,(0) =0, (56) « \(4-™) for n — 1,..., 3, which proves the assertion. □ Remark 2. In some constructions, the condition number of the wavelet basis is improved by orthogonalization of boundary wavelets or by the orthog-onalization of scaling functions on the coarsest level. In our case, the improvement was insignificant. 16 5.2. Norm equivalences It remains to prove that $ and $ are Riesz bases for the space L2 ([0,1]) and that properly normalized basis $ is a Riesz basis for Sobolev space Hs ([0,1]) for some s specified below. The proofs are based on the theory developed in [13] and [17]. For a function / defined on the real line a Sobolev exponent of smoothness is defined as sup{s : / G Hs (M)}. It is known that primal scaling functions extended to the real line by zero have the Sobolev regularity at least 7 = § and that dual scaling functions extended to the real line by zero have the Sobolev regularity at least 7 = 0.344. Theorem 6. i) The sets {$j} := {$j}j>jo anal := formly stable, i.e. are uni- CP\\HX3)< h4>],k feel,- < C \\b\\HX) for all b = {bk} G I2 {T3), j > j0. ii) For all j > j0, the Jackson inequalities hold, i.e. (57) inf - vA\ < 2-5J \\v\\Hs([m for all v G Hs ([0,1]) and s < N, (58) Vj^Sj and inf - Vj\\ < 2-5J \\v\\Hs([m for all v G Hs ([0,1]) and s < N. (59) in) For all j > j0, the Bernstein inequalities hold, i.e. \\vj\\hs([o 1]) ~ II^J'H for a^ vi e and s < 7, and (60) (61) Proof, i) Due to Lemma 2.1 in [17], the collections := i^i}j>j0 an<^ < :— \ are uniformly stable, if &j and j0 Ml ^ 4>j,k ^ 1, k G Xj, j > j0, (62) 17 and j and j are locally finite, i.e. # {A/ G X, : fc, n Qjtk + 0} < 1, for all fc G X,, j > j0, (63) and # jfc7 G X,- : fij>fc/ n fij>fc ^ 0j < 1, for all k G X,-, j > j0, (64) where Qj^ :— supp and Qj^ :— supp ^j.. By (23) the sets j and j are biorthogonal. The properties (62), (63), and (64) follow from (9), (11), and (18). ii) By Lemma 2.1 in [17], the Jackson inequalities are the consequences of i) and the polynomial exactness of primal and dual multiresolution analyses. iii) The Bernstein inequalities follow from i) and the regularity of basis functions, for details see [17]. □ The following fact follows from [13]. Corollary 1. We have the norm equivalences ]=]0 , (65) where v G Hs ([0,1]) and s G (—7,7). The norm equivalence for s — 0, Theorem 2, and Lemma 4, imply that $ := $jg u |j and * := ®jo U |j *j J=JO ]=]0 are biorthogonal Riesz bases of the space I? ([0,1]). Let us define D = (D x'x' \,\ej D A,A \,\€j. (66) (67) The relation (65) implies that D s$ is a Riesz basis of the Sobolev space Hs ([0,1]) for s G (-7,7). 18 6. Quantitative properties of constructed bases In this section, we compare quantitative properties of bases constructed in this paper, cubic spline-wavelet basis from [26] and cubic spline multiwavelet basis recently adapted to homogeneous boundary conditions in [28]. The condition of multi-scale wavelet bases is shown in Table 1. Our wavelet basis is denoted by CF, a basis from [28] is denoted by Schneider and a basis from [26] adapted to complementary boundary conditions by method from [18] is denoted by Primbs. The last basis is the same as the basis from [5] adapted to complementary boundary conditions by method from [18], see Remark 1. Other criteria for the effectiveness of wavelet bases is the condition number of a corresponding stiffness matrix. Here, let us consider the stiffness matrix: A*..= («fc.^»^.ra6*Al..- (68) It is well-known that the condition number of AJ0>S increases quadratically with the matrix size. To remedy this, we use a diagonal matrix for preconditioning - 'C (69) where DJ0)S = diag((^fe,^fe>1/2) . (70) In [7] the anisotropic wavelet basis were used for solving fourth-order problems. Here, we use isotropic wavelet basis, i.e. we define multiscale wavelet basis on the unit square by q>lDs = $j U % (g> (72) The symbol (g) denotes the tensor product. The preconditioned stiffness matrix 2£>A^esc for the biharmonic equation defined on the unit square is similar to the one dimensional case. Condition numbers of the stiffness matrices are listed in Table 1 and Table 2. The condition number of the stiffness matrix corresponding to wavelet basis by Primbs exceeds 104 already for number of levels j — 3. Wavelet basis from [17] adapted to complementary boundary conditions by method from [18] is very badly conditioned, its quantitative properties can be found in [28]. 7. Numerical example Now, we compare the quantitative behaviour of the adaptive wavelet method with our bases and bases from [28]. Both bases are formed by cubic splines and have local duals. We consider the equation A2u = f in Q, u = — = 0 on dQ, (73) on for Q — (0, l)2, where the solution u is given by u (x, y) — v (x) v (y), v (x) :— x2 f 1--—J . (74) Note that the solution exhibits a sharp gradient near the point [1,1]. We solve the problem by the method designed in [12] with the approximate Table 2: The condition of numbers of stiffness matrices of the size N x N for j levels. j N CF N Schneider 1 289 128.05 900 484.35 2 1089 141.28 3844 583.41 3 4225 212.01 15876 626.91 4 16641 257.56 64516 653.45 5 66049 281.21 260100 673.19 6 263169 297.23 1044484 689.43 7 1050625 306.12 4186116 703.42 20 10" 9 10" o 10" E 8, 10" -*-CF - e -Schneider 10 10 10 number of basis functions 10" I 10"4 10 -*-CF - © -Schneider 0 500 1000 1500 2000 2500 3000 number of iterations Figure 4: The convergence history for adaptive wavelet scheme with various wavelet bases. multiplication of the stiffness matrix with a vector proposed in [6]. We use wavelets up to the scale |A| < 10. The convergence history is shown in Figure 4. In our experiments, the convergence rate, i.e. the slope of the curve, is similar for both bases. However, they significantly differ in the number of basis functions and number of iterations needed to resolve the problem with desired accuracy. The number of basis functions was about 104 for an error in Z/°°-norm about 10~7. The number of all basis functions for full grid, i.e. basis functions on the level ten or less, is about 106, therefore by using an adaptive method the significant compression was achieved. It can seem that the number of iterations is quite large, but one could take into account that in the beginning the iterations were done for much smaller vector and the size of the vector increases successively. The algorithm is asymptotically optimal, i.e. the computational time depends linearly on the number of basis functions, see [12]. Acknowledgments: The authors have been supported by the project ESF "Constitution and improvement of a team for demanding technical computations on parallel computers at TU Liberec" No. CZ.1.07/2.3.00/09.0155. References [1] K. Bittner, Biorthogonal spline wavelets on the interval, in: Wavelets and Splines, Athens, 2005, Mod. Methods Math., Nashboro Press, Brentwood, TN, 2006, pp. 93-104. [2] N.M. Bujurke, C.S. Salimath, R.B. Kudenatti, S.C. Shiralashetti, A fast 21 wavelet-multigrid method to solve elliptic partial differential equations, Appl. Math. Comput. 185 (2007) 667-680. [3] J.M. Carnicer, W. Dahmen, J.M. Peňa, Local decomposition of refinable spaces, Appl. Comp. Harm. Anal. 3 (1996), 127-153. [4] D. Černá, V. Finěk, Optimized construction of biorthogonal spline-wavelets, in: T.E. Simos et al. (Eds.), ICNAAM 2008, AIP Conference Proceedings 1048, American Institute of Physics, New York, 2008, pp. 134-137. [5] D. Černá, V. Finěk, Construction of optimally conditioned cubic spline wavelets on the interval, Adv. Comput. Math. 34 (2011), 519-552. [6] D. Černá, V. Finěk, Approximate multiplication in adaptive wavelet methods, submitted. [7] D. Černá, V. Finěk, Adaptive wavelet method for fourth-order elliptic problems, in: T.E. Simos et al. (Eds.), ICNAAM 2011, AIP Conference Proceedings 1389, American Institute of Physics, New York, 2011, pp. 1606-1609. [8] X.F. Chen, J.W. Xiang, Solving diffusion equation using wavelet method, Appl. Math. Comput. 217 (2011) 6426-6432. [9] C.K. Chui, E. Quak, Wavelets on a bounded interval, in: Numerical Methods of Approximation Theory (Braess, D.; Schumaker, L.L., eds.), Birkháuser, 1992, pp. 53-75. [10] A. Cohen, I. Daubechies, J. C. Feauveau, Biorthogonal bases of compactly supported wavelets, Comm. Pure and Appl. Math. 45 (1995) 485-560. [11] A. Cohen, W. Dahmen, R. DeVore, Adaptive wavelet schemes for elliptic operator equations - convergence rates, Math. Comput. 70 (2001) 27-75. [12] A. Cohen, W. Dahmen, R. DeVore, Adaptive wavelet methods II - beyond the elliptic case, Found. Math. 2 (2002) 203-245. [13] W. Dahmen, Stability of multiscale transformations, J. Fourier Anal. Appl. 4 (1996) 341-362. 22 [14] W. Dahmen, B. Han, R.Q. Jia, A. Kunoth, Biorthogonal multiwavelets on the interval: cubic Hermite splines, Constr. Approx. 16 (2000) 221-259. [15] W. Dahmen, C.A. Miccheli, Banded matrices with banded inverses, II: locally finite decomposition of spline spaces, Constr. Appr. 9 (1993) 263-281. [16] S. Dahlke, W. Dahmen, K. Urban, Adaptive wavelet methods for saddle point problems - optimal convergence rates, SIAM J. Numer. Anal. 40 (2002) 1230-1262. [17] W. Dahmen, A. Kunoth, K. Urban, Biorthogonal spline wavelets on the interval - stability and moment conditions, Appl. Comp. Harm. Anal. 6 (1999) 132-196. [18] W. Dahmen, R. Schneider, Wavelets with complementary boundary conditions - function spaces on the cube, Results Math. 34 (1998) 255-293. [19] R.Q. Jia, S.T. Liu, Wavelet bases of Hermite cubic splines on the interval, Adv. Comput. Math 25 (2006) 23-39. [20] R.Q. Jia,, Spline wavelets on the interval with homogeneous boundary conditions, Adv. Comput. Math 30 (2009) 177-200. [21] R.Q. Jia, W. Zhao, Riesz bases of wavelets and applications to numerical solutions of elliptic equations, Math. Comput. 80 (2011) 1525-1556. [22] A. Khademi, K. Maleknejad, Filter matrix based on interpolation wavelets for solving Fredholm integral equations, Commun. Nonlinear Sci. Numer. Simul. 16 (2011) 4197-4207. [23] S.T. Liu, Y. Xu, Graded Galerkin methodds for high-order convection diffusion problem, Numer. Methods Partial Differential Eq. 25 (2009) 1261-1282. [24] K. Maleknejad, M.N. Sahlan, The method of moments for solution of second kind Fredholm integral equations based on B-spline wavelets, Int. J. Comput. Math. 87 (2010) 1602-1616. 23 [25] K. Maleknejad, M. Yousefi, Numerical solution of the integral equation of the second kind by using wavelet bases of Hermite cubic splines, Appl. Math. Comput. 183 (2006) 134-141. [26] M. Primbs, New stable biorthogonal spline-wavelets on the interval, Result. Math. 57 (2010) 121-162. [27] K. Sandeep, S. Gaurb, D. Duttac, H.S. Kushwahac, Wavelet based schemes for linear advectiondispersion equation, Appl. Math. Comput. 218 (2011) 3786-3798. [28] A. Schneider, Biorthogonal cubic Hermite spline multiwavelets on the interval with complementary boundary conditions, Result. Math. 53 (2009) 407-416. 24 November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'finek International Journal of Wavelets, Multiresolution and Information Processing (c) World Scientific Publishing Company WAVELET BASIS OF CUBIC SPLINES ON THE HYPERCUBE SATISFYING HOMOGENEOUS BOUNDARY CONDITIONS DANA ČERNÁ * and VÁCLAV FINĚK Department of Mathematics and Didactics of Mathematics, Technical University of Liberec Studentská 2, 461 17 Liberec, Czech Republic dana. cernaÚtul. cz vaclav. finek@tul. cz Received (Day Month Year) Revised (Day Month Year) Accepted (Day Month Year) Published (Day Month Year) In the paper, we propose a construction of a new cubic spline-wavelet basis on the hypercube satisfying homogeneous Dirichlet boundary conditions. Wavelets have two vanishing moments. Stiffness matrices arising from discretization of elliptic problems using a constructed wavelet basis have uniformly bounded condition numbers and we show that these condition numbers are small. We present quantitative properties of the constructed basis and we provide a numerical example to show an efficiency of Galerkin method using constructed basis. Keywords: Construction; Wavelet; Cubic spline; Homogeneous Dirichlet boundary conditions; Condition number; Elliptic problem; Galerkin method; Conjugate gradient method. AMS Subject Classification: 46B15, 65N12, 65T60 1. Introduction In this paper, we propose a construction of a new cubic spline wavelet basis on the hypercube that is well-conditioned, adapted to homogeneous Dirichlet boundary conditions and the wavelets have two vanishing moments. The wavelet basis of the space Hq (H), where il = (0, l)d and d £ N, is then obtained by a tensor product and a proper normalization. First of all, we summarize the desired properties of a constructed basis: - Riesz basis property. We construct Riesz basis of the space L2 (H) that, when normalized with respect to i^-seminorm, is also a Riesz basis of the space Hi (ÍÍ). * Corresponding author 1 November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'fmek 2 Dana Černá and Václav Finěk - Polymial exactness. Since the primal basis functions are cubic B-splines, the primal multiresolution analysis has polynomial exactness of order four. It means that all polynomials of degree less than four belong to the span of scaling functions at the given level. - Vanishing moments. The wavelets have two vanishing moments. - Locality. The primal basis functions are local in the sense of Definition 1.1 below. - Smoothness. Primal basis functions belong to C2 ($7) and dual basis functions belong to C($l), where C ($7) is the space of continuous functions on domain $1 and Cn (fi) is the space of functions on domain $1 that have continuous derivatives up to order nEl - Closed form. The primal scaling functions and wavelets are known in the closed form. - Homogeneous Dirichlet boundary conditions. Constructed wavelet basis satisfies homogeneous Dirichlet boundary conditions. - Well-conditioned bases. Our objective is to construct a wavelet basis that is well conditioned with respect to the L2-norm and is well conditioned with respect to the i^-seminorm, when normalized appropriately. We denote the Sobolev space or its subspace by H C Hs (fi) for nonnegative integer s and the corresponding inner product by {-,-}H, a norm by \\-\\H and a seminorm by \-\H. In case s = 0 we consider the space L2 (fi) and we denote by (■, ■} and ||-|| the L2-inner product and the L2-norm, respectively. Let J be some index set and let each index AG J take the form A = (j, k), where |A| := j £ Z is a scale. Let ^«2, for v = {vx}XeJ,vxeR, (1.1) and I2 (J) := {v : v = {vx}XeJ ,vxeR, ||v||2 < oo} . (1.2) Our aim is to construct a wavelet basis in the sence of the following definition. Definition 1.1. A family ^ := {ip\, A £ 3} is called a (primal) wavelet basis of H, if i) ^ is a Riesz basis for H, i.e. the closure of the span ofty is H and there exist constants c,C £ (0, oo) such that cllbll2 < , *s the support of ip\, and at a given level j the supports of only finitely many wavelets overlap at any point x e f2. For the two countable sets of functions T,fl C H , the symbol (r, fJ}^ denotes the matrix {T,il)H:={h,uj)H}^ribien. (1.4) Remark 1.1. It is known that the constants and from Definition 1.1 satisfy: C* = \JXmin {(<&,■<&}H), C* = \j\rnax (1.5) where Xmin ((*, V)H) and \rnax ((*,*> H) are the smallest and the largest eigenvalues of the matrix (>J7, ~^)H, respectively. Many constructions of spline wavelet or multiwavelet bases on the interval have been proposed in recent years.3'4'15'18'19'21 In Ref. 1, 2, 11, 17 cubic spline wavelets on the interval were constructed. In these cases dual functions are known and are local. Spline wavelet or multiwavelet bases where duals are not local are also known.5'12-15 The advantage of our construction in comparison with cubic spline biorthogonal wavelets with local duals1'2'11'17 is that the support of wavelets is shorter, condition numbers of the corressponding stiffness matrices are smaller and the advantage is also a simple construction. 2. Construction of scaling functions A primal scaling basis is the same as a scaling basis in Ref. 1, 17. It is generated from functions , 4>bi and 4>t2- Let 0 be a cubic B-spline defined on knots {0,1,2,3,4}. It can be written explicitly as: c) = < 1r> ze[o,i], -^ + 2a;2-2a;+§, xe [1,2], ,xe[2,3], xe [3,4], otherwise. %- - 4x2 + lfte - f c2 6 o, (2.1) Then satisfies a scaling equation1'17 4>(x 4>(2x) 4>(2x- 1) 300- | {2x-3) | {2x-4) (2.2) 8 2 4 Let 4>bi be a cubic B-spline defined on knots {0,0,0,1,2} and 4>b2 be a cubic B-spline defined on knots {0,0,1,2, 3}, i.e., 4>bi(x) 4 - 2f- + 3a;, x e [0,1 4 o, xe [1,2], otherwise, (2.3) November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'finek 4 Dana černá and Václav Finěk and 062 (z) = ' 3-ii# + ¥> ze [0,1], ~Y2~ ~\~ ~~2~ 2 i *^ ^ 7 ^] 7 fe^- a; e [2,3], 6 o, otherwise. .1, 17 Then f,i and 4>b2 satisfy scaling equations: , . , 061 (2a;) 3^fc2(2a;) , 30 (2a;) 061 (a;) = —-— + + 0,2 (2a;) , 110 (2a;) , 0 (2a; - 1) , 0 (2a; - 2) 0h? [Xj =----------. 4 16 2 8 For j e N, j > 3 and a; G [0,1] we set 0,-,fc (a;) = 2i/20(2^a; - fc), fc = 3, S^fc V^v = z ' (^z x — fi;^, ň; = o, . . . z — ±, (a;) = yVfo^yx), 0,-,2,+i (a;) = 2^2«fo(2^(1 - a;)), (a;) = 2'l2j,k/ \\4>j,k\\ , = 1,..., 2j + 1} and Vj = span$^. v / The sets $ ^ are uniform Riesz bases of the space Vj. It means that the sets $ ^ are Riesz bases of the space Vj with Riesz bounds independent on j. The proof can be found in Ref. 1. The graphs of the functions 4>j,k on the coarsest level j = 3 are are be found in displayed in Figure 1 Fig. 1. Functions 03tfc, k — 1,... ,9. November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'fmek Wavelet basis of cubic splines on the hypercube satisfying homogeneous boundary conditions 5 3. Construction of wavelets In some applications such as adaptive wavelet methods,6'7 vanishing moments of wavelets are needed. In our case, we construct wavelets with two vanishing moments, i.e. xkip(x)dx = 0, k = 0,l. (3.1) We set Vj as the space of continuous piecewise linear function: v, = C(o,i)n -+T), (3.2) fc=0 ^ ' where P\ (a, 6) is the space of all algebraic polynomials on (a, 6) of degree less or equal to 1. Clearly, with this choice the dimension of Vj is 23 +1 that is the same as the dimension of Vj. We construct wavelets 'ipj:k, k = 1,..., 23, such that ipj^ £ Vj+i and 'i>j,k,4>)=0 (3.3) for all functions £ V}, because then (3.1) will be satisfied. Since we want ipj^ £ Vj+i, we define a generator wavelet as 6 ip{jx) = YJ9k^{2x-k), (3.4) fc=0 and -1 7 -119 1 -119 7 -1 (3.5) The coefficients are computed such that (ip,ui) = 0 for all functions ui that are continuous and are linear on intervals [k, k + 1], k £ Z. Then for rl>jlk(x) = 2j'2i>(2jx -k + 2), k = 3,2j - 2, j £ N, j > 3, (3.6) the condition (3.3) is satisfied and the functions and ipj^ have two vanishing wavelet moments. The support of the wavelet is [0,5]. The graph of is shown in Figure 2. We define boundary wavelets ipbi and ipt,2 by: Mx) = gfrfoipx) + gf^{2x) + YJ9hk^x -k + 2), (3.7) fc=2 6 VtaCz) = 9o2M2x) + gf4>b2(2x) + ^9^^ -k + 2), November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'finek 6 Dana Černá and Václav Finěk Fig. 2. Wavelets ip, tp^i and ipb2- where -,9? „f>2 9o >■ • ,9e 939 -393 6233 -4,1 70 20 560 2770661 256057 -493633 20761777 -76369591 „ _ _ _ _ _ 7 _3 1828560'457140' 76992 ' 1828560' 7314240 ' ' (3.8) Then suppf,i = [0,3], suppf,2 = [0,4] and both boundary wavelets have two vanishing moments. For j £ N, j > 3 and x £ [0,1] we define ij^(x) = y/2xi>bl{yx), Vi,»- (x) = 2^/2^(2^(1 - x)), (3.9) and % = {V'i,fc/IIV'i,fc||,fe = l,---,2i}, =span^. (3.10) We denote 2+s oo *s = $3u(J% and $ = $3 U [J f j. (3.11) 3=3 3=3 In the following, we prove that !P is Riesz basis of the space L2 (0,1). The set !PS is a finite dimensional approximation of !P. Theorem 3.1. The sets tyj, j > 3, are uniform Riesz bases ofWj. Proof. We computed the matrix ľ : ^3} (3.12) November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'finek Wavelet basis of cubic splines on the hypercube satisfying homogeneous boundary conditions 7 using (3.4) and (3.7). For example, for j = 3 we obtained (3.13) where the numbers are rounded to three decimal places. The matrix Fj for j > 3 has the similar structure. The first two rows and columns and the last two rows and columns corresponds to boundary wavelets and for k,l = 3,.. .23 — 2: 1, k = l, -0.029, \k-l\ = 1, < -0.077, \k-l\ =2, (3.14) -0.001, \k-l\ =3, 0, otherwise. /1.000 0.128 0.103 0.003 0 0 0 0\ 0.128 1.000 0.432 -0.145 -0.014 0 0 0 0.103 0.432 1.000 -0.029 -0.077 0.001 0 0 0.003 -0.145 -0.029 1.000 -0.029 -0.077 -0.014 0 0 -0.014 -0.077 -0.029 1.000 -0.029 -0.145 0.003 0 0 0.001 -0.077 -0.029 1.000 0.432 0.103 0 0 0 -0.014 -0.145 0.432 1.000 0.128 \ o 0 0 0 0.003 0.103 0.128 1.000 / ■ "J>k,l It is easy to see that Fj is banded and diagonally dominant. Estimates for the smallest eigenvalue XJmin and the largest eigenvalue X?max of the matrix Fj can be computed using the Gershgorin circle theorem: Kaax < max 4 -Ep&i i>0-2' fc=i n \Fu \ + E\Ftk fc=i < 1.8, (3.15) (3.16) (3.17) where F\k are the entries of the matrix Fj. With the help of Remark 1.1 the assertion is proven. □ The proof that !P is a Riesz basis is based on the following theorem.8'12 Theorem 3.2. Let J £ N and let Vj and Vj, j > J, be subspaces of L2 (0,1) such that Vj C Vj+i, Vj C Vj+i, dimVj = dimVj < 00, j > J. (3.18) Let <&j be uniform Riesz bases ofVj, $y be uniform Riesz bases ofVj, tyj be uniform Riesz bases ofV^CiVj+i, where Vf~ is the orthogonal complement ofVj with respect to the L2-inner product, and let (3.19) November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'finek 8 Dana Černá and Václav Finěk Furthermore, let the matrix (3.20) be invertible and the spectral norm of Gj 1 is bounded independently on j. In addition, for some positive constants C, 7 and d, 7 < d, let and for 0 < s < 7 let inf \\v - Vj\\ < C2-jd ||v||^rf(0jl) , v £ Hq (0,1 11^11^(0,1) — <^^3S ll^ll ' vi e (3.21) (3.22) and let similar estimates (3.21) and (3.22) hold for 7 and d on the dual side. Then there exist constants k and K, 0 < k < K < 00, such that k ||b||2 < j,k,k = l,...,2j} (3.24) that is a Riesz basis of the space Vj. Recall that Vj is denned by (3.2). Let ' x + i, x e [-1,0], i-x,xe[o, 1], 0, otherwise, and for x £ [0,1] we define Then 4fc (x) = yl24> (2jx - k) , k = 1,..., 2j! - 1, 4>jtk (x) = 2<-j+1^24) (2jx -k),k = Q,2j. {^k,k = 0,...,2j} (3.25) (3.26) (3.27) (3.28) are uniform Riesz basis of the space Vj.1 November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'fmek Wavelet basis of cubic splines on the hypercube satisfying homogeneous boundary conditions 9 The matrix G has the structure 17 40 11 40 11 80 0 0 0 0 o\ 19 120 9 20 17 80 11 120 0 0 0 0 1 60 13 60 11 20 13 60 1 120 0 0 0 0 1 13 11 13 1 0 120 60 20 60 120 0 0 1 13 11 13 1 0 120 60 20 60 120 0 1 13 11 13 1 120 60 20 60 60 0 11 17 9 19 120 80 20 120 0 11 80 11 40 11, 40 / (3.29) V It is easy to verify that the matrix Gj is banded and strictly diagonally dominant. Therefore, it is invertible and the spectral norm of G.71 is bounded independently on j. It is known8 that when 7 is the Sobolev exponent of smoothness of the basis functions and d is the polynomial exactness of Vj than (3.21) and (3.22) are satisfied. In our case, the Sobolev exponent of smoothness is 7 = 3.5 and the polynomial exactness of Vj is d = 4. On the dual side, 7 = 1.5 and d = 2. Therefore, due to Theorem 3.2, the norm equivalence (3.23) is satisfied for s £ (—1.5,3.5). Since we proved that (3.23) holds for s = 0, the set !P is indeed a wavelet basis of the space £2(0,1). □ It remains to prove that when the wavelet basis !P is normalized in the H1-seminorm, then it is a wavelet basis of the space Hi (0,1). We denote I3 :={0,1,...,8} and Jj := {l,. ..,$>} . (3.30) Theorem 3.4. The set [ J > 3,fc £ j (3.31) is a wavelet basis of the space Hq (0,1). Proof. We follow the Proof of Theorem 2 in Ref. 3. From the proof of Theorem 3.3, we know that the relation (3.23) holds for s = 1. Therefore the set {2-3 3,k £ Jj} (3.32) is a wavelet basis of the space H^ (0,1). From (2.6), (3.6) and (3.9) there exist nonzero constants C\ and C2 such that and Ci2J'<|Vj,fc|Hi(n)3, k £ Jj, (3.33) Ci23 < \ 3, k G Jľ}| be such that (3.35) We define 23ä3 fc ß3,fc = 77—i—!-> fe £ 2-3, &j,fc 2^5 IV3.fclii^(0,l) l^'.fclii^(0,l) and b = {03^, fe G I3} U {bj:k,j > 3, fc £ J}}. Then llbll Hb||2 < ^ < 00. , j > 3, fe G J,-, (3.36) (3.37) Since (3.32) is a Riesz basis of (0,1) there exist constants C3 and C4 such that C3||b||2< Therefore fcex3 kejj,j>3 C4||b||2> fcex3 kejj,j>3 (3.39) tt-i-4>3,k + 2_ H-i-'^'fc fcÖ3 l^.fc lífi(0,l) fce^,j>3 m^Hi(o,i) H* (0,1) and similarly c3 ■■ ■■ c2\\h\\^ a3,k ^ ^3,^1^1(0,1) 3,fc+ 51 "3,k k&J,,j>3 l^'^liíoHO,!) (3.40) if 1(0,1) It is known1'16 that an orthogonalization of the scaling functions on the coarsest level can lead to improved quantitative properties of the resulting wavelet basis. Therefore, we define the set ort _ ( jjjrt by K-^a, K=($3,$3 Then the set of scaling functions ^rt is orthonormal and CO (3.41) (3.42) (3.43) J=3 is a wavelet basis of the space L2 (0,1) and its appropriate rescaling is a wavelet basis of the space Hq (0,1). November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'fmek Wavelet basis of cubic splines on the hypercube satisfying homogeneous boundary conditions 11 4. Multivariate wavelets We present two well-known constructions of multivariate wavelet bases on the unit hypercube.22 They are both based on tensorizing univariate wavelet bases and preserve Riesz basis property, locality of wavelets, vanishing moments and polynomial exactness. 4.1. Anisotropic construction For notational simplicity, we denote V2,fc kej2:=l3 (4.1) and J:={{j,k), j>2, kejj}. (4.2) Then we can write *or* = {^,fc, 3 > 2, k e Jj} = {Va, A G J}. (4.3) Recall that for A = (j, k) we denote A = j. We use wgiv to denote the tensor product of functions u and v, i.e. (u ® v) (xi,x2) = u (xi) v (x2). We define multivariate basis functions as: ip\ = ®t=1ipxi, A= (Al5..., Ad) e J, J = Jd = J® ...®J. (4.4) Since tyort is a Riesz basis of L2 (0,1) and ~>$>ort normalized with respect to H1-seminorm is a Riesz basis of Hq (0,1), the set *oni:={^,AeJ} (4.5) is a Riesz basis of L2 (fi), = (0, l)d, and its normalization wr*—'AGJI <46> IWifi((0,l)d) J is a Riesz basis of Hq (fi). The set *™=={V'A,A=(Ai)...)Ad)) |Ai|<2 + s} (4.7) is a finite-dimensional approximation of tyant, 4.2. Isotropic construction We define for j > 3 and k = (ki,... kj) multivariate scaling functions: 4>jM-=®ti4>JM, (4-8) and $}s° := {j,k,e = ®f=ltso. 5. Quantitative properties In this section, we present the condition numbers of the stiffness matrices for the following elliptic problem: —eAu + au = f on fi, u = 0 on díl, (5-1) where A is the Laplace operator, e and a are positive constants. The variational formulation for an anisotropic wavelet basis is where u .— (VLaniyr -qjani fani — (^j •qjani'j An advantage of discretization of elliptic equation (5.1) using a wavelet basis is that the system (5.2) can be simply precondtioned by a diagonal preconditioner.10 Let November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'fmek Wavelet basis of cubic splines on the hypercube satisfying homogeneous boundary conditions 13 D be a matrix of diagonal elements of the matrix A, i.e. D^lM = A\:I1S\:I1, where S\:M denotes Kronecker delta. Setting we obtain the preconditioned system Aamuam = fam. It is known10 that condAQni < C < oo. (5.5) Let uani = (uam)T ^,am fam = ^ ^amN, _ and let D™ be a matrix of diagonal elements of the matrix A°m, i.e. (D™)A = (A™)^^. We set Aasni := (D^™) "1/2 A^ni (DrO _1/2 , (5.7) -am__/-r\ani\l/2 ani cani__/-p*am'\ —1/2 cani and obtain preconditioned finite-dimensional system (5.8) Since A°"! is a part of the matrix Aam that is symmetric and positive definite, we have also condA°™ 1 by i — l h. (6.2) u,-_i, i = l,...,kj, 0, i — kj,..., kj+i, where k3 = (2j+2 + l)2. A criterion ||r^|| < e3, where t3 : = A*soUj—fjso, is used for terminating iterations of conjugate gradient (CG) method at level j. It is possible to choose smaller e3 on coarser levels,13 but in our case we choose t3 constant for all levels, because other choices of e3 did not lead to significantly smaller number of iterations in our experiments. The method for anisotropic wavelet basis is similar. We denote the number of iterations on the level j as M3. It is known22 that one CG iteration requires O (N) floating-point operations, where N x N is the size of the matrix. Therefore the number of operations needed to compute one CG iteration on the level j requires about one quarter of operations needed to compute one CG iteration on the level j + 1, we compute the total number of iterations by 3=0 The results are listed in Table 6 and Table 7. The residuum is denoted r„, u is the exact solution of the given problem and us is an approximate solution obtained by multilevel Galerkin method with s levels of wavelets. It can be seen that the number of conjugate gradient iterations is quite small and that IK - wIL Iks - «11 i la .s (6.4) IK+i - ulloo IK+i-m|I 16 i.e. that order of convergence is 4. It confirms the theory. Table 6. Number of iterations and error estimates for multilevel conjugate gradient method for isotropic wavelet basis. s N M ||rs|| ||ws — u|| ||us — u\ 1 289 17.00 1.00e-6 1.02e-5 2.95e-6 2 1 089 17.06 1.51e-7 6.95e-7 2.49e-7 3 4 225 16.75 1.29e-8 4.83e-8 1.61e-8 4 16 641 15.31 1.78e-9 2.87e-9 9.92e-10 5 66 049 14.48 1.59e-10 1.79e-10 6.18e-ll 6 263 169 12.77 3.21e-ll 1.12e-ll 3.77e-12 7 1 058 841 12.16 3.11e-12 1.38e-12 6.45e-13 November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'flnek Wavelet basis of cubic splines on the hypercube satisfying homogeneous boundary conditions 17 Table 7. Number of iterations and error estimates for multilevel conjugate gradient method for anisotropic wavelet basis. s N M ||r-|| \\us - u\\ \\us - u\ 1 289 9.25 8.15e-6 1.03e-5 2.97e-6 2 1 089 11.13 1.16e-6 7.10e-7 2.49e-7 3 4 225 11.42 1.33e-7 4.91e-8 1.62e-8 4 16 641 12.05 1.32e-8 2.90e-9 9.93e-10 5 66 049 12.14 1.31e-9 1.76e-10 6.20e-ll 6 263 169 11.95 1.32e-10 1.14e-ll 3.78e-12 7 1 058 841 11.98 1.46e-ll 1.24e-12 6.01e-13 Acknowledgments The authors have been supported by the project "Modern numerical methods" No. 5844/16 financed by Technical University in Liberec. The authors would like to thank T. Šimková for her help with numerical experiments. References 1. D. Černá and V. Finěk, Construction of optimally conditioned cubic spline wavelets on the interval, Adv. Corn-put. Math. 34 (2011) 219-252. 2. D. Černá and V. Finěk, Cubic spline wavelets with complementary boundary conditions, Appl. Math. Comput. 219 (2012) 1853-1865. 3. D. Černá and V. Finěk, Quadratic spline wavelets with short support for fourth-order problems, to appear in Result. Math. ,66 (2014) 525-540. 4. D. Černá and V. Finěk, Cubic spline wavelets with short support for fourth-order problems, Appl. Math. Comput. 243 (2014) 44-56. 5. C.K. Chui and E. Quak, Wavelets on a bounded interval, in Numerical Methods of Approximation Theory, eds. D. Braess, D. and L.L. Schumaker), (Birkháuser Verlag, 1992), 53-75. 6. A. Cohen, W. Dahmen and R. DeVore, Adaptive wavelet schemes for elliptic operator equations - convergence rates, Math. Comput. 70 (2001) 27—75. 7. A. Cohen, W. Dahmen and R. DeVore, Adaptive wavelet methods II - beyond the elliptic case, Found. Math. 2 (2002) 203-245. 8. W. Dahmen, Stability of multiscale transformations, J. Fourier Anal. Appl. 4 (1996) 341-362. 9. W. Dahmen, B. Han, R.Q. Jia, and A. Kunoth, Biorthogonal multiwavelets on the interval: cubic Hermite splines, Constr. Approx. 16 (2000) 221—259. 10. W. Dahmen and A. Kunoth, Multilevel preconditioning, Numer. Math. 63 (1992) 315-344. 11. W. Dahmen, A. Kunoth, and K. Urban, Biorthogonal spline wavelets on the interval - stability and moment conditions, Appl. Comp. Harm. Anal. 6 (1999) 132—196. 12. T.J. Dijkema and R. Stevenson, A sparse Laplacian in tensor product wavelet coordinates, Numer. Math. 115 (2010) 433-449. 13. R.Q. Jia and S.T. Liu, Wavelet bases of Hermite cubic splines on the interval, Adv. Comput. Math 25 (2006) 23-39. 14. R.Q. Jia, Spline wavelets on the interval with homogeneous boundary conditions, Adv. November 18, 2014 13:27 WSPC/WS-IJWMIP cerna'finek 18 Dana černá and Václav Finěk Comput. Math 30 (2009) 177-200. 15. R.Q. Jia and W. Zhao, Riesz bases of wavelets and applications to numerical solutions of elliptic equations, Math. Comput. 80 (2011) 1525-1556. 16. R. Pabel, Wavelet methods for PDE constrained elliptic control problems with Dirich-let boundary control, Thesis, Universität Bonn (2005). 17. M. Primbs, New stable biorthogonal spline-wavelets on the interval, Result. Math. 57 (2010) 121-162. 18. S.M. Quraishi and K. Sandeep, New bi-cubic spline wavelet based thin plate finite elements, Int. J. Multiscale Comput. Eng., DOI: 10.1615/IntJMultCompEng.2014002616 19. S.M. Quraishi and K. Sandeep, New cubic Hermite finite element wavelets with improved properties, Int. J. Wavelets Multiresolut. Inf. Process. 20. A. Schneider, Biorthogonal cubic Hermite spline multiwavelets on the interval with complementary boundary conditions, Result. Math. 53 (2009) 407—416. 21. A. Tavakoli and F. Zarmehi, Construction of the matched multiple knot B-spline wavelets on a bounded interval, Int. J. Computer Math., DOI: 10.1080/00207160.2014.960403 22. K. Urban, Wavelet methods for elliptic partial differential equations, Oxford University Press, Oxford, 2009. Results in Mathematics manuscript No. (will be inserted by the editor) On a sparse representation of a n-dimensional Laplacian in wavelet coordinates Dana Cerna • Vaclav Finek Received: date / Accepted: date Abstract Important parts of adaptive wavelet methods are well conditioned wavelet stiffness matrices and an efficient approximate multiplication of quasi sparse stiffness matrices with vectors in wavelet coordinates. Therefore it is useful to develop a well conditioned wavelet basis with respect to which both the mass and stiffness matrices are sparse in the sense that the number of nonzero elements in any column is bounded by a constant. Consequently, the stiffness matrix corresponding to the n-dimensional Laplacian in tensor product wavelet basis is also sparse. Then, a matrix-vector multiplication can be performed exactly with linear complexity. In this paper, we construct a wavelet basis based on Hermite cubic splines with respect to which both the mass matrix and the stiffness matrix corresponding to one dimensional Pois-son equation are sparse. Moreover, a proposed basis is very well conditioned on low decomposition levels. Small condition numbers for low decomposition levels and a sparse structure of stiffness matrices are kept for any well conditioned second order partial differential equations with constant coefficients and moreover they are independent of the space dimension. Keywords Wavelet ■ Riesz bases ■ Cubic Hermite spline ■ Homogeneous Dirichlet boundary conditions ■ Condition numbers ■ Sparse representations Mathematics Subject Classification (2000) 15A12 ■ 41A15 ■ 65F50 ■ 65N12 ■ 65T60 The authors have been supported by the SGS project "Numerical Methods II". D. Černá Department of Mathematics and Didactics of Mathematics, Technical University of Liberec, Studentská 2, 461 17 Liberec, Czech Republic V. Finěk Department of Mathematics and Didactics of Mathematics, Technical University of Liberec, Studentská 2, 461 17 Liberec, Czech Republic E-mail: Vaclav.Finek@tul.cz 2 Dana Černá, Václav Finěk 1 Introduction A general concept for solving of operator equations by means of wavelets was proposed by A. Cohen, W. Dahmen and R. DeVore in [8,9]. It consists of the following steps: transformation of the variational formulation into the well conditioned infinite-dimensional problem in the space I2, finding of the convergent iteration process for the I2 — problem and finally a derivation of its computable version. The aim is to find an approximation of the unknown solution u which should correspond to the best Y-term approximation, and the associated computational work should be proportional to the number of unknowns. Essential components to achieve this goal are well conditioned wavelet stiffness matrices and an efficient approximate multiplication of quasi-sparse wavelet stiffness matrices with vectors. In [8], authors exploited an off-diagonal decay of entries of the wavelet stiffness matrices and designed a numerical routine APPLY which approximates the exact matrix-vector product with the desired tolerance e and that has linear computational complexity, up to sorting operations. The idea of APPLY is following: To truncate A in scale by zeroing a,ij whenever 5(i,j) > k (S represents the level difference of two functions in the wavelet expansion) and denote resulting matrix by Ak. At the same time to sort vector entries v with respect to the size of their absolute values. One obtains vk by retaining 2fc biggest coefficients in absolute values of v and setting all other equal to zero. The maximum value of k should be determined to reach a desired accuracy of approximation. Then one computes an approximation of Av by w := Akv0 + Ak_i(vi - v0) + ... + A0(vk - vk_i) (1) with the aim to balance both accuracy and computational complexity at the same time. In [16], binning and approximate sorting strategy was used to eliminate these sorting costs and then an asymptotically optimal algorithm was obtained. The idea is following: Reorder the elements of v into the sets Vo, • • •, Vq, where v\ £ V-i if and only if 2~i_1 ||v||;2 < vx < ||v||;2 , 0 < i < q. Eventual remaining elements are put into the set Vq. And subsequently to generate vectors vk by successively extracting 2fc elements from \J{ Ví, starting from Vo and when it is empty continuing with V\ and so forth. Finally the scheme (1) is applied. Further improvements of this scheme were proposed in [4,12]. Although the APPLY routine has optimal computational complexity, its application is relatively time consuming and moreover it is not easy to implement it efficiently. It is well known, that condition numbers of stiffness matrices in wavelet coordinates depend on Riesz constants of a wavelet basis. Before we explain it in more detail, we start with a definition of a wavelet basis. We consider here families & = {ip\, A £ J\ C ^(0,1) of functions (wavelets) where J is an infinite index set and J = J® U where J$ is a finite set representing On a sparse representation of a n-dimensional Laplacian in wavelet coordinates 3 scaling functions living on the coarsest scale. Any index A £ J is of the form A = (j,k), where |A| = j denotes a scale and k denotes spatial location. The above notation enables us to write wavelet expansions as d7> := £ d\ip\. At last, for s > 0 the space Hs will denote a closed subspace of the Sobolev space Hs (0,1), defined e.g. by imposing homogeneous boundary conditions at one or both endpoints, and for s < 0 the space Hs will denote the dual space Hs := (H~s)'. \\-\\HS will denote the corresponding norm. Further hiJ-) will denote the space consisting of the power summable sequences and ||- H^^) will denote the corresponding norm. A family }P = {ip\, A £ J\ C -£2(0,1) is called a wavelet basis of Hs for some 7,7 > 0 and s £ (—7,7), if — }P normalized in Hs is a Riesz basis olHs, that means }P forms a basis olHs and there exist constants cs, Cs > 0 such that for all b = {b\}Xej £ h (J) holds , , A(a;) dx < 2-m^ \v\Hm(0 x) , V« £ Hm (0,1). 0 It means that integration against wavelets eliminates smooth parts of functions and it is equivalent with vanishing wavelet moments of order m. We consider here the following Dirichlet problem u - E —= / in Q = (0, l)d with u = 0 on df2 (3) i=i &xi for given / £ H^1 (i?) . A Riesz wavelet basis for (i?) can be constructed by a tensor product of univariate Riesz wavelet bases. Indeed, let }P = {ip\, A £ J\ be after appropriate normalization a Riesz wavelet basis for spaces £2(0,1) and #o(0,l) then 4 Dana Černá, Václav Finěk is a Riesz basis for Hq (i?) (see [14]) with the Riesz constants (see [12] mm (c0,cijc0 XeJd ir!(ß) (5) Vfo £ I2 (Jd) 5 where constants cq, Co, ci, C\ are Riesz constants with respect to spaces L2 and H\, respectively. Writing u = uT\)]\eJd, XeJd then an equivalent formulation of (3) is Au = f with A = D 1 (M®...®M + S®...®M-\-----h M ® ... ® S), (6) where D = diag |\\®j=1ipxm\\Hl{n)\, and 1 dj>\ dj>ß o dx dx dx and M : ipx ipß dx (7) are the one-dimensional stiffness and the mass matrices, respectively. Then (5) implies cond(A) H1 by A(u)(v) = a(u,v) MveH, and then (8) is equivalent to A(u) = f. (9) If a is H—elliptic, then there exist positive constants c_4, such that ca\\v\\u < \\A(v)\\w 1, let Vn be the space of piecewise cubic splines v £ C1(0, l)nC[0,1] for which v(0) = v(l) = 0. The dimension of Vn is 2™+1 and the set 1. This property ensures that both the mass and stiffness matrices corresponding to the one-dimensional Laplacian have at most three wavelet blocks of nonzero elements in any column and then the number of nonzero elements in any column is bounded independently of matrix size. The first two wavelets have supports in [—1,1] and are uniquely determined by their orthogonality to cubic polynomials and by imposing that the first one is odd and the second one is even: Vi(a;) = 2(2x - 1). The second two wavelets have supports in [—2,2]. And we impose on them again the above orthogonality condition which will be ensured by requiring that they are orthogonal to cubic polynomials on intervals [—2,0] and [0,2], respectively. Again one of them should be odd and the second one even. There remains several free parameters. To obtain a more sparse stiffness matrix and a better conditioned wavelet basis, we use these free parameters to prescribe the orthogonality of the first derivative of constructed wavelets to the first derivative of the first two wavelets. We obtain these two wavelets: On a sparse representation of a n-dimensional Laplacian in wavelet coordinates 7 151 2 281 ^x) = ~m^l{2x + 3) + 5M2x + 2) ~ 4soM2x + + M2x) 281 , . 2 , 151 "48O0l(2x ~ 1} + 50l(2x ~ 2) ~ 480M2X ~ 3) -gi^2(2x + 3) + ^02(2a; + 2) - ^02(2* + 1) 1551 , . 79 , . 711 , H--02 2a; - 1)--4>2(2x - 2) H--02 2a; - 3), 224 ^v 7 56 V ' 22V v 7' 7 19 163 v-4(z) = ^01 (2x + 3) - -0i(2a; + 2) + ^i(2x — 1) and 02(2a; — 1), and moreover they also will be also mutually orthogonal. And we obtain 4 4 03(a;) = g02(a; + 1)l[—1,1] + chi.x) + -^{x - 1)|[—1,1], 4>A{x) = -1202(a; + l)|[_i,i] + 0i(a;) + 1202(a; - 1)|[-1,1]• Fig. 4 The modified boundary scaling functions 03 and 04. Now a basis of the space V\ is defined by $! := {0i(2a; - 1), 02(2a; - 1), 03(2a; - 1), 04(2a; - 1)} . To further improve condition numbers of the constructed basis, we construct new basis functions for the space W\. The first two wavelets will be orthogonal to scaling functions from the space Vi, will not depend on the boundary scaling functions from the space V2 and one of them will be odd and the second one even. We obtain these two wavelets: 794 8793 8793 4>5{x) = 0i(2a; + l)- —01(2a;) + 01(2a;-l) + —02(2a; + l)--—-02(2a;-l), On a sparse representation of a n-dimensional Laplacian in wavelet coordinates 9 143 52 143 Mx) = -M2x + l)+M2x-l)-—M2x + l)-—M2x)-—M2x-l). Fig. 5 The first two modified wavelets ip§ and ip&. The second two wavelets will be again orthogonal to scaling functions from the space V\ and moreover will be orthogonal to the first two newly constructed wavelets. Again one of them will be odd and the second one even. Then we obtain: 144 275 Mx) = 2(2x + 1) Ml- 144 , , .. 275 ■ —02(2a; + 2)|[_i,i] - - - 68 , x 275 , . 144 , - — 5(2x - 1), i/>6{2x - 1), v7(2x - 1), v>8(2x - 1)} 10 Dana Černá, Václav Finěk and a basis of the space #o(0,l) is denned by CO 9 = $1U$1\J^j. (11) 3=2 A sparsity patterns for the mass matrix M and for the one dimensional stiffness matrix S, respectively, denned in (7) can be seen in Figure 2. In the next section, we prove that it is a wavelet basis. 3 Properties of the constructed basis To proof that the constructed basis forms a Riesz basis of the space Hq (0,1), we use the following theorem from [13] which summarizes results from [10,11]: Theorem 1 Let jo be the coarsest level and let Vj0 C Vj0+1 C...C L2(0,1), Vj0 C Vj0+1 C...C L2(0,1) be sequences of primal and dual spaces with dim Vj = dim Vj such that for uniform L2(0,1)— Riesz bases 1, let Vj be the space of piecewise cubic functions on intervals [k2~i+1, (k + 1)2^+1] for h = 0,..., 2'-1 - 1. Then dimension of Vj is apparently 2J+1 and from the construction immediately follows that Wj = vJ+1nv3 ±l2(0,1) Now, we construct uniform £2(0,1)—Riesz bases i(2x), 02(2a;), 4>i(2x — 1), and 02(2a; — 1) which span the space of C1(0,1) cubic splines on the interval [0,1] and with functions 0i(-) := (a; —1/2)*| [0,i] for i = 0,1, 2, 3 which span the space of piece-wise cubic functions on [0,1]. Further we apply a number of transformation at the both bases to obtain a sparse and strictly diagonally dominant matrices $3 A £2(0,1) ax(2x - 1) We keep the functions (2a;-1) and a2(2a;-l) (2a;-1) which are supported in the interval [0,1]. 12 Dana Černá, Václav Finěk Fig. 8 The first two primal basis functions a\ and c*2. In the second step, we construct the first two dual basis functions in a such a way that these new dual basis functions are orthogonal to the first two primal basis functions. Moreover the first new dual function is a linear combination of even polynomials while the second one is a linear combination of odd polynomials. After appropriate normalization, we obtain and Fig. 9 The first two dual basis functions (3\ and /32. In the third step, we construct the second two new primal basis functions as a linear combination of functions (j)i(2x), (f>2(2x), 4>i(2x—1), 4>2(2x — 1), 4>i(2x — 2), and 4>2{2x — 2) in such a way that these new primal basis functions are orthogonal to dual functions f3i(x), ^(x), f3i(x — 1), and ^(x — 1). Moreover, we require that the first new primal basis function is even with respect to the point x = 1, and the second one is odd with respect to the point x = 1. We obtain a3(2x) := 0i(2x) + 40i(2a; - 1) + 0i(2a; - 2) On a sparse representation of a n-dimensional Laplacian in wavelet coordinates and a4(2x) := 4>2(2x) + — 2{2x - 1) + (t>2(2x - 2). o 13 In the fourth step, we construct_the second two new dual basis functions as a linear combination of functions i(x) and i(x + 1) for i = 0,1, 2,3 in such a way that these functions are orthogonal to functions a\{2x — 1), «2(22; — 1), a\{2x + 1), and «2(22; + 1). Moreover, we require that the first new dual basis function is orthogonal to functions «4(22; — 1), «4(22; + 1), and «4(22; + 3) and the second one is orthogonal to functions «3(22; — 1), «3(22; + 1), and «3(22; + 3). After appropriate normalization, we obtain Then for j > 1, we define collections of functions $j : = [v/2^a4(2^ + l)|[0]1],v/2^ai(2^-l^ V23-1a3(2jx - 1), V23-1ai(2jx - 1), V2i-1a1(2jx - 3), V23-1a2(2jx - 3),..., V23-1a1(2jx - 2j + 1), V2^a2(2jx - 2j + 1), V2^a4(2jx - 2j + l)|[0,i] } , 14 Dana Černá, Václav Finěk Fig. 11 The second two dual basis functions [5% and [3^. and $j : = | v/2^T/34(2^1x)|[o ^,V2^/31(2j-1x),V2^l32(2j-1x), yW^M^^x - 1), yr2F^pi(2j-1x - 1), V^^-^x - 1), yW^M^^x - 1),..., v/2^T/3i(2^1a; - 2j^ + 1), V2^ß2(2j-1x - 2'-1 + 1), v/2^ľT/34(2^1a; - 2Í'"1) From the construction directly follows that span 1 form uniform £2(0,1)—Riesz bases for the space W\ and Wj, respectively. Proof. Due to the orthogonality of functions from ~*P\, they apparently form uniform L2(0,1)—Riesz bases for W\. For j > 1, we can numerically check 16 Dana Černá, Václav Finěk that matrix / 107179 137200 264659 617400 -1756 5145 19 140 -37501 137200 84241 \ 617400 264659 617400 38971 154350 -620 3087 53 630 -84241 617400 578 8575 -1756 5145 -620 3087 704 343 0 1756 5145 -620 3087 19 140 53 630 0 13 28 19 140 -53 630 -37501 137200 -84241 617400 1756 5145 19 140 107179 137200 -264659 617400 84241 \ 617400 578 8575 -620 3087 -53 630 -264659 617400 38971 . 154350 / which includes only wavelets with nonzero support in the interval (2 J 1,2 •'), is positive definite. The same matrix will be obtained in any interval in the form (k2~j-1, (k + l)2-j-1) for k = 1,... ,2^+1-2. For k = 1 and k = Z>+1-1, we obtain similar matrix, where the first row and column will be deleted for k = 1 and the fifth row and column for k = 2J+1 — 1. These smaller matrices are also positive definite. Consequently any matrix {&ji) can be composed from these small matrices and its the smallest eigenvalue can be bounded by the smallest eigenvalue of the small matrix and the largest eigenvalue can be bounded by double of the largest eigenvalue of the small matrix. Then by using the same arguments as in the last paragraph of the previous proof, we can conclude that collections of functions }pj form uniform L2(0, 1)—Riesz bases for the spaces Wj for j > 1. □ Now, we can apply Theorem 1. It is well-known [7] that a direct estimate of order d is satisfied when all polynomials of order d satisfying possibly boundary conditions are included in the space Vj0, while an inverse estimate of order 7 is known to hold with 7 = r + | when spaces Vj are spanned by piecewise smooth Cr(0,1) functions for some r £ { — 1,0,1,...}, where r = —1 means that no global continuity is satisfied. For constructed basis, we have d = d = 4, 7=f' and 7 = \- Then Theorems 1, 2, 3 imply the following results. Theorem 4 Let W(0,1) = [L2(0,1), Hd(0,1) H 7^(0,1)] s/4 , for s £ [0,4] and Hs(0,1) := (%~s(0,1))' for s < 0. Then for s G (-■|, |), the collection $x U 2-s!?i \J°°=2 2-s^j is a Riesz basis for Hs(0,1). Especially, the constructed basis, when normalized in £2(0,1) or -ff1(0,1), forms a Riesz basis for £2(0,1) and -ff1(0,1), respectively. 4 Condition numbers In this section, we provide condition numbers of one-dimensional stiffness matrices S and condition numbers of mass matrices M (see (7)) for different decomposition levels. Basis functions are normalized in L2(0,1) or in i?1(0,1), On a sparse representation of a n-dimensional Laplacian in wavelet coordinates 17 respectively: S Jp 3rr dx U"L IV-aI and M : Jo V'a Vy dx \iJx\\L2(0,r)\\iJß\\L2(0,l) And we compare condition numbers with condition numbers for a similar wavelet basis proposed in [13]. Results are summarized in Table 1. DS NEW n COND L2 COND Hl COND L2 COND Hl 4 7.0 1.7 1.0 2.6 8 15.2 4.4 1.0 2.9 16 24.3 5.5 6.3 3.7 32 32.0 5.8 12.7 4.4 64 37.3 6.2 18.8 4.8 128 41.2 6.6 24.4 5.1 256 44.1 6.8 29.3 5.3 512 46.3 6.9 33.6 5.4 1024 48.1 7.0 37.2 5.5 2048 49.5 7.1 40.4 5.5 4096 50.7 7.1 43.1 5.5 Table 1 Condition numbers of matrices M and S. Further, we consider here the following Dirichlet problem -V^—in a = (0, l)d with u = 0 on dO i=l &Xi for given / £ H^1 (i?) in two and three dimensions. A Riesz wavelet basis for Hq (i?) can be constructed by a tensor product of univariate Riesz wavelet bases. We consider here two options: an isotropic and an anisotropic tensor product. Isotropic wavelets arise as a tensor product of univariate wavelets and scaling functions from the same decomposition level. Then e.g. in two dimensions, we have these three types of wavelets j,k ® 1pj,l, 1pj,k ® j,l, i>j,k ® 1pj,l, where 4>j,k is a scaling function on the level j and ipjj is a wavelet on the same level. For a definition in arbitrary dimensions, we refer to [17]. Anisotropic wavelets were already introduced in (4). Then e.g. in two dimensions, wavelets will be of the form 1pj,k ®1pl,m, where ipj^ and ipi,m are wavelets generally on different levels. Therefore their supports can be arbitrarily anisotropic. In all cases, we use a normalization of basis functions in H1— seminorm. In Tables 2 and 3, we summarize condition numbers of stiffness matrices in two and three dimensions. We again compare them with condition numbers for a similar wavelet basis proposed in [13]. 18 Dana Černá, Václav Finěk DS NEW n isotropic anisotropic isotropic anisotropic 16 11.7 11.7 2.6 2.6 64 57.8 57.8 2.9 2.9 256 82.8 103.9 28.4 16.7 1024 90.2 144.0 49.8 43.4 4096 94.0 180.4 59.8 68.5 16384 95.4 213.4 66.1 92.9 65536 95.9 239.2 69.8 117.1 262144 96.1 259.6 72.2 138.7 1048576 96.2 281.0 73.7 158.1 Table 2 Condition numbers of stiffness matrices for d — 2. In all tables, n represents the number of basis functions, NEW denotes new wavelets, and finally DS denotes wavelets proposed in [13]. Obtained results confirm that condition numbers of stiffness matrices are on the first two decomposition levels small and independent of the spatial dimension. DS NEW n isotropic anisotropic isotropic anisotropic 64 81.7 81.7 2.6 2.6 512 812.0 812.0 2.9 2.9 4096 1383.0 2329.0 366.7 100.3 32768 1537.5 4297.5 764.3 517.8 262144 1595.8 6147.1 1022.0 1212.6 2097152 1611.3 7994.3 1159.2 2125.2 Table 3 Condition numbers of stiffness matrices for d — 3. References 1. Bramble, J. H., Cohen, A., Dahmen, W.: Multiscale Problems and Methods in Numerical Simulations, Springer-Verlag Berlin Heidelberg (2003). 2. Černá, D., Finěk, V.: Construction of optimally conditioned cubic spline wavelets on the interval. Adv. Comput. Math. 34, 219-252 (2011). 3. Černá, D., Finěk, V.: Cubic Spline Wavelets with Complementary Boundary Conditions. Appl. Math. Comput. 219, 1853-1865 (2012). 4. Černá, D., Finěk, V.: Approximate Multiplication in Adaptive Wavelet Methods, Cent. Eur. J. Math. 11, 972-983 (2013). 5. Černá, D., Finěk, V.: Quadratic Spline Wavelets with Short Support for Fourth-Order Problems. Result. Math. 66, 525-540 (2014). 6. Černá, D., Finěk, V.: Cubic Spline Wavelets with Short Support for Fourth-Order Problems. Appl. Math. Comput. 243, 44-56 (2014). 7. Ciarlet, P.: Finite Element Method for Elliptic Problems, Society for Industrial and Applied Mathematics. Philadelphia, PA, USA (2002). 8. Cohen, A., Dahmen, W., DeVore, R.: Adaptive Wavelet Schemes for Elliptic Operator Equations - Convergence Rates. Math. Comput. 70, 27-75 (2001). 9. Cohen, A., Dahmen, W., DeVore, R.: Adaptive Wavelet Methods II - Beyond the elliptic case. Found. Math. 2, 203-245 (2002). On a sparse representation of a n-dimensional Laplacian in wavelet coordinates 19 10. Dahmen, W.: Stability of multiscale transformations. J. Fourier Anal. Appl. 2, 341-361 (1996). 11. Dahmen, W., Stevenson R.: Element-by-element construction of wavelets satisfying stability and moment conditions. SIAM J. Numer. Anal. 37, 319-352 (1999). 12. Dijkema, T. J., Schwab, Ch., Stevenson, R.: An adaptive wavelet method for solving high-dimensional elliptic PDEs. Constr. Approx. 30, 423-455 (2009). 13. Dijkema, T. J., Stevenson, R.: A sparse Laplacian in tensor product wavelet coordinates. Numer. Math. 115, 433-449 (2010). 14. Griebel, M., Oswald, P.: Tensor product type subspace splittings and multilevel iterative methods for anisotropic problems. Adv. Comput. Math. 4, 171-206 (1995). 15. Primbs, M.: New stable biorthogonal spline-wave lets on the interval. Result. Math. 57, 121-162 (2010). 16. Stevenson, R.: Adaptive solution of operator equations using wavelet frames. SIAM J. Numer. Anal. 41, 1074-1100 (2003). 17. Urban, K.: Wavelet Methods for Elliptic Partial Differential Equations. Oxford University Press, Oxford (2009).