Doctoral Degrees (Mathematical Sciences)

Permanent URI for this collection

https://scholar.sun.ac.za/handle/10019.1/852

Browse

Browsing Doctoral Degrees (Mathematical Sciences) by Subject "Algorithms"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Rank matrix cascade algorithm, hermite interpolation
    (Stellenbosch : University of Stellenbosch, 2007-12) Dongmo, Guy Blaise; De Villiers, Johan; Sauer, Tomas; University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences.
    ENGLISH ABSTRACT: (Math symbols have changed) Wavelet and subdivision techniques have developed, over the last two decades, into powerful mathematical tools, for example in signal analysis and geometric modelling. Both wavelet and subdivision analysis are based on the concept of a matrix–refinable function, i.e. a finitely supported matrix function which is self-replicating in the sense that it can be expressed as a linear combination of the integer shifts of its own dilation with factor 2: F = TAF = å k∈Z F(2 ・ −k)Ak. The coefficients Ak, k ∈ Z of d × d matrices, of this linear combination constitute the so-called matrix- mask sequence. Wavelets are in fact constructed as a specific linear combination of the integer shifts of the 2-dilation of a matrix- refinable function cf. [2; 9], whereas the convergence of the associated matrix- subdivision scheme c0 = c, cr+1 = SAcr, r ∈ Z+, SA : c = (ck : k ∈ Z) 7→ SAc = å ℓ∈Z Ak−2ℓ cℓ : k ∈ Z ! , subject to the necessary condition that rank := dim   \ ǫ∈{0,1} n y ∈ Rd : Qǫy = y o   > 0, Qǫ := å j∈Z Aǫ+2j, ǫ ∈ {0, 1}, ( cf. [26]) , implies the existence of a finitely supported matrix- function which is refinable with respect to the mask coefficients defining the refinement equation and the subdivision scheme. Throughout this thesis, we investigate in time–domain for a given matrix mask sequence, the related issues of the existence of a matrix–refinable function and the convergence of the corresponding matrix– cascade algorithm, and finally we apply some results to the particular research area of Hermite interpolatory subdivision schemes. The dissertation is organized as follows: In order to provide a certain flexibility or freedom over the project, we established in Chapter 1 the equivalence relation between the matrix cascade algorithm and the matrix subdivision scheme, subject to a well defined class of initial iterates. Despite the general noncommutativity of matrices, we make use in the full rank case Qǫ = I, ǫ ∈ {0, 1}, of a symbol factorization, to develop in Chapter 2 some useful tools, yielding a convergence result which comes as close to the scalar case as possible: we obtained a concrete sufficient condition on the mask sequence based on the matrix version of the generating function introduced in [3, page 22] for existence and convergence. Whilst the conjecture on nonnegative masks was confirmed in 2005 by Zhou [29], our result on scalar case provided a progress for general mask sequences. We then applied to obtain a new one-parameter family of refinable functions which includes the cardinal splines as a special case, as well as corresponding convergent subdivision schemes. With the view to broaden the class of convergent matrix-masks, we replaced in chapter 3 the full rank condition by the rank one condition Qǫu = u, ǫ ∈ {0, 1}, u := (1, . . . , 1)T, then improved the paper by Dubuc and Merrien [13] by using the theory of rank subdivision schemes by Micchelli and Sauer [25; 26], and end up this improvement with a generalization of [13, Theorem 13, p.8] in to the context of rank subdivision schemes. In Chapter 4, we translated the concrete convergence criteria of the general theory from Theorem 3.2, based on the r-norming factor introduced in [13, Definition 6, p.6], into the context of rank, factorization and spectral radius (cf. [26]), and presented a careful analysis of the relationship between the two concepts. We then proceed with generalizations and improvements: we classified the matrix cascade algorithms in term of rank = 1, 2, . . . , d, and provided a complete characterization of each class with the use of a more general r−norming factor namely τ(r)-norming factor. On the other hand, we presented numerical methods to determine, if possible, the convergence of each class of matrix cascade algorithms. In both the scalar and matrix cases above, we also obtained explicitly the geometric constant appearing in the estimate for the geometric convergence of thematrix-cascade algorithm iterates to the matrix- refinable function. This same geometric convergence rate therefore also holds true for the corresponding matrix–cascade algorithm. Finally, in Chapter 5, we apply the theory and algorithms developed in Chapter 4 to the particular research area of Hermite interpolatory subdivision schemes: we provided a new convergence criterium, and end up with new convergence ranges of the parameters’ values of the famous Hermite interpolatory subdivision scheme with two parameters, due to Merrien [23].