(7737 Illllllllllllllllll LIBR’ARY ' Michigan State University This is to certify that the dissertation entitled STUDIES ON STURM-LIOUVILLE WAVELETS AND FAST ALGORITHMS presented by Shangqian Zhang has been accepted towards fulfillment of the requirements for Ph . D. degree in Applied Mathematics Major professor Date 12/13/95 MS U is an Affirmatiw Action/Equal Opportunity Institution 0- 12771 PLACE IN RETURN BOX to remove this checkout from your rocord. TO AVOID FINES totum on or baton dot. duo. DATE DUE DATE DUE DATE DUE .mlmJfil ML JL l U4: l ' H l I MSU I. An Nflrmottvo Action/EM Opportunity Institution WM‘ H7 __ fi_—.fi__. _ STUDIES ON STURM-LIOUVILLE WAVELETS AND FAST ALGORITHMS By Shangqian Zhang A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1995 ABSTRACT STUDIES ON STURM-LIOUVILLE WAVELETS AND FAST ALGORITHMS By Shangqian Zhang Recent developments in the mathematical theory of wavelets have led to many important applications in engineering and sciences. These existing wavelets, how— ever, suffer from their limitations in dealing with non-uniform (weighted) spaces or singular differential operators. To overcome the limitations of existing wavelets, we shall construct, in this dissertation, wavelets from a general class of integral trans- forms known as Sturm-Liouville (S-L) transforms which are closely related to singular differential operators and weighted spaces. We first construct S-L cp-transforms which are very close to S-L wavelets except that they are a redundant system of functions rather than an orthonormal basis. We then construct S-L wavelet bases and show that they are complete orthonormal systems. In the course of such construction, we also discover certain norm equivalence properties for S-L wavelets. We obtain two applications of S-L wavelets. The first application is to the fast evaluation of S-L transforms. We shall present a fairly general fast algorithm for a class of S-L trans- forms whose father wavelets satisfy certain decay conditions. The second application concerns fast solvers for singular differential equations related to S-L operators. We finally prove that the projection matrix of the differential operator by the Galerkin method is sparse and can be preconditioned to a matrix with 0(1) condition number by a diagonal matrix. Thus, S-L wavelets provide fast solvers for singular differential equations related to S-L operators. To my parents, who always love me. To my wife, who always understands me and always loves me. To my son, who does not always understand me but always loves me. iii ACKNOWLEDGMENTS In the six years of my graduate studies, the job market in mathematics has gone from bad to worse. As a mathematics Ph.D. student, I have constantly had concern and frustration regarding my future. It was my great fortune, in this period of tough times, to always have support from professors, staff members, and my fellow graduate students at Michigan State University, to whom I owe a great debt of gratitude. Without their support, it would have been extremely difficult for me to finish this six year long journey. At the risk of omitting some names which deserve my thanks, I would like to thank the following people. I would like to express my deep gratitude to my advisor Professor David H. Y. Yen, who has been guiding me through this long six year journey and always lends his full support to me. Using this opportunity, I would like to wish him good health. I would like to convey my sincere appreciation to my co—advisor Professor Michael W. Frazier, who shows me mathematical insights about the wavelet theory and gives me his support without reservation. I would like to thank Professor Zhengfang Zhou for his help and for many discussions regarding this thesis. I would like to thank Professor Bang- Yen Chen, Professor Chichz'a Chiu, and Professor Qiang Du for their help and concern for my research progress. Also I would like to thank several people outside of my thesis committee: I wish to thank Professor Tien- Yien Li for his constant encouragement, Professor Wei-Eihn K non for his support in my graduate studies, and Ms. Barbara Miller, an outstanding secretary, for all of her help in the past six years. At last but not least, I would like to thank my fellow graduate students: Mr. T im- othy England, Dr. Xiaodi Wang, Dr. Xiaoshen Wang, Mr. Chris Weiss, Dr. Zhang- gang Zeng, and Mr. Jinjz'n Zhao. I thank them for their support. It has been fun to work with them at Michigan State University. iv Contents 1 Introduction 1 1.1 Motivations and an overview ....................... 1.2 Organization of dissertation ....................... 3 2 Sturm-Liouville cp-transforms 2.1 Sturm—Liouville transforms ........................ 2.2 Properties of S-L problems ........................ 2.3 Sturm-Liouville catransforms ...................... 10 2.4 Norm equivalence for S-L (p-transforms ................. 14 3 Sturm-Liouville wavelets 17 3.1 Construction of Sturm-Liouville wavelets ................ 17 3.2 Hankel (Bessel) wavelets and their localization estimates ....... 21 3.3 Norm equivalence for Sturm—Liouville wavelets ............. 25 4 Fast Sturm-Liouville transform 30 4.1 Fast Sturm-Liouville wavelet transforms ................ 30 4.2 Fast Sturm-Liouville transforms ..................... 36 4.3 Fast Hankel (Bessel) Transforms ..................... 37 5 Fast solvers for singular differential equations 40 5.1 Review on fast solvers for differential equations with almost constant coefficients ................................. 41 5.2 Fast solvers for singular differential equations ............. 43 6 Discussions and concluding remarks 47 List of Figures 4.1 Hankel (Bessel) wavelet 450,1(z) for J1. 4.2 Hankel (Bessel) wavelet (150.1001!) for J1. vi Chapter 1 Introduction 1.1 Motivations and an overview Selection and construction of function bases in mathematics have important implica- tions in many science and engineering applications. Function bases are used to encode images in image processing, to represent different geometric objects in CAD / CAM, and to approximate solutions for differential equations, among other applications. It is not an exaggeration to say that function bases play an essential role when we apply mathematics to real world problems. Wavelet bases are new kinds of function bases. Before wavelets, there were two types of commonly used function bases. One type of bases are called spectral bases such as sine, cosine, and Jacobi polynomial bases. Spectral bases are localized in their corresponding spectrum but not localized in space. The other type of bases are localized in space but not localized in spectrum, such as piecewise polynomials and splines. We refer to them as finite element bases. Both types of the above bases have limitations and disadvantages. Because spectral bases are not localized in space, there are Gibbs phenomena for spectral approxi- mations. On the other hand, it is difficult to resolve high frequency oscillations or jumps by finite element bases since they are not localized in spectrum. To retain the advantages and overcome the disadvantages of both types of bases, wavelet bases were recently introduced. Analysis involving the use of wavelets is called the wavelet analysis. Wavelet analysis is a very versatile tool. It has wide applications in many engi- neering areas as well as in mathematics itself. Important applications include image compression and fast solvers for differential and integral equations. Many applications even touch our daily life such as designing high definition televisions and compressing the finger print database for the FBI. Why does wavelet analysis have such a wide range of applications? One impor- tant reason is that the wavelet analysis has deep roots in mathematics, particularly in harmonic analysis. Some philosophy from harmonic analysis as well as some novel mathematical observations are used in wavelet analysis. One basic motivation for wavelet analysis is to represent functions efficiently and faithfully in various senses or function norms. There are three important ideas in wavelet analysis. First, wavelet analysis is a space—frequency (time-frequency) analysis in which both space (time) and frequency are considered. More precisely, wavelet basis functions (wavelets) are localized in space and spectrum. An advantage of wavelet bases over spectral bases is that wavelet bases can overcome or at least alleviate Gibbs’ phenomena for approxi- mating a step function, while an advantage of wavelet bases over finite element bases is that wavelet bases can resolve high frequency oscillations or jumps of functions. In a uniform (unweighted) space, wavelets use dilations for different frequencies and translations for different locations. Second, the wavelet decomposition in spectrum is a special decomposition known as a Littlewood-Paley decomposition. In this de- composition, the transformed functions in spectrum are decomposed into frequency components in intervals [2”, 2"+2]. Because of this special frequency arrangement, the wavelet coefficients of a given function can be equivalent to the function not only in 2-norm function spaces but also in p-norm function spaces. In mathematical terms, wavelet bases have norm equivalence properties in a wide range of function spaces; therefore, wavelets represent functions faithfully. Third, a spectral basis usually con- sist of eigenfunctions of certain differential operator. Thus they give a diagonal rep- resentation of the corresponding differential operator. Spectral bases, however, are not localized in space. Wavelets are related to eigenfunctions of differential operators in the sense that wavelets can almost diagonalize these differential operators, while at the same time they are localized in space. Summarizing the properties of wavelets discussed above, we characterize wavelets as function bases that are localized in both space and spectrum, have certain norm- equivalence properties in a wide range of function spaces, and can nearly diagonalize many differential operators. For existing standard wavelets, the term spectrum means the Fourier spectrum (the Fourier transform), the associated differential operators are those with constant coefficients. As we know, there are integral transforms besides the Fourier transform; there are transforms associated with differential operators with variable coefficients. Such integral transforms and differential operators also play important roles in ap- plications to engineering or scientific problems. For example, when working with the two-dimensional Laplacian in polar coordinates, we use the Hankel (Bessel) trans- form rather than the Fourier transform. Indeed, many integral transforms can be generated form singular S—L problems. They are thus referred to as S-L transforms or generalized Fourier transforms. Can one construct wavelets for S—L transforms? If the answer is yes, we shall call such wavelets S—L wavelets. One then inquires as to how S-L wavelets are related with the corresponding S-L operators. Questions also arise to as what kind of norm equivalence properties such S-L wavelets enjoy and what possible applications such S-L wavelets may have. In this dissertation, we shall answer the above questions to some extent. First, we construct S-L go—transforms which are very close to S-L wavelets except that they are redundant spanning systems rather than orthonormal bases. Then, we construct S-L wavelets bases and prove that they are complete orthonormal systems. We also obtain certain norm equivalence properties for the S-L wavelets constructed. We find two types of applications of S-L wavelets. The first type of applications concerns fast evaluations of S-L transforms. We present a fast algorithm for a class of S-L transforms whose father wavelets satisfy certain decay conditions. The second type of application is to obtain fast solvers for singular differential equations related to S-L operators. We prove that the projection matrix of the differential operator by the Galerkin method is sparse and can be preconditioned to a matrix with 0(1) condition number by a diagonal matrix. Therefore, S-L wavelets will lead to fast solvers for singular differential equations related to S-L operators. 1.2 Organization of dissertation For the remainder of this chapter, we shall give a brief description as to how this dis— sertation is organized. In Chapter 2, we provide some background information on S-L transforms and spectral properties of singular S-L differential operators. Then, similar to standard cp-transforms for the Fourier transform, we construct S—L go—transforms for S-L transforms. In constructing S-L cp-transforms, a simple trick is used for weighted spaces (Lemma 2.3) in addition to the standard Calderon identity (Lemma 2.2). The S-L cp-transform yield a redundant or “overcomplete” system of functions. This re— dundancy limits their applicability. On the other hand, the redundancy makes the norm equivalence proof (Theorem 2.8) much easier and more transparent than the corresponding proof for S—L wavelets. In fact, we use the norm equivalence property for S-L 4p— transform as a bridge to the proof of the norm equivalence property for S-L wavelets. In Chapter 3, we construct S-L wavelets by adapting Meyer’s construction of wavelets to general S—L transforms. We construct our S-L wavelets on the spectral side so that they are automatically localized in spectrum. There are two tricks for this construction. One is to adapt Meyer’s wavelet bases form L2((-00, +00), d5) to L2([0, +00), d6) (Lemma 3.1). The other one is to deal with the weight function p(§) (Lemma 2.3). After constructing S-L wavelets, we prove that S-L wavelets constitute complete orthonormal systems (Theorem 3.1). For the spatial localization property of S-L wavelets, we provide a proof just for Hankel (Bessel) wavelets to illustrate the basic idea of localization proofs (roughly speaking integration by parts). A general proof for a large class of S-L wavelets will be given in [9]. A special technique employed in the general proof is the Priifer transform ([2]). At the end of the this chapter, we obtain the norm equivalence property for S-L wavelets by using Schur’s lemma and the norm equivalence property for S-L cp-transforms. Chapter 4 gives a general fast algorithm for evaluating S-L transforms in so far as the father wavelets satisfy certain decay conditions. There are two steps in this algorithm. In step one, we use the fast S-L wavelet transform to obtain S-L wavelet coefficients from N spatial function values. The computational complexity for this step is 0(N) or at most 0(NlogN). In step two, by the special structure of S- L wavelet bases, we can evaluate the wavelet series in spectrum by the FFT. The computational complexity for this step is 0(NlogN). In Section 4.1, we apply mul- tiresolution analysis to S-L transforms and give fast S-L wavelet transforms. This section not only provides us with the first step of the fast S-L transform, but also gives us an important part of the S-L wavelet theory. In Section 4.2, we give the second step of our algorithm. In Section 4.3, we apply the ideas of our algorithm to a concrete S-L integral transform—the Hankel (Bessel) transform, and show that the Parseval identity and the decay property of father wavelets are essential ingredients of our fast algorithm. In Chapter 5, we prove that S-L wavelet bases give us fast solvers for singular differential equations related to S-L operators. In Section 5.1, we give a brief review on the fast solvers for differential equations with almost constant coefficients. In Section 5.2, we show that S-L wavelets can overcome the limitation of standard wavelets and yield fast solvers for singular differential equations. We prove two assertions. First, the projection matrix of the differential operator by the Galerkin method is sparse. Second, the projection matrix can be preconditioned to a matrix with 0(1) condition number by a diagonal matrix. Chapter 6 contains some disscusions and concluding remarks. This dissertation extends the ideas of standard wavelets for the Fourier transform to S—L transforms and constructs S-L wavelets. We obtain some theoretical results and some applications. However it is by no means the end of research in this di- rection. Rather it is just the beginning. We link wavelets with integral transforms and eigenvalue problems. We set up a structure for constructing wavelets from either singular S—L eigenvalue problems or from integral transforms. We need to develop our research by adding some more detailed studies on some concrete S-L eigenvalue problems and their corresponding integral transforms. Chapter 2 Sturm-Liouville go-transforms We shall construct in this chapter Sturm—Liouville (S-L) cp-transforms. S-L cp—transforms are very close to S-L wavelets except that they are redundant spanning systems rather than orthonormal bases. Although a S—L cp-transform gives us a redundant system, its norm equivalence property is relatively easier to prove. This proof can be taken as a vehicle to prove the norm equivalence property of S—L wavelets. 2.1 Sturm—Liouville transforms In this section, we shall present some background materials about S—L transforms. We shall state some lemmas and theorems without proofs, as such proofs can be found elsewhere, say, in the books of B. M. Levitan and I. S. Sargsjan [12] [13]. Let y(r, A) be an eigenfunction of the following S-L eigenvalue problem Mill 5 -y” + C1(~'v)y Ay (2-1) y(a, A)cosa + y'(a, /\)sina = O y(b, A)cos,3 + y'(b, A)sin,8 = 0 (2.2) where a and ,3 are given, and y’ = g. A S-L problem is said to be regular if the interval [a,b] is finite, and the potential function q(a:) is in L1([a,b]). Otherwise, if [a,b] is infinite, or if q(a:) is not in L1([a,b]), or both, the S-L problem is said to be singular. It is well known that a regular S-L problem leads to eigenfunctions that are com— plete in L2([a, b]). As b —+ 00, a regular S-L problem becomes a singular S-L problem, and we shall state what become of the counterparts of the S-L eigenfunction expansion and show that they become S—L transforms. Let a = 0 and b —> 00 in (2.2), then, (2.1) and (2.2) become the following singular S-L problem y” + {A — q(a:)}y = 0, O S .r < 00, (2.3) y(O, A) = sina, y'(0, A) = —cosa. (2.4) In (2.3), we assume that q(:z:) is real valued and continuous in each finite interval [0, b], 0 < b < 00. Let yn,b(:r) = y(as, Amb) be the n-th eigenfunction of the regular S-L problem (2.1)(2.2). Then, we have the following expansion theorem: Theorem 2.1 For any f(.r) E L2((0,b),dx), the Parseval equality 2 job f2(x)d.r = :2 a: (job f(a:)yn,b(x)dx) (2.5) ml) holds, where 0,2”, = fé’ yg’b(:r)d:c. Proof: See [13], p. 28. C] If we introduce the following monotonically increasing step function _ Z 351'— A S 0a A = A 0, 00",ng amb then equality (2.5) can be written in the form b 00 / f2(:v)d:v= / Fund/to), 0 -00 where 6 NA) = [0 f(x)y(x, mm. We now let b —> 00 in the above equality. This then leads to the S-L integral transform for the singular S—L problem (2.3), (2.4). Before illustrating this we need the following lemma. Lemma 2.1 For any positive number N, there exists a positive constant number A=A (N) not depending on b, such that Vin/{MM} = Z i = MN) - Pb(—N) < A -N 0, A > 0, then 1 A+A d,\ ”(A + A) — p“) = ;/. «Wm + emf i.e., the spectrum of the problem {23),{2.4) is continuous in the interval (0, 00), where (2.7) y(A) = sina—\-71._;‘/ooosin(\/At)q(t)y(t,A)dt, (2.8) cosa 1 °° y(A) = ’VT+ W 0 cos(\/At)q(t)y(t,A)dt, (2.9) for y(t, A) satisfying {ESQ/2.4). Proof: See [13], p. 83. D Theorem 2.6 If q(x) E LI([O,00),dx), then, for A < 0, the spectrum of the problem (2.3),(2.4) is discrete, and bounded from below. Proof: See [13], p. 82. E] Spectral properties for other potentials q(x) can be found in [12] [13]. 2.3 Sturm—Liouville cp-transforms We now construct S-L go-transform in this section. For this purpose, we need the following lemmas. Lemma 2.2 There exists a real function @ E C°°([0, 00)) such that suppcfi C {6; i S ICI s 1}, lcfil > c>0 iffi; s (a g g, and Z (ea-"of =1 for all 5 > o. (2.10) VEZ Proof: See [8], p. 54. D A more general version of the above lemma can be found in [8], p. 54. Lemma 2.3 If {bu} is an orthonormal basis of L2(dx), then, {bu/wi} is an or- thonormal basis of the weighted space L2(w(x)dx) with weight w(x) Z 0. Proof: For all f(x) 6 L2(w(x)dx), by definition, [f2(x)w(x)dx < +00 i.e, [(fwirdx < +00 thus, fwi E L2(dx). Since bn is an orthonormal basis in L2(dx), 2 N Iim/[fwi—Zb, dx=0. n=l N—+00 10 Then, for the convergence in L2(w(x)dx) 2 N #1120 f - “2:; < f, bnw’i >w bnw'i wdx N 2 . r i = 135130 fw2 —n:=:l < f,b,,w2 > bn dx N 2 = [$3130 fwi—nz=21bn dx = 0. Also < bnw"%,bmw—% >w=< bmbm >= 6m... Thus, {bnw‘i'} is an orthonormal basis of L2(w(x)dx). C] Before we present the S-L cp—transform identity we need a new notation K (x, E ) defined as follows: KW) “é‘ y(m’). Then (2.3) and (2.4) become, respectively, ——d—x§ + q(x)K = 52K, 0 S x < 00, (2.11) K(0,£) = sina, K'(0,§) = —cosa. (2.12) In this dissertation, we are primarily interested in the case q(x) 6 L1((0, 00), dx) for the construction of S-L wavelets or S-L cp-transforms. For this case, by Theorem 2.5 and 2.6 we know that the spectrum is continuous for A _>_ 0 and finite discrete for A < 0. Since we need a continuous spectrum for either S-L wavelets or S-L cp— transforms, we shall construct S-L wavelets or S-L (p-transforms for A Z 0. In general, we shall expand any function f(x) 6 L2([0, 00),dx) in the following way: for A < 0, we expand f (x) with respect to eigenfunctions or local eigenfunctions (similar to the local sine or cosine bases) and for A Z O, we use S-L wavelets as a basis. In what follows, for simplicity, we only consider the case A Z 0 which implies 6 = x/A are nonnegative real numbers. In the variable 6 the S-L transforms become Pa) = (f(x)f= (”unmade f(x)€L2([0,oo)), (2.13) f(x) = (no): foooF(€)K(x,€)dp(€), F(c)eL2([o,oo),dp=/ooof(x)g( (x)dx=/_: F(g ()p(g)dg -.—.,,, (2.15) We are now ready to construct S-L cp-transforms as outlined in the following theorem. Theorem 2.7 For any f(x) 6 L2([0, 00),dx), we have the following S-L go-transform identity : Z Z < fi‘i’vm > ‘Puma (2.16) 1162 n:l where _ ((am-”02*”-Wynn-”n20), 99”" — 12(6)”2 2” = / 2(2'"¢)2“‘"“’/2sz‘n(2-”mroK(2,spur/226. (2.17) 0 Here, cfi is given in Lemma 2.2. Proof: For any f(x) 6 L2([0,00),dx), f(x) = /°°f(oK(2,11)dp() = zj°°(2 (2 €)f)2(f(E)K(x, 1212(2) (byLemma22) uEZ = 232/2 2(2 of )¢(2'”E)K($,€)p'(€)d€, (since supp(p’ = < f, (pm >, (by (2.15)). Hence 00 2(2'"c)f(o = Z < L221. > 2-<”-1>/2s2'n(2-"mr§)(2101-12. n=l Substituting the above equality into (2.18), we have f(x) 2"°° = Z] Z2*"-Wane-"ms(den-”221222) uEZ 0 n=1 K02, £)p’(€)d€ 00 2v = ZZ / 95(2‘”€)2‘(”"’/23in(2’”nr€)[f(x,€)(p’(€))”2d€ uEZ n=l = Z i < f, 9911,11 > (‘Pumflml VEZ 11:1 : Z Z < f, 9011,71 > 99V.n(m)' VEZ n=l Remark 1: The advantages of the S-L go-transform include localization in spec- trum, localization in space, and norm equivalence properties. Compared with S-L wavelets, the advantage of S-L cp-transforms is that its norm equivalence property can be proved more easily and this proof will serve as a vehicle for the proof of the norm equivalence property for S-L wavelets (to be introduced in the next chapter); the disadvantage of S-L cp-transforms is they are redundant systems (i.e. not linearly independent) while S-L wavelets are orthonormal bases. The reason for the redun- dancy of S-L «(J-transforms is that supp{§5(2"”€)f(§)} C [2"‘2,2"] , however, it is expanded with respect to an orthonormal basis on [0, 2"]. 13 Remark 2 In the construction of S-L cp-transforms, we have used the basis {2 (”“ll/zsin(2“’ n11'.’;')}°°___l for L2([0,2"]). We also have other choices. For instance, we can choose {cnK(§, {22“} from the following S-L eigenvalue problem: __ d2K(€a €2",n) dx2 + Q($)K(€1€2",n) : 6;”,11K(€1€2”1n) 0 S (I) < 2” K(0, €222.) = o, K(2”, £22,.) = o. By expansion theorems ( Theorem 1.5.1 and Theorem 1.5.2 in [12]), we know that {cnK(£, {22,0} is an orthonormal basis for L2([O, 2"]). For the case K(x, E) = K(£, x), the basis {cnK(§,£22,,,)} may give better spatial decay of S-L cp-transforms or S-L wavelets than does the basis {2'(”'l)/zsin(2"’n7r{) 3,1, 2.4 Norm equivalence for S-L cp-transforms Similar to the fact that the Fourier transform changes differential operators to multi- pliers, S—L operators become multiplier operators under S-L transforms. In addition, S-L go-transform bases are localized in the spectrum. Combining these two facts above, we obtain a norm equivalence property for S-L gin-transforms. Let L denote the operator -£—, + q(x), i.e Lf(2) = 1’3]? + 2121212). Lemma 2.4 Supposef E 02([0,00)), f(0) = 0, limx-mo f(x) = 0, and lim,,_,oo K0325) f(x) = 0 for all g > 0. Then (Zing) = 222(2) Proof: Integrating the left side above by parts, we have (271(2) = [032211212 >22 = /°° —f” 2)K 22+ f 22122 = 212021211? + form—(+122 dx +/0q( ()x f()x )K( x(,€)dx dK(x, d2K(x ———£—’)d =o+ —-—),€2f()13°—/°°f 2(2) .122 2 14 +/m x,§Mx = [00 f(w (dexé) +q(2:)K($,€))d$ = 2/0°° f(2)K( 2,2)2 2 (by211) = 2213(2). D Theorem 2.8 Suppose f(x) satisfies: f(x) 6 C2([0,00)), f(0) = 0, limaHoo f(x) = 0, and limznoo K(x,§)f’(x) = 0 for allfi _>_ 0. Then, there are constants Cl > 0, 02 > 0, which are independent of f, such that CIZZI2VIZS SCZZZI2VI21 VEZ n=l uEZ n=1 or, in other words, < Lf,f >2 2 f: l2” < f, 90,”, >l2. (2.19) 1162 n=l Proof: By Lemma 2.4 and the Parseval identity, = <31f>lfl : <€2ftf>PI = / 2212122220122) = z/:12 22122121 2))? 222'()2 (1212.10)) uEZ 2 2221:: 12(2 2)) m )1? '()2 1162 = 222”] 122-”211212)12'() (22222(2-”2)c12"-2,2”1) 1162 Since {2 (V ll/zsin(2u ”nr€)°° :1 is an orthonormal basis for L2([0, 2"], d5), we have [0 12222)) 1112 )1: 22'( 2) 22 00 = 2:0 n=1 2" 2 2(2-V2)f(2)(2'(2))”22“"-Wane-22022 m A : Z|P' [2 n=l 00 = Z| [2 n=l 15 By the above two equalities, we have 211 :2 222"]: 1162 = Z Z |2" < f,<,o..,,, > |2. VEZ n=l ”WI |f(€ )l2 1061 6) d6 16 Chapter 3 Sturm-Liouville wavelets We constructed in the last chapter S—L cp-transforms. One disadvantage of such S-L go-transforms is that they are redundant i.e. not linearly independent. We shall in the last chapter overcome this disadvantage by constructing an orthonormal basis referred to as the S—L wavelet basis. We shall also prove a norm equivalence property for S-L wavelets. 3.1 Construction of Sturm—Liouville wavelets Our goal in the construction of S-L wavelets is to obtain basis functions that are localized in space and in S-L spectrum and have certain norm equivalence properties. To have S-L wavelets localized in the S-L spectrum, we begin our construction in S-L spectrum. We then prove that the S—L wavelets are localized in space and have the appropriate norm equivalence. The basic idea of the construction is to adapt Meyer’s wavelets in spectrum to S-L transforms. By (2.15), we know that the function space in the S-L spectrum is L2((0,00),p’d§). Thus on the S-L spectrum, we wish to construct an orthonormal basis with localization properties for the weighted space L2((0200),p’d€)- Meyer constructed his wavelets {hu,k(x)} as the following ( [14], [3]): 1222(2) = (52.46))” where “ A ” and “ ' ” represent the respectively Fourier transform and its inverse, and A 1 —u — "V — i —u 2.,2(2)=\/-277;2 ”22 (k ””2222 2). (3.1) 17 Here the “window” function w(§) : R ——) R satisfies: w(§) E C °°(R) (or just Cm(R) for some m), suppw(§) Q {5 : 27r/3 S [If] S 87r/3}, and w(—§) = 211(5) for all .f E R. One concrete example which is given in [3] is the following: 222(12212121— 1)) 223121932, 2(2) = 222(21421121-1» —" s )2 21 s 23— (3.2) 0, otherwise, where y(x) is a C°° function satisfying 0 ' < V(x) = ’ if x _ 0’ and V(x) + V(l - x) = 1. (3.3) 1, if x 2 1, Meyer proved that {hu,k(£)} is a complete orthonormal system for L2(R). Based on the Fourier transform of Meyer’s wavelets, we define 1 —!—2""/2+1sin(2 ”(k — — 222(2) 42‘ —2Im(iz.,.(2)) = fl? 2) {)w(2""€), k 2 1, (3-4) and establish the following lemma. Lemma 3.1 The collection {gu,k(§)}uez,keN is a complete orthonormal system in L2([0,00),d€)- Proof: By (3.1) and (3.4), 222(2) = -—2Im(1‘2..,2(2)) = 31(2..(2)—i2.2(—2)) __1 . Since each 9%“) is odd and real, f2...-(2)2.2(2)22 = $— /_: 2222222022 = ,1— j: (2.2.12) — 112—222)) (122.2(2) - 11.2.2120) 22 l = 5(6#,u6j,k — 6#,u6j.-k+1 _ (film‘s-.741)" + 6t‘1V6_-l+11‘k+1 ) < 311.1(6), 3145(6) > 18 Since k,j Z 1, thenj 75 —-k+1 and —j+1 31$ Is. Also, 6“,V6_j+1’_k+1 = 5p,,,6j,k. Hence .. . l < 911.1(6), 914k“) > = 5(6uw6ch _ 0 _ 0 + 5n.V6-j+l,—k+l) = 6p,u6j,k Thus the system {§V,k(§)},,€ 2,1,6 N is orthonormal. For the completeness of {§V,k(€)}yez,keN, suppose f({) E L2([0,oo),d§) and < f,g,,,;c >= 0 for each V E Z,k E N. Let fo(§) be the odd extension of f(f) to R. Then for k 2 1 L: fo(€)iz"'k(€)d£ = 1:5“) [71—2—7;2—”/2603(2-V(k — %)E)w(2-u€) 1 1 _V ‘7? mo V(:—§)§)w w(2 a) dc : 0 - _ :fo( €)gu,(k§ = --2 < 2f,g°:,k > = 0. (3.5) If k S 0, then -k +1 2 1, so that by (3.5), f: f.(¢)iz.,.(s)dc j: fo(-€)lzu,k(-£)d(-€) = — j: fo(£)l1u.-k+1(€)d€ : —i < fagV.-k+1 > z 0. (3.6) By (3.5), (3.6), and the completeness of {ilu,k(§)}uez,kez in L2(R), we obtain that fo(€) = 0 a.e. on R. Hence f({) = 0 a.e. on [0,oo). Cl Recalling Lemma 2.3, we define S—L wavelets in S-L spectrum by the following: A d_e[ gu,k(€) MO " (more _ _1_/s1n<2-V(1c - %)€)w(2-V£) _ «212 (p’(€))‘/2 , (3”) represents the S-L transform. Finally, we where p’(§) is given in (2.14) and “ define S-L wavelets in space by mo) ‘2' (113.1(5)) 19 _ 2-V/2+1 cosin(2-V(k-§-)g)w(2-Vg) — r27. 0 (1115))!” I“ ’5)de —u/2+l 0.0 _ 2\/2—7_r [0 SW2 ”(k-%)€)w(2‘”§)fi’(x, )(p’(€))‘/2d€ (3.8) By the Parseval identity (2.15), we obtain the following theorem. Theorem 3.1 The collection {ibu,k(:c)},,€z,keN is a complete orthonormal system in LV<[o,oo).dx). Proof: By the Parseval identity (2.15) and Lemma 3.1, we have loco ¢u.j($)¢u,k(x)dx : fooo $fl.j(£)¢u,k(€)pl(€)dé 0° find-(C) gu,k(€) , 0 (p’(€))l/2 (p/(€))1/2P(E)d€ : < gu.j(€)9gu,k(€) > = 5u.u5j.k- Therefore {1/),,,k(:r)}uez,ke~ is an orthonormal system. For the completeness of {wu,k(:c)}yez,k€)v, suppose that < f , $14k >= 0 for all u E Z,k E N, and f 6 L2([0,oo),dx). Then by the Parseval identity (2.15), < f, 11...). >= Amf(€)1h,k(€)p’(€)d€ = 0, u e 2,): e N, i.e., f0 hooray/29.40% -—- o, u e Z,k e N. By Lemma 3.1, we have flea/(5)1” = 0. on [0,“). Hence, CC. f(x) = Ell 00 A f(£)K(:v,£)p’(€)d£ f(€)K(x,~f)p’(€)d€ = f(e)(p’(§))‘/2K(x,s)(p'(£))V/Vd5 00 ll 8'o\.o\. 0 II 5: Therefore, {¢u,k($)}uez,keN is a complete system. Cl 20 3.2 Hankel (Bessel) wavelets and their localization estimates The purpose of this section is threefold. First, we construct Hankel (Bessel) wavelets to illustrate that the essential ingredients in our wavelet construction are the exis- tence of an integral transform and the corresponding Parseval identity. The integral transform does not have to be generated from a S-L problem or, in particular, from a S-L problem in normal form. Second, we study the spatial localization of Hankel (Bessel) wavelets to show the flavor of spatial localization proofs. The proofs for a more general case q(x) E L1([0, 00)) will be given in [9]. Third, the Bessel case is of particular interest in its own right for applications. The Hankel (Bessel) transform is given by: 1‘15) = (f(x)): (magnum-owns, f(x)eLV([o,oo),xdx) (3.9) f(x) = (no): [flotsam F(c)eLV([o,oo).eds) (3.10) where Jn(x.£) = K (x, C ) is a solution of the Bessel eigenvalue problem £5. #1310) _ EZKWS) = §2mK(a:,§), o g :1: < oo. (3.11) Also, there is a Parseval identity < f,g >x= f0 f(w)g(-r)wd:v = f... F(€)G(€)€d€ =< F,G >e . (3-12) Similar to (3.7), we define Hankel (Bessel) wavelets as: All, é- . 2—u/2+l 0° “taped/(2)) = «27 o Exactly the same proof as for Theorem 3.1 shows that the above Hankel (Bessel) sine-Vac — %)€)w(2”"€)Jn(x€)€‘/2d€- (3.13) wavelets form an orthonormal basis in L2([0,oo),;rd:r). We now prove the spatial localization property for Hankel (Bessel) wavelets. More precisely, we want to show that z/JVJ, is localized around 2"(lc — 1 / 2) and that {$14k} have the correct dilation property. Lemma 3.2 Given a function 7(5): [0,oo) -—> R that satisfies 7(6) 6 C°°(R), sappy“) Q {E :0 < c < E < (1}. Let Lg = i (5%) — 33. Then for any b 6 [0,00), fsz‘n(bé)v(e).l.(xé)ds 21 = $2:bb2 [000 cos(b€) [726—2 +2£— d5 (1(7 ——(€—€))] J,,(:r€)d§ —$2 1—b2 [000 3i”(b€)L£ (1%)) Jn($§)d€ (3.14) and [coswomwnaods = 3:2 f- b2 [000 sin(b§)[fly (£5) + 25‘? d6 d(7—(¢.—€))] Jn($§)d€ —.x2—-:—b_2.,/ooo cos(b§)L£ (1%)) Jn($€)d€. (3.15) Proof: We first prove (3.14). Writing A = f0°° sin(b§)7(§)Jn(at§)d§ and using L£(Jn($§)) = —zV:J.(x:), we have (3.5VV — b2)A = f: sin(b§)7(£)a: VJ, (x§)a'§ — b2A (3.16) = —/000 sin(b§)—(—€)L£(J Jn(:c€))d.f—b2A. (3.17) Since sappy“) Q {E : 0 < c < 6 < d}, we have on the interval [c,d] the following Green’s formula for L5 (see [16] p.269). < Lafig > - < f, Leg >= dW(f,§; d) - cW(f, .1); c)- Then for f({) = sin(b{)1%9, 9(5) = Jn(a:€), we have W(f,§; d) = f(d)§’(d) - Will—"(61) = 09701) - 9(d)0 = 0- Similarly, W(f, .51; C) = 0- Hence Loosin(b§)l%€—)L5(Jn($§)ld§ ___ [sin(b§)l(§—)L:(Jn($€))d€ : < f) Lég > = < Lafig > = [d L 5(sin( b§))1—-(€)J Jn(a:£)d§ = fooo L£( sin (55));9 J.n(:c{)d{ (3.18) 22 By (3.17) and (3.18), we have 7(6) (3:2 — b2)A = — f: L€(sin(b5)—E—)J,,(:c5)d5 — (PA. (3.19) Note that Le(fg) d: (6;- é(fg)) - ngg = (€f”’g+§fg) —-"E—fg = f’g + £f”g + 25f’g’ + f (£g’)’ — = f’g + €f”g + 2Ef’g’ + fLeg E‘fg Thus for f(5) = sin(b€)) 9(5) = 7(§)/€a j_(€)) 5 b2 bsin(b€)7(€) + 2€bCOS(b€) (— L5 (sin(b5) 7(€)_ 7'05) —bcos( b5) Ml Substituting the above expression into (3.19), we have (x2 — b2)A : — [00° (bcos(b5)f—y-(.’EQ — bzsin(b5)7(5) + 25bcos(b5) (7(6)) + T sin(b5)L (7—29)) Jn(:c§)d5 — b2A = —b/OOO cos (b5) [l—(C) +25— d5 (1(7 (66—1)] Jn(:1:5)d5+b2A — [00° sin(b5) )L5( L9) Jn(35)d5—b2A C : —b/Ooo cos (b5) [Z—(O +25— d5 M( (50)] Jn($€)d§ —-/ooo sin(b5)L£ (“70) Jn(:c5)d5. Thus (3.14) holds. Similarly, (3.15) also holds. D Based on the above lemma, we now prove the following spatial localization theorem about Hankel (Bessel) wavelets. 23 Theorem 3.2 For Hankel (Bessel) wavelets {ibu,k(:c)} defined by (3.13) and related with positive integer order Bessel functions Jn(1:), we have [11) I < 2"“: -1/2)M CM min{2un$n,2—y/2$-l/2} u,k($) — 2uM(:z: + 2-v(k — l/2))M (1+ 2qu _ 2-V(k -1/2)|)M where M is a positive integer. Proof: By (3.13) for V = 0, 1101.1 zfiQ/WSM —1/2)£)w(£)J.(a:€)éV/Vds. In Lemma 3.2, we let b = lc — 5, c = 2?”, and d = 8?". For the first iteration, let 7(5) = w(5)51/2. Noting that 311ng (fléfl) Q supm(5) Q [c,d], and this function is C °°, we can apply Lemma 3.2 M times. After M iterations, we have 1 $01k”): ($2_ —T_2)M:baM'IfMl( 37)) where fM,((:c) = f0°° sin(b5)7M,)(5)Jn(:t5)d5, a114,) S M, and 7114,)(5) satisfies the con- dition for 7(5) in Lemma 3.2. Then bM 12/2041)): I _b—7—,M_.21fm,(. For an integer order Bessel function Jn(:r), we have ( see [7]) |J,,(:c)| < min{:c",:c“/2}. Hence WM) = I [00°sin(b€)7M.z(€)Jn(a=€)d€| d = I /. sin(b€)7M,z(€)J..(-r€)d€| s Cmaxlm,.(e)(d - c)lm1'n{:c", x-V/V} = CM,)min{a:",x‘1/2} < +00. Therefore, bM 2M l¢o,k($)| S W E; IfM,1(:r) bM 2M 3 W;CM.zmin{xV,x—V/2} =1 CMbM Wmin{xn, $—l/2}. 24 Since [$0.43)] S max|w(5)(d — c)|min{a:",a:‘l/2} < 00, the above inequality can be rewritten as bM CM For a general u, noting that min{:r",.r‘l/2}. 2—u/2-l-l me) = m °°s1n(2‘ V(k——)€)w(2 Vanessa/211: 2u-/2+l " 2W7 Taoism (k-—)1 )m) (t)J,,(2"a:t)(2"t)1/2d(2"t) = 2 11101). 2 33) we have I¢.,.(x)l = 2"Iwo,).(2"x)| 2%“ CM (21/;- + b)M (1 + I212: — bl)“ 2"(k — 1/2)“ CM min{2""x", 2‘”/2x‘1/2} 2"“(2: + 2-V(k —1/2))M (1+ 2"|:z: -— 2-V(k —1/2)|)M min{2unxn’ 2—u/2m—l/2} Similar results can be established for Hankel (Bessel) wavelets associated with non-integer order J,‘(:r) because [J,,(:c)| S car“. Applying the same ideas, we can also obtain decay properties for such S-L wavelets whenever K (at, 5) = K (5 , at). 3.3 Norm equivalence for Sturm—Liouville wavelets In Section 3.1, we constructed orthonormal S-L wavelet bases. Thus, a function f (11:) in L2([0,oo)) can be expanded in a S-L series. We wish to inquire as to whether the sizes of such expansion coefficients can characterize the given function f (:r) The answer to this question is related with the norm equivalence property of S-L wavelets. This property is sufficiently important for wavelets that it should be regarded as a part of the definition of the S-L wavelets. Because of the norm equivalence property, we shall see that in Chapter 5 that the projection matrices of S-L operators on S— L wavelet bases can be preconditioned to a condition number of 0(1) by diagonal matrices. This together with the sparseness of the projection matrices gives us fast solvers for differential equations involving S-L operators. 25 The proof of norm equivalence property for S-L wavelets is based on the above result about the norm equivalence for S-L (p-transforms (Theorem 2.8) and Schur’s lemma. We use Schur’s lemma to prove that the transform operator from S-L (,0- transform coefficients to S-L wavelet coefficients is bounded. First we give Schur’s lemma in its simplest form. Lemma 3.3 (Schur’s lemma) Let I and J be countable index sets. Let A = {Ai.j}i61.j€J be a matrix and TA be the associated operator taking a sequence a: = {lejEJ to T)”: = {(TAx),},-el, where (TAz), = 2,- A,,J-:rj. Assume that B = sup: [AM] < +00 3 i and C = 511.92 [Am] < +00. ' j Then TA :12(J) —-) 12(1) is bounded with ”TA“12(J)—>I2(I) S @- Proof: |(TA$)1| S 2 IAifljl J = ZIA,,j|‘/2|A,,j|1/2|x,| J |/\ 1/2 1/2 (2 [14,01]) (2 [A1,jll33jl2) (Cauchy-Schwartz inequality) j j 1/2 S 01/2 (ZIA.,)II$,VI2) - ,- Hence XEKY‘AIL‘LI2 S 0;;IA13H331V = CZ|$1|2;IA1.J'| 3 BCJZIIBJ'V- ,- Thus “TA”19(J)—>12(I) S V BC. 26 C] To apply Schur’s lemma to S—L wavelets and the S—L cp-transform, we need to verify the conditions in Schur’s lemma. We first prove the following lemma. Lemma 3-4 Define {‘Pumluezmzl by (217) and {tbchlueZchl by {3..8) (a) UV — 11 ¢ {2,3,4,5}, then < wand/Ia): >=0. (b) IfV—p E {2,3,4,5}, then for each M > 0 there exists CM < +oo, CM independent of V, n, p, k, such that GM (1+In7r — 2""“(k —1/2)|)M. l< Wad/1.1.1: > I S (c) We have B = supZ I?” < sown/1...). > I < +oo “’1‘ um and C = supz |2“‘” < $0u,m¢u,k > I < +oo. V,n ch Proof: (a) By the Parseval identity (2.15) < Spa/mafpmk > = < 9511,11, 11511.1: >p’ = [m¢.,.(€).t.,.(é)p'(é)de _ [m ‘P(2‘”€)2’("‘1)/2sin(2_”n7rfl 1 2‘V/2V1w(2’V6)sin(2“V(k - 96) o (19%))”2 x/iir ()0’(~€))‘/2 p’(€)d€ = fin-(“”2 [.00 cps-Vowe-V5)sz‘n12-erc)sz'n(2-V(k — —)¢)d: 2 1 2 TH‘V‘V’” [0... ww<2V-Vy)s1n(nvry)sz'n(2V“‘<’V — ill/W = figs—1)). f.” so(y)w(2VVVy)1cos((mr - 2V-V(k — —)y) — cos((n1r + 2"““(k — %)y)]dy. Since suppcp Q [1/4, 1] and suppw Q [27r/3,87r/3], we must have y E [1/4,1] fl [2“"’21r/3,2“"’81r/3] for go(y)w(2"“‘y) 31E 0. This requires 2“""87r/3 > 1/4, i.e. V - p S 5, and 2“"’27r/3 < 1, i.e. V —- p _>_ 2. This proves (a). (b) For each V - p E {2,3,4,5}, the function go(y)w(2""‘y)x[o,°0](y) is C°°(R+) and has a compact support, and hence belongs to the Schwartz space S (R) It follows 27 that its Fourier transform is rapidly decaying (this can be proved by integration by parts). For each M > 0, we have I < 50mm 1%,): > I CM + CM (1+ [nir — 2“‘“(k — l/2)|)M (1+ |n1r + 2"““(k —1/2)|)M' Since n, k 2 O, the second term above is determined by the first. The result (b) now follows. (c) Let M _>_ 2 in (b). Then B = supz2“—”I < (pu,n,t/),),k > | “9" VJ! 2”_VCM < - 8.35;;(1 +|n1r — was —1/2)))M 5 oo 2—mCM ‘ 315;: (1+ Imr — 2'"(k —1/2)I)M 5 °° 2-mCMdCC < - 8:11.);2/0 (l+|:c7r—2m(k—l/2)|)M = supCj'w p,k < 00. Similarly, C = SUPZ Izu-V < 9011,11, wink > ] < +00. V,n Mk Cl Based on the two lemmas above, we have the following norm equivalence theorem. Theorem 3.3 Define {ibu,k}uez,k21 by (3.8). Suppose f: [0,oo) —-> R satisfies f E C2([0,oo)), f(0) = 0, limit...» f(x) = O, and lim,,,_,co K(:r,5)f’(a:) = 0 for all5 2 0. Then for S-L operator L[y] E —j: + q(x)y, we have < Lf,f >2 2 i I2“ < fut“). >|2, (3.20) #62 lc=l i.e., there are constants Cl, Cg, which are independent of f(x), such that 012 2 I2“ < fab“). >|2 s< Lf,f >3 02 Z 2 I2“ < M... >I2. #EZ k=l uEZlczl 28 Proof: By Theorem 2.8, we have 2 Z I?” < My). >|2 < Lf,f > 2 VEanl oo oo 2 = Z:2u<22¢mkasoum> VEZn=l uEZkzl (by Theorem 3.1) 2 Z ZZu—p < $11.10 cPmn > 2“ < f, 1A).}; > #62 k=l =25? VEZ n=1 By Lemma 3.4, the matrix A = {Amm’k} = {2""‘ < ibu,k,1p,,,n >} satisfies the conditions of Schur’s lemma and hence is l2-bounded. This gives < Lf,f >3 ”AMP-+12: 212V < f. 11... >12. #62 lc=l For the converse estimate, we have, by (2.16) 00 2 Z 2: [2” < fflt’ch >l uEZk=l 00 2 oo = Z 2u99V,mQ/Jp,k> pEZ k=l VEZn=l : Z Z Zzfl-V < somnatbmk > 2V < f, 1162 :1 VEanl 2 a- By Lemma 3.4, the matrix B = {Baku/.71} = {2“"’ < sou,n,¢p,k >} satisfies the conditions of Schur’s lemma. Hence 2 Z [2“ < fall’ch >l2 S ”Blip—H? E Z [2” < fa‘PVm >l2 pEZ k=1 VEZn=l < C < Lf,f > (by Theorem 2.8). 29 Chapter 4 Fast Sturm-Liouville transform We shall give a general fast algorithm for evaluating S-L transforms in this chapter. There are two steps for the algorithm. In step one, we use the fast S—L wavelet transform to obtain N S-L wavelet coefficients from N spatial function values. The computational complexity for this step is O( N) or at most 0(NlogN). In step two, by the special structure of S—L wavelet bases, we can evaluate the wavelet series in spectrum by the Fast Fourier Transform (FFT). The computational complexity for this step is 0(NlogN). In Section 4.1, we apply multiresolution analysis to S-L transforms and give a fast S-L wavelet transform. This section not only provides the first step of the fast S-L transform but also gives us an important part of the S-L wavelet theory. In Section 4.2, we present the second step of our algorithm. Finally, in Section 4.3, we apply the ideas of our algorithm to a concrete S-L integral transform— the Hankel (Bessel) transform, and show that the Parseval identity and the decay property of father wavelets are the essential ingredients of our fast algorithm. 4.1 Fast Sturm—Liouville wavelet transforms We shall construct fast S-L wavelet transforms in this section. The basic idea of the fast S-L transform is similar to the one for standard wavelet transforms. There are two essential ingredients. One is the adjacent two level relationship. The other is the localization property of wavelets. We first construct a two level relationship in the S-L spectrum. Then, taking inverse S-L transforms, we obtain a two level relationship in space. Let 23(5) and h(5) be the father wavelet and mother wavelet for Meyer’s wavelets in spectrum. We use 30 the definition given in [3] (pp. 137 and 117): l 21r 27r’ [6] S '3', 12(5) = 71-;005 (ix/(21.15) — 1)), — s IEI s — (4.1) 0, otherwise, ‘ _ _l_ 15/2 h(C) - V276 10(6), (4-2) where w(5) is the window function given by (3.2) and V(5) is defined by (3.3). It follows that there exist 27r periodic functions mo(5) and m f(5) such that ([3], p. 138) 13(6) = mo(€/2)9(€/2) (4-3) and 13(5) = m;(€/2)13(€/2)- (4.4) In fact, m,(5) = eiémo(5 + 1r). For Meyer’s wavelets, m0(5) = \/2—7ereZ i)(2(5+27rl)). At the V-th level, (4.3) and (4.4) become 1‘42"?) = mo(2_("+1)€)5(2-("+1)€) and Ila-Vs) = m)(2“VV"§)é(2“V+”£). Then, by (3.4), we have —2Im(iz.,.(5)) = —2-V/2+‘Im(iz(2-V§)e"2‘"“‘) —2_y/2+1Im(mf(2-(V+l)€)6(2-(V+l){)e—iZ-Vké) = _2-v/V+11m(e-12‘VU=-1/V>Vmo(2-5 + 7r)é(2“V+"§)) 911,1:(5) Since mo(5) and 6(5) are real, 9.4.(5) = 2‘V/2Jrl~‘>‘in(2_"(k — 1/2)€)mo(2’(”+1)€ + WWW—(WIT)- (4-5) Since mo(5) is an even 27r-periodic function, we can expand it in terms of {cos(l5)}}’_°j__0: mo(5) = iC)cos(l5) 5 Z 0. (4.6) l=0 31 Thus, m0(2‘(”+1)5 + 7r) = ZC;cos(l(2'(”+1)5+ 7r)) l=0 f(—1)'Czcos(1(2-y,k(x) satisfies the correct decay and dilation estimates, i.e., l¢u,k(x) < C , f > 0, >1, 4.11 |_1+2‘“’|:1:—x,,,k|fi or a '6 ( ) where C is a constant independent of u and k, for {mm} which is a set of points with limk_,00 12”,), = +00. Section 4.1 contains for numerical evidence of this property in the case of the Hankel (Bessel) transform, which is one variant of the case described here. Based on the above localization assumption for 45”,],(11), we shall show that there exists a fast S—L wavelet transform, which transforms N = 2"° function values { f (33%),) }15k52vo in space to N = 2"° wavelet coefficients {< f, 1/Ju,1c >}OSV}. Let 5 be the threshold error and let A, be a positive constant such that Ink-Av Cda: 0° Cda: < d f . 4.12 /. 1+2°”|x—mu,kl" 5 a“ ..,.+A.1+2av|x—x.,.lfi<5 ( ) 33 From (4.12), we have C’ 1+! A” < (5201’) where C’ is a constant depending on a, ,3, and C. Choose the level V0 such that ll 0’ V0 > ; 0g2 W . Then A30 < 5. (4.13) Assume that f (x) is a compactly supported Lipschitz continuous function, i.e., |f($)-f(y)| < le-yl, (4-14) where L is a Lipschitz constant. With this assumption, f (m) is a bounded function, i.e., |f(-“B)| < 3, (4-15) where B is a constant. Since f (x) is compactly supported and {¢m,k($)} are rapidly decaying functions, there is a positive integer N such that I < f, 43%,), > I < 5 for k > N. Therefore for the level V0, we need only to compute coefficients {< f, 43%,), > }1$k_<_N- Without loss of generality we assume that N = 2V0, For each I: _>_ 0, < fa¢uo,k > jam f(x)¢,,o,k(:c)d:1: .1: , —A :1: ,+A oo = / "°" ”° + / "°" "° + / f(w)¢uo,k(a=)dw 0 xm’k_Ayo xu0,k+Auo By (4.11), (4.12), and (4.15), we have $90»"’AVO xyka—AVO I] f(x)¢...k(x)dx s B] 1¢..,.(x)ldx 0 0 S Be. Similarly, f°° f(x )1... .1 )dx < Be. xvo.k+Avo Thus, < fa¢uo, k > = [”'::”1H(x)¢..k( )dm+0(e) yo. yo wqu-k ,(uok-i-Auo = f(x...) . _ :10“. )da:+ /. _. (J‘(x)-f(:vuo,k))¢uo.k(:v)dsv+0(6)- 34 By (4.11), we have |¢uo,k(x)| S C. Then by (4.14), ’m#+Am L (f(x) — f(x..,.))¢...k(x)dx mk'Am :1: '+A s L "°" ”° lx—xuo.k||¢uo.k(w)ldw xVOIk-AVO :1: _+A S LC 1.01. me—xuo,k|da: 3u0,k-Avo = LCAa = 0(5). Thus, LmJ+Am = mm] 1...k(x)dx+0(e) xmk‘Am = my”) (jam ¢,,,,,.(:c)d:c — 0(5)) + 0(5) 2 f(rvquc) low ¢Vo,k(z)d$ + 0(5). We denote f0°° ¢Vo,k(x)d:1: by Bum)" which can be computed once and for all at the outset (i.e., once for each choice of q(x) in (2.11) and the window function w(x) in (3.1)). Then the above equality becomes < f, 45.0,). >= f(.1:,,,,,,,)B,,,,,,c + 0(5) 1 g k g 2”°. (4.16) Therefore, we need one multiplication to compute each coefficient < f, ¢mG > and thus we need 0(2"°) multiplications to compute all of the coefficients {< f, 45%,), > }1Sk52V0 . We can obtain better accuracy than 0(6) as given in (4.16) by using more sophisticated quadrature. For step two, let us determine the computational complexity of computing {< f, 1/1uo,k >}ogu}151¢52uo. By (4.9) and (4.10), we have the following two level relationships between projections: < f , $11.1: > = fii(_1)lcl l< fa¢u+1,2k—1+1 > + < f,¢u+1,2k—1—1 >], (4-17) < f aim/c > °° C fl: 31 i< f9 ¢V+1,2k+l > + < faqSu-Hflk—l >1. (4-18) (:0 Similarly to the standard wavelet transform, we begin with {< f, $110.1: >}1Sk52uo and compute {< f,¢,,o_1,k >l1§k§2”°"1 and {< f,¢,,o_1,k >}lsk32"°“ by (4.17) and 35 (4.18). We then use {< f, 43%-”; >}15k32Vo-1 to compute coefficients at level V0 — 2. We repeat the above procedure down to level 0. By the decay property of Meyer’s wavelets, we know that limH00 C; = 0. For a given computer roundoff error 6’, there exists L such that |Cz| < 5’ for all 1 > L. Therefore, the summation 22:0 in (4.17) and (4.18) can be replaced by 21:0 for computational purposes. Thus it requires 0(L2") multiplications to compute the co- efficients of level u from those of level V + 1. If L << V, then, the computational complexity is 0(2"). If L 2 V, noticing that (4.17) and (4.18) are discrete convolu- tions, we can use the FFT to evaluate (4.17) and (4.18) in 0(1/2") multiplications. By steps one and two above, we see that the total number of multiplications for the S—L wavelet transform is of order 0(Vo2”°)+0((1/o— 1)2("°‘1))+- - -+0(2)+0(1) = 0(Vo2”°), i.e., 0(NlogN). 4.2 Fast Sturm—Liouville transforms From the last section, we see that we can compute N = 2"° coefficients {< f, (Pym), > }0$u. By the Parse— val identity (2.15), we have < f9 $14k >p':< fa $14k >= fch- Since {zfiu’k(§)} is an orthonormal basis in L2([0, oo), dp), we have 00 2" A 1. A f(é) : z: Z < fa $11.1: >p’ ¢V,k(€) Uz-OO 1c=l A A A ”(J-1 2” A A A < fa¢0,l >p’ ¢0,1(€) + Z Z < fa $14k >p' $11,146) 11:0 k=l 110-1 2" = < fa450,1><130,1(€)+ Z 2: £113.41). (4.19) 11:0 1c=1 22 The goal of numerical S-L transforms is to convert N function values { f (mu,k)} to N spectral values {f(§n)}. Here, let 6,, = 53171 for 1 S n S N. A straightforward evalua- tion requires 0(N2) multiplications to compute { f (5111115123 N by (4.19). However, if we use the special structure of 11,4145), we see that (4.19) is similar to a windowed sine transform and only 0(NlogN) multiplications are required to evaluate {f(§n)}lsn51v. Substituting (3.7) in (4.19) we have A f(E) 36 = < fa¢o,1 > 91504101)”: zfuk—fZ ”/H‘SMZ l’(1‘7—‘1‘)€)(—’p_“-12‘f(( Sis/)2 11:01:: 1 = < 1.1.. > 101(1) 110—1 -11 2—11/2+1____ w(2 £1 7:121- Z an- Let B), = {{nhugnaun, for 0 S p S 110 — 1. Since suppw(2“’€) C [2"27r/3,2"87r/3], for all {n E B”, we have w(2""£n) : 0 if 11 75 p or 11 — 1. Therefore, for all €11 E B“, (4.20) becomes 3:1 fuksin(2 ”(k —- §)§). (4.20) f(é.) - <11 >1 (:)+—2*‘/”+‘w——(2_")€" 21 moms k—lx) _ 1 0,1 0,1 11 \/§_ (p,(€n)) ))l/2 11,1: 2 n w (11 1) 21‘- +"\/i2—-;2 (ii—”fl“ ($021“- :))1f2) k; fu— 1,kSzn( (2 (“ l)(k-- —)€n) (4.21) In B”, there are 2“+1 — 2“ = 2“ Q’s. To compute f(én) for all {n E B” by (4.21), we need 0(2") multiplications to evaluate the first term < f, (1)0,1 > 6503““). For the sec- ond term, we need 0(112") multiplications to evaluate the sum 2:; fu,ksin(2"‘(k — ‘96:) using the FFT. Then we need 0(2“) multiplications to multiply (W by the sum. The third term is similar. Thus, we need a total of 0(2") + 0(112“) = 0(112") multiplications to compute f({,,) for all En E B. To count the total number of multiplications, we take a sum over 11, i. e. ,2)“; 0(112“): 0(1102"°) = 0(NlogN). Combining the fast S-L wavelet transform and the the above synthesizing pro— cedure, the total computational complexity is 0(NlogN) + 0(NlogN)= 0(NlogN). Therefore, this algorithm can transform N function values { f ($111)} to N S—L spectral values { f (511)} in 0(NlogN) multiplications. 4.3 Fast Hankel (Bessel) Transforms Thus far, the fast S-L transform algorithm has been described for integral transforms generated from S-L problems in their normal form (2.11). In this section, we apply the same ideas to the Hankel (Bessel) transform to show that the algorithm also works for integral transforms generated from a general form S—L problem. In fact, the algorithm even works for an integral transform that may be unrelated to any S-L problem so long as the integral transform has a Parseval identity and the father wavelets {(16,443)} have the correct decay properties. 37 We recall the following from Section 3.2. that the Hankel (Bessel) transform is given by: F(s) =1))=/°°1(11()1§ 111 1(1) 6 L2((o,oo),1d1) 1(1) = F((E) )= /°° F(s)1.(11)111, F(s) e L2([o,oo),sds) where Jn (2:5): K,(2: {) IS a solution of the Bessel eigenvalue problem given in (3.11). Also, there IS a Parseval identity x=/000f($)g():rd2:=/:F(€ §)§d§ =,.5 Similar to (3.7) and (4.8), we define Hankel (Bessel) wavelets as: 9:1. (5) -_2—V/2+1 11 12 1.,.(1)=(—€’:—,5—) — 1271 [f 111(2 (1—§)s-)w(2 01(101/11, and ¢11,k(x) : (2- 11/28 “Ia-11kg) v(:;:€)). = 2“”? [cuisine-"km 01(1011/215 To give a fast Hankel (Bessel) transform, we first check whether the fast Hankel (Bessel) wavelet transform holds. To do this, we need to verify the two level rela- tionship (4.9), (4.10) and the decay property (4.11). It is straightforward to check that (4.9) and (4.10) are indeed true. Regarding decay, we have numerical evidence indicating that the functions {¢V,k(2:)} have proper spatial localization. In Fig. 4.1 and Fig. 4.2 we plot Hankel (Bessel) father wavelet functions ¢0,1(2:) and (120.1112) for J1(:c) using MATHEMATICA. In the window function w(m) in (3.2), we choose 11(2) = 2:4(35 — 84:: + 702:2 — 202:3)(cf. [3], p.119). We can see from these figures that (120,1(2) and ¢o,1o($) are rapidly decaying func— tions. It is interesting to note that ¢o,1o($) has smaller amplitude than (120.1(2) because the weight 2: in L2([0, oo),:cd2:). Once the fast Hankel (Bessel) wavelet transform holds, by the Parseval identity, we know from the last section that there exists a fast Hankel (Bessel) transform. From this example for the Hankel (Bessel) transform, we can see that the Parseval identity and the decay property are the ingredients for obtaining a fast algorithm for an integral transform, whether or not the transform is related to a S-L problem. 38 fix 5 “7.5 10 12-. 17-. [,1 Figure 4.1: Hankel (Bessel) wavelet ¢o,1(:c) for J1. Figure 4.2: Hankel (Bessel) wavelet (1030(2) for J1. 39 Chapter 5 Fast solvers for singular differential equations To solve a linear elliptic differential equation (a PDE or an ODE) numerically, Galerkin methods are used to convert the differential equation into a linear alge- braic system. One way to solve the linear algebraic system is by iterative methods. The computational complexity of an iterative method is proportional to the prod- uct of the number of nonzero entries and the condition number of the matrix of the linear system. For a finite element method, the number of entries is 0(N) (the ma- trix is sparse) and the condition number is 0(N2) (the matrix is ill-conditioned), where N is the number of unknowns. By preconditioning, the condition number can be reduced to 0(N) for a finite element method. However, if we use a wavelet basis for the Galerkin method, the condition number will be 0(1) after being pre- conditioned by a diagonal matrix. Therefore, the complexity of the iterative method is 0(N) X 0(1) = 0(N) rather than 0(N) x 0(N) = 0(N2) for a finite element method. Thus, the wavelet-Galerkin method gives us fast solvers for linear elliptic differential operators. Unfortunately, if we use existing wavelets associated with the Fourier transform, we have fast solvers only for regular elliptic differential equations with almost constant coefficients. Here, almost constant coefficients mean variable coefficient bounded above and away from zero below. One thus questions if there exist bases which give fast solvers for singular differential equations. Here by singular differential equations we include those with variable coefficients not bounded from below or above. We shall show in this chapter that our S-L wavelets give fast solvers for singular differential 40 equations related to S-L operators. For simplicity, we consider here only one dimensional elliptic differential equations, i.e., ODEs. The method here can be easily generalized to higher dimensional cases involving simple domains. We give a review of fast solvers for elliptic differential equations with almost constant coefficients in Section 5.1. Then in Section 5.2, we present our results on fast solvers for singular differential equations. 5.1 Review on fast solvers for differential equa- tions with almost constant coefficients This review is based on S. J affard’s article ([10]). For simplicity, we consider here only the 1-D case whereas the 2-D case was considered in [10]. We consider the following elliptic differential equation with Dirichlet boundary conditions _% (a(x)d::t)) + b(2:)u(2:) = g(2:) 0 < x < 1 (5.1) and with the conditions 0 < Cl S a(2:) 3 C2 < +00 (5.2) 0 < b(2:) S C3 < +00. (5.3) The variational form of (5.1) is du dv 1 5,31; > + < b(2:)u,v >—< 9,?) > for all 11 E H0([0,1]) (5.4) Where H3 = {f(x) 1 f(0) = f(1)= 01% E 112((0, 1))} and < fig >= fol f’($)g'($)d$- The Galerkin approximation of (5.4) is to find 11 = qu,n\ll,,,n(2:) in V”o = span{\Il,,,n(2:),0 < 11 < 110,0 S n < 2"} C H6([0,1]) such that for any 1) E VVO, (5.4) is true, i.e., < a(:r) {< a($)‘pi1,m‘pir,k > + < b($)‘Du,m Wm}: >}{Xu.k} = {< 92‘111121 >} where summations implied in the tensor notation are understood. In abbreviated form, we can write the equation above as M X = Y, 41 where M = {< a(2: )lllfmfill’ k > + < b(x )\II,,,,,,\II,,,;c >}, X = {X1111}, and Y = {< g,\Il.,,n >}. In the above approximation, {\Ilm} are special basis functions for H6([0, 1]) con- structed by S. Jaffard and Y. Meyer ([11]). The {Wm} have the following norm equivalence property: 04 Z (211...)? s ((1)11, s 05 z: (211...)? (5.5) where {cm} are coefficients of the expansion f (2:) = Zcm‘IImCr) E Vuo. Denoting {cm} by A, we then have ATMA=+. Since there is a C6 > 0 such that llfllng — ll;- :1le < Cellfllu for any f 6 H6, we have ATMA = < a(m) >+ IV _f__f dx’xd _f__f_ dx’a:d IV c.1111,- Similarly ATMA = + 02113—1”2 + CallfllL2 (02 + a:Csc'elllfllyg- |/\ |/\ Hence C1llflli13 s ATMA s (02 + 0301)Ilflli,,;. By the above inequality and (5.5), we have 0401 212”cu,,,|2 g ATMA g (35(012 + C304) 2 |2"c,,,,,|2. If we choose B = {2"cm}, then C,C,||BII?1 s BTD-‘MD-IB 3 05(02 + 0306)||B||,22 42 where D = {2”6w6km} is a diagonal matrix and D'1 = {2""6u,u6k,n}. Since B can be an arbitrary vector, the eigenvalues of the preconditioned matrix D‘lM D"1 are bounded from above by 05(02 + 0306) and from below by C401. Because D‘1 M D‘1 is symmetric, Am” 05(02 + C306) Amin C401 where C" is independent of the size 110 of the space VVO. Thus, we have cond(D‘1MD"1) = O( 1). c0'nd(D‘l MD’I) = |/\ = C’, 5.2 Fast solvers for singular differential equations In this section, we show that the Galerkin approximations using S-L wavelets give fast solvers for singular differential equations related with S—L operators. Coefficients of these singular differential equations do not satisfy conditions (5.2) and (5.3). We give two reasons for having fast solvers for singular differential equations using S—L wavelets. First, the approximation matrix can be preconditioned by a diagonal matrix to a matrix with condition number of 0(1). Second, the approximation matrix is sparse. Since the S-L wavelets are generated from S-L problems in their normal forms, we consider singular differential equations in normal forms. Other forms can be transformed into such normal forms by the Liouville transform. Thus, we consider the following problem Lu = -— + q(x)" = 9(56) (5-6) 11(0) = 0, u(oo) = O, (5.7) where q(x) can become unbounded at :r = 0. For example, in the normal form of the Bessel equation, q(x) = (1/4 — n2)/2:2. The weak form of (5.6) is < Lu,v >=< g,v > for all 1) E S([0,oo)), (5.8) where S = {1 = 1(0) = 1(oo) = o, 1.11 1 1220,11)» and < 1.1 >= 11° 1(1)1(1)d1. In the Galerkin approximation, we let u = 2 M1,," and v = 1,11,,» Both 11 and v are in the finite—dimensional space V,,0 = spanfdhqmo < 11 < 110,1 3 k g 2"}. {11%,} are S-L wavelets defined by (3.8). Then (5.8) becomes {< [111014111 1£11,]: >}{X11,n}:{< 911%,]: >}- 43 where summations implied in the tensor notation are understood. In abbreviated form, we can write the equation above as MX = Y. (5.9) Let 1(1) = 21....1... e v... and A = {1...}. Then ATMA =< Lf,f >. By Theorem 3.3, we have C'1::|2"c,,,n|2 S ATM/l S C2 2 [2"cmlz. If we choose B = {2"cum}, then 011181112 5 BTD-lMD-‘B s CzllBII1 where D = {2”5u,,,6k,,,} is a diagonal matrix and D’1 = {2'”5,,,,,5k,n}. Since L is a self-adjoint operator, M is a symmetric matrix. Hence c0nd(D—1MD—l) = Am” < ——- = C", where C’ is independent of the size 110 of the space V10. Thus, we have cond(D'1 M D") = 0(1). Another important reason for our having fast solvers is that the matrix is sparse. We shall establish the sparseness of the approximation matrix M in (5.9). S-L wavelet bases are multilevel bases. Generally speaking, for a multilevel basis, two properties of the basis are important for leading to the sparseness of the approximation matrix. The spatial localization property of a wavelet basis gives the sparseness of the ap- proximation matrix in one level while the spectral localization property of the wavelet basis generates the sparseness among different levels. Since multilevel non-wavelet bases (multilevel finite element bases) are not localized in spectrum, approximation matrices are not sparse among different levels. In this work here, the idea in the proof of the sparseness of the approximation matrix is slightly different from the general idea given above. As we will not include a general proof of the spatial localization property in this dissertation, we shall establish the sparseness in one level by the fact that same level S-L wavelets are orthonormal ' in spectrum. 44 Theorem 5.1 The entries {Mmm’k} ofM in (5.9) satisfy (a)IfIV-11l>1 M11,n;11,k = 0) (5)1fIV-IJISI 22110M Mun‘ < ' ' 2’" - (1 + In — 1/2 - 21-1111 -1/2)()M where M > 0 and CM is independent of 11,n,11, and 1:. Proof: By Lemma 2.4, we have (Lfinflé) = (215,“). By the Parseval identity (2.15), < Lgbmnpu,” > = <(L7/21..),J.,:, >,,: = fez/17.211751011101115 (a) By the assumption on the support of w(fi) in (3.2), 112%,, and 15“,), have disjoint supports if |11 — 11] > 1, and (a) follows. (b) If I11 - Ill S 1, (3.8) gives < LIAM, 21),“); > = i2-<”+“”’ [00°121(2-2)w(2-"1)111(2-”(n — 1/2)1)ez'n(2-"(1 - 111011 = 1242“)” [00° 5212101211)(111((2-"(1 — 1/2) — 2‘~(1 — 1/2))£) —cos((2"’(n — 1/2) + 2’"(k — 1/2)){)]d€ = £20211” [0 221121111111)(coe(((n —1/2) — 221(1 — 112))1) -003(((n -1/2)+ 2""“(19 *1/2))y)ldy Then for each value of 11 — 11 6 {—1,0, 1}, y2w(2""‘y)w(y) is a Schwartz function supported in {y : 1/4 < y < 1}. Hence its Fourier transform is rapidly decaying. Thus I < qumawmk > I < CM2211 + CM2211 _ (1+ Kn -1/2)- 2"““(’c -1/2)|)M (1 + K71 -1/2)+ 2"“‘(k -1/2)|)M Since n, k > 0, the second term is dominated by the first. Hence (b) is proved. D 45 Corollary 5.1 The preconditioned matrix R = D"1MD'1 satisfies (a) HIV-Ill >1 R11,n;u,k = 0) (b)1f|V-1t|£1 CM , < IRu,n,u.kl — (1+ In _1/2 — 2“"“(16 —1/2)l)M where M > 0, CM is independent of 11,11,11, and 11:. Proof: The proof follows from Theorem 5.1 and the definition of D". D From the above corollary, we see that 1211.1:ch decays very fast away from the diagonal and some sub-diagonals. Therefore, it is a sparse matrix. 46 Chapter 6 Discussions and concluding remarks One main motivation for research in this dissertation is to construct fast solvers for differential equations. As standard existing wavelets give fast solvers for regular dif- ferential equations. The S-L wavelets constructed here provide fast solvers for a much larger class of differential equations including those involving singular differential op- erators. The key idea behind S-L wavelets is that they are constructed directly from S-L differential operators and the corresponding S-L integral transforms. We have thus linked together wavelets, integral transforms, and differential operators. The underlying idea behind our approach is fairly general and may be extend in other directions as discussed below. It will be interesting to explore the relationship between wavelets and orthogonal polynomials such as Legendre polynomials and Chebyshev polynomials. Such orthog- onal polynomials play important roles in the numerical solutions of solving differential equations though they are not localized in space. It is known that orthogonal polyno— mials may be generated from S-L eigenvalue problems, usually with discrete spectra. It is possible to construct wavelets from the S-L problems following the procedure in this dissertation, but it may be difficult to establish the spatial localization of the wavelets by following the argument for continuous spectra in the dissertation. Such spatial localization may be verified by numerical experiments. Another possibility for treating the discrete spectrum cases is to construct wavelets from the spatial side, similar to the construction of local sine or cosine bases. Also, we wish to find kernels K (2:, 6 ) for S-L integral transforms. In the construc- 47 tion of S—L wavelets we have assumed that the corresponding S-L transform is known. In other words, the kernel K(:1:,£) is given. However, the kernel K (2,6), which may be regarded as the eigenfunction for a S-L problem, is usually not known. We need to find it either numerically or analytically. One favorable property of wavelets is that wavelets for one differential operator L = %(a(2:)fi-) + M2)??? can give fast solvers for a class of differential operators L: = %(cl(2:)a(2:)%) + c2(2:)b(:c)gd; where 0 < c1(2:),c2(:r) < 00 (see Chapter 5). For a class of S-L problems related to LC, we only need to find one K (2:,{) of a S—L problem. Thus, it may be possible to obtain one K (2:, 5 ) analytically by choosing right c1(z) and c2(2:). Once we have found one K (2:, E ), we can then use wavelets generated by this kernel to compute the remaining kernels efficiently. Another direction for future research concerns 2—D (or higher dimensional) wavelets for solving PDEs. For l-D problems, we may regard wavelet Galerkin methods as some methods in—between finite element methods and spectral methods. In fact, wavelet Galerkin methods have the advantages of both finite element methods and spectral methods. Wavelet Galerkin methods provide fast ways to solve differential equations. It is natural to expect that 2—D wavelets will provide us with fast solvers for 2—D PDEs. However, there do not exist many 2-D wavelets for non-rectangular domains. Tensor products of l-D wavelets have been used to generate 2-D wavelets for rectangular domains. However, there is no straightforward way to generalize l-D wavelets to 2-D wavelets for non—rectangular domains. Similar to the generalization from standard wavelets to S-L wavelets, we must first define and delineate desirable properties of 2-D wavelets. Then we must understand the underlying reasons for each desirable property in the construction of 2-D wavelets. If possible, we wish that these 2-D wavelets have compact supports. Further along this direction, we would ulti- mately like to construct 2-D wavelets for singular PDEs. The construction of 2-D (or higher dimensional) wavelets will be an important research topic direction because of their potential applications. Even moderate success in this direction will be greeted by researchers outside of the wavelet research community. Finally, we wish to understand the relationship between wavelet bases and other multilevel bases and that between wavelet Galerkin methods and multigrid methods. We believe that wavelet methods and multigrid methods are somehow related and properties such as those on spatial localization, spectral localization, or Littlewood- ‘ Paley decomposition in spectrum may help to bring new insights to multigrid meth- 48 ods. Researchers have been attempting to use wavelets to solve differential equations in the last five years or so. Such attempts have been successful to some extent but they are not as successful as finite element methods. There is not as yet commercial PDE package using wavelets. In fact, there may still be a long way to go to archive this purpose. However, this does not rule out future success in this regard. With the nice properties of wavelets, it is believed that there will be better and faster commercial PDE packages in the future. Wavelets may remain under the name of finite elements for a while, but we believe that the ideas behind wavelets will permeate commercial PDE packages and make the latter better and more efficient. 49 Bibliography [1] B. K. Alpert and V. Rokhlin, A fast algorithm for the fast evaluation of Legendre expansions, SIAM J. SCI. COMPUT. Vol. 12, No. 1, pp. 158—179, January 1991. [2] Birkhoff and G.-C. Rota, Ordinary Difierential Equations, John Wiley & Sons, New York, 1978. [3] I. Daubechies, Ten Lectures on Wavelets, CBMS—NSF Reg. Conf. Ser. Appl. Math. 61, Philadelphia, SIAM, 1992. [4] B. Davis, Integral Transforms and Their Application, 2nd ed. pp 267-268, Springer-Verlag, New York, 1985. [5] J. Epperson and M. Frazier, An almost orthogonal radial wavelet expansion for radial distributions, J. Fourier Anal. and Appl. Vol. 1 pp. 311-353, 1995. [6] J. Epperson and M. Frazier, Polar wavelets and associated Littlewood-Paley the- ory, to appear in Dissertationes Mathematicae. [7] G. Folland, Fourier Analysis and its Applications’ Brook/ Cole Publishing Com- pany, Pacific Grove, CA, 1992. [8] M. Frazier, B. Jawerth, and G. Wesis, Littlewood-Paley Theory and the Study of Function Spaces, CBMS Conf. Lect. Notes 79, Providence, AMS, 1991. [9] M. Frazier, S. Zhang, and Z. Zhou, Sturm-Liouville wavelets, in preparation. [10] S. Jaffard, Wavelet methods for fast resolution of elliptic problems, SIAM J. NUMER. ANAL. Vol. 29, No. 4, pp. 965-986, August 1992. [11] S. Jaffard and Y. Meyer, Base d’ondelettes dans des ouverts de R”, J. Math. Pures Appl. Vol 68, pp95-108, 1989. 50 [12] B. M. Levitan and I. S. Sarjsjan, Introduction to Spectral Theory, Translations of Mathematical Monographs Vol.39, AMS, 1975. [13] B. M. Levitan and I. S. Sarjsjan, Sturm-Liouville and Dirac operators, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1991. [14] Y. Meyer, Principe d’incertitude, bases hilbertiennes et algebres d’operateures, Seminaire Boubaki, 1985—1986. [15] S. A. Orszag, Fast eigenfunction transforms, in Science and Computers, Ad— vances in Mathematics Supplementary Studies, G. C. Rota, ed., Academic Press, New York, 1986, pp.23-30. [16] I. Stakgold, Boundary Value Problems of Mathematical Physics, McMillan, New York, 1968. 51 "11111111111111115