Multivariate Refinable Function And Its Applications

This dissertation has ?ve parts including preface and conclusion. Our mainresults covers chapter 2 to chapter 4.In the part of preface(chapter 1), we have brie?y introduced the history ofwavelet analysis, re?nable function and subdivision including the background ofthe dissertation.In chapter 2, we have investigated the characterization of a compactly sup-ported spline funcion ? de?ned on simplex in Rn. We have given the necessaryand su?cient condition of ? beging M-re?nable, where M, the dilation matrixof the re?nement function, is an n×n integer matrix with the norms of all itseigenvalues greater than 1. Furthermore, we have gived a necessary and su?cientcondition of the shifts of ? forming Riesz basis.In chapter 3, we have investigated the existence of prewavelets with ?nitedecomposition and ?nite reconstruction. The su?cient and necessary condition ofthe existence of these prewavelets and some equivalent condition are presented.Especially when r = 1 , we show that {?j(x ? k) | 1≤j≤r,k∈Zs} isshift-orthogonal if there exist prewavelets with ?nite decomposition and ?nitereconstruction. As an example, when r = 2 we construct a prewavelet with ?nitedecomposition and ?nite reconstruction where the scale function is not shift-orthogonal, which demonstrate that there exist vector prewavelets with ?nitedecomposition and ?nite reconstruction.In chapter 4, First we have given an algorithm for segmenting a simplex inthe n-dimensional space into n + 1 cube-like polyhedrons. Second we provided map F which maps the n-dimensional unit cube to these polyhedrons. Using F,we transfer the subdivision of a rational surface on simplex to the subdivisionof a tensro product surface. Third, we prove that the map F is a one to onecorrespondence at least in lower dimensional spaces (n≤3). Moreover, wepropose the approximating subdivision and the interpolatory subdivision schemesand the estimation of computational complexity for triangular B′ezier patches ona 2-dimensional space. In the end of chapter 4, we compare our schemes withGoldman's in computational complexity and speed.Finally, we have brie?y summarized the research work in the dissertationand pointed out further problems to resolve.The main results from the dissertation can be listed as follow.1 Characterization ofM-Refinable Splines With Compact SupportLet A = (a1,a2,···,as) be an s×n matrix with integral entries and of rankn, s≥n. Vector aj∈Rn,j = 1,2,···,s. De?ne the Box-spline BA(x) with thehelp of Fourier transform:定义1.1 a1,a2,···,as∈Zn. We say the matrix A = (a1, a2,···,as) is unimod-ular if any matrix formed by any s linearly independent column vectors of thematrix A has determinant value±1.定义1.2 ?0 = {(x1,x2,···,xn)∈Rn;0≤xj≤1,∑jn=1xj≤1} is calledstandard simplex on Rn, and a simplexΔon Rn is a nonsingular a?ne transformof standard simplex, i.e.,Δ= AΔ0+c for some nonsingular matrix A and c∈Rn.∪定L义1.3 We say that {?j}jL=1 is a simplex decomposition of a bounded set E if is simplex for every j, andΔj∩Δl has Lebesgue measure zerowhen j≠l. 定义1.4 A functionφis called a blockwise polynomial if there exists a simplexdecomposition to the supporting set ofφ, such thatφis a polynomial onevery simplexΔj. Blockwise polynomial is also called spline in this paper.定义1.5 Let M be an n×n matrix with integral entries,ω∈Rn. A trigono-metric polynomial R(ω) is said to be M-closed if R(Mω)/R(ω) is a trigonometricpolynomial too.定理1.6 Let n≥2,φis a compact support spline, . Mbe a matrix with intiger entries and the absolute values of all its eigenvalues arelarger than 1. thena.φis M-refinable, if and only if it can be written asandi). BA(x) is a box spline de?ned on by (1.1), where A satis?esfor some constant c1;ii). k is a positive integer and satislies for the normal vectorof every sigular hyperplane of ?;iii). l∈Zn satisfies iv). P∏sis a polynomial that satis?es P(MTω) = c2P(ω), where P(ω) andj=1(aj·ω) don't have common factor, and c1 is a constant;v). R(z) = R(eEω) =∑j rjzj satis?es that R(z)∏js=1(zaj-1) is a MT–closed trigonometric polynomib. Furthermore, integer shift of ? forms Riesz basis if and only if 1). P ispolynomial of zero degree 2). A is unimodular 3). R(z) is a monomial. 定义1.7 A polynomial P is called a principal homogeneous polynomial if thereexist a natural number K and aj∈Rn, 1≤j≤K, such that P(ω) =∏jK=1 aj·ω.定义1.8 T(ω) =∑jαje?Eβjωforαj∈C,βj∈R is called a generalized trigono-metric polynomial.引理1.9 Let Pj (j = 1,2) be two nonzero polynomials, and Tj (j = 1,2) twononzero generalized trigonometric polynomials. If Pj and Tj (j = 1,2) satisfyP1(ω)T1(ω) = P2(ω)T2(ω), then P1(ω) = CP2(ω) and T1(ω) = C?1T2(ω) holdfor some complex number C.引理1.10 Let T be a trigonometric polynomial and T(ω) = 0 on plane aj·ω= 0,j = 1,2,···,N. Then there exist trigonometric polynomial R(ω) andτj∈R,j = 1,2,···,N such that T(ω) = R(ω)∏jN=1(eEτjaj·ω? 1), whereτjaj∈Zn,j = 1,2,···,N.定义1.11 For adjacent ?j and ?l, letπbe the plane which their n ? 1 di-mensional pubulic boundary is lying on. Then we callπa sigular hyperplane off if f(x)|?j and f(x)|?l are di?erent polynomials. Hence, all the planes pass-ing through the n ? 1 dimesional boundaries of the simplex support of a blockpolynomial function are sigular hyperplane.命题1.12 Let ? be a M?re?nable spline with compact support. Then thereexists an integer k∈Z such that (MT)k?j =λj?j, whereλj∈R, holds for thenormal vectors ?j of all singular hyperplanes of ?.命题1.13 Let ? be an M?re?nable spline with compact support. Then ?? canbe written as ?? =∑pqjj((ωz)), where pj(ω) are the principal homogeneous polynomi-als, qj(z) are generalized trigonometric polynomials, and there exist k such thatpj((MT)?kω) = cjpj(ω) for some constants cj,j = 1,2,···.引理1.14 Let M be a matrix with intiger entries, and the absolute value ofall its eigenvalue are larger than 1, T be a nonzero generalized trigonometricpolynomial and H be a nonzero trigonometric polynomial. If then e?ElT(M?I)?1ωT(ω) is a trigonometric polynomial for some l∈Zn.命题1.15 Let M be a matrix of intiger entries, and all of its eigenvalue be realand lager than 1. Then for a given nonzero trigonomitric polynomial H(z) ifq1(zM) = c1H(z)q1(z) and q2(zM) = c2H(z)q2(z) then c1 = c2 and there exist aconst c3 such that q1(z) = c3q2(z), where c1 and c2 are two nonzero constants,and q1(z) and q2(z) are nonzero generalized trigonometric polynomials.2 Prewavelets with Finite Decomposition and FiniteReconstruction定义2.1 Funcions fj(x), 1≤j≤N are de?ned on Rd. f1(x),f2(x),···,fN(x)are called as linear independent, if ?f =∑Ni=1 cifi(x) = 0, implicate ci = 0,i = 1,2,···,N. Furthermore, letΛ? Zd be a set. {fk | k∈Λ} are linearindependent, if arbitrary ?nite functions in the setΛare linear independent.定义2.2 Let S be a function space and {fk | fk∈S,k∈Λ} be linear indepen-dent. If ?g∈S, there exists a ?nite set ? ?Λsuch that g =∑k∈? ckfk, then{fk | k∈Λ} is called as a linear basis of S.{定理2.3 Let r∈N, x∈Rd, ?1(x),?2(x),···,?r(x) be functions de?ned on Rd.?j(x ? k) | 1≤j≤r,k∈Zd} be a linear basis of a function space S. Forj = 1,2,···,n, de?ne:w∑here aj,i(k)∈?0(Rd),1≤j≤n,1≤i≤r. Denote z = e?Eω, Aj,i(z) =k aj,i(k)zk, A(z) = (Ai,j(z))n×r. Then {ψj(x ? k) | 1≤j≤n,k∈Zd} isanother linear basis of S if and only if n = r and det(A(z)) is a monomial.定理2.4 If ?1,?2,···,?r are compactly supported functions. {?j(x ? k) | 1≤j≤r,k∈Zd} is a linear basis of a function space, {ψj(x?k) | 1≤j≤r,k∈Zd}is another linear basis of S. Then {?j(x?k) | 1≤j≤r,k∈Zd} is a Riesz basisif and only if {ψj(x ? k) | 1≤j≤r,k∈Zd} is a Riesz basis. 命题2.5 When r = 1, the linear basis of S is unique.Let r∈N, m > 1,m∈N, x∈Rd, and ?(x) = (?1(x),?2(x),···,?r(x))T bewhere Hk = (hj,i(k))r×r is a r×r matrix, k∈Zd. Denote H(z) = m1d∑k Hkzk.Then we have:De?ne subspace sequence Vj ? L2(Rd):where overline means closure of a set. If subspace sequence Vj satisfy is Reisz basis of V0.Then we say ? generate a MRA(multiplicity r) of L2(Rd). Let Pv0 be an orthog-onal projector from Vˉ1 to Vˉ0, Wj be the orthogonal complement of Vj in Vj+1.We say is Riesz basis of W0.Denote Zdm := Zd/mZd =Zmd, de?ne mapping: It is easy to know thatα(j,μ) is inversible. Letβ(k) = (β1(k),β2(k)) be theinverse mapping ofα, which means: is a basis of V1.In order to obtain the prewavelets with ?nite decomposition and ?nite recon-struction, we need to show there exists satisfyinga linear basis of V1.By theorem 2.3. 2. equals to ?nd a Laurent polynomia G(z) such thatis a monomial. For the convenience of the construction of pre-wavelets, we give the theorem of the existence of prewavelets as follows.定理2.6 Notation as before-mentioned, the neccessary and su?cient conditionof the existence of prewavelets with ?nite decomposition and ?nite reconstructionis that:2. there exists a Laurent polynomial matrix F(z) such that detis amonomial. Letand A(z) is reversible on the unit disk. Denote . Then,enote定理2.7Then PV0f∈V0 if and only if推论2.8 is a Laurent polynomial matrix.DenoteAnd let then we have:定理2.9 Notation as before mentioned ,the following conditions are equivalent1.2. is a Laurent polynomial matrix.3. is compact support.4. A(z) is a Laurent polynomial matrix and detA(z) is monomial.5. On the unit disk, C(z) is a Laurent polynomial matrix and detC(z) is mono-mial. 推论2.10 When r = 1, if the prewavelets with finite decomposition and finitereconstruction can be constructed fromφ(x), then the shifts ofφ(x) must beorthogonal.定理2.11 Let is a Laurentpolynomial matrix, then ?(x) is a compactly supported function.定理2.12 Let is a Laurentpolynomial matrix, thenBy direct computation we knowψ1(x) andψ2(x) are the prewavelet with ?nitedecomposition and ?nite reconstruction.3 Dimension Reduction Subdivision SchemeBase on Proper ParameterizationLetεj∈Rn stands for the vector with jth component 1 and all othercomponents 0. En represent the collection of all vertexes of [0,1]n, the n-cube inthe n-dimensional space. 定义3.1 We say that a convex polyhedron Y with 2n face in the n-dimensionspace is cube-like if Y satis?es that1. Y is a line, if n = 1;2. Y is a non-degenerated convex quadrilateral, if n = 2;3. every (n ? 1)-dimensional boundary of Y is a cube-like polyhedron on n ? 1hyperplane, if n≥3.Let all vertex of a simplex V in Rn be V0, V1,···, Vn, and (ω0,ω1,···,ωn)Tbe barycentric coordinates of V , where S is a rational surface de?ned on V : p(ω0,ω1,···,ωn) : V→S.Let all vertex of a simplex V in Rn be V0,V1,···,Vn . (ω0,ω1,···,ωn)T ebarycentric coordinates of V , where∑ni=0ωi = 1 and Vk = (ω0 = 0,···,ωk?1 =0,ωk = 1,ωk+1 = 0,···,ωn = 0)T, 0≤k≤n.For 0≤k≤n, select Vk as the origin point, get rid ofωk, 0≤k≤n, we canobtain the new barycentric coordinates (ξ1,···,ξn)T, whereξj =ωj?1 for j < kandξj =ωj for j≥k.Let Define the collection of vertexes whenever the superscript k is self-evident.) as follows: w{here m =∑jn=1 ij. It is easy to know that Y0 k,0,···,0 = V?0 = Vk = 0. And forYi k1,i2,···,in}, we have:命题3.2 For all j, 1≤j≤n, letThen I0j and I1j lie on two di?erent n ? 1 dimensional hyperplane.推论3.3 dimensional hyperplane.命题3.4 Let all vertex of a simplex V in Rn be V0, V1,···, Vn. Selecting V0,···, Vn as the origin respectively, we can get n + 1 cube-like polyhedron Y (V0), Y (Vk) and {Y (Vk)}kn=0 are non-overlapping.Let {Y ik1,i2,···,in} be the vertex set of Y (Vk). We de?ne F is a map from n-cube to Y (Vk). Moreover, p·F : [0,1]n→Sk is are-parametric representation? of the subpatch Sk.引理3.5 Assume that Y is a cube-like polyhedron in Rn whose vertex set is{Yi1,i2,···,in}, n≤3. Let F be a map de?ned by the equation (3.3). Then theJacobian matrix of F is nonsingular. 定理3.6 Assume that Y is a cube-like polyhedron in Rn whose vertex set is{Yi1,i2,···,in}, n≤3. Let F be a map de?ned by the equation (3.3). Then F is aone to one correspondence.