A generalized Taylor factorization for Hermite subdivision schemes

In a recent paper, we investigated factorization properties of Hermite subdivision schemes by means of the so-called Taylor factorization. This decomposition is based on a spectral condition which is satisfied for example by all interpolatory Hermite schemes. Nevertheless, there exist examples of Hermite schemes, especially some based on cardinal splines, which fail the spectral condition. For these schemes (and others) we provide the concept of a generalized Taylor factorization and show how it can be used to obtain convergence criteria for the Hermite scheme by means of factorization and contractivity.     

From Hermite to stationary subdivision schemes in one and several variables

Vector and Hermite subdivision schemes both act on vector data, but since the latter one interprets the vectors as function values and consecutive derivatives they differ by the “renormalization” of the Hermite scheme in any step. In this paper we give an algebraic factorization method in one and several variables to relate any Hermite subdivision scheme that satisfies the so–called spectral condition to a vector subdivision scheme. These factorizations are natural extensions of the “zero at π” condition known for the masks of refinable functions. Moreover, we show how this factorization can be used to investigate different forms of convergence of the Hermite scheme and why the multivariate situation is conceptionally more intricate than the univariate one. Finally, we give some examples of such factorizations.     

Regularity of multiwavelets

The motivation for this paper is an interesting observation made by Plonka concerning the factorization of the matrix symbol associated with the refinement equation for B-splines with equally spaced multiple knots at integers and subsequent developments which relate this factorization to regularity of refinable vector fields over the real line. Our intention is to contribute to this train of ideas which is partially driven by the importance of refinable vector fields in the construction of multiwavelets. The use of subdivision methods will allow us to consider the problem almost entirely in the spatial domain and leads to exact characterizations of differentiability and Hölder regularity in arbitrary L _p spaces. We first study the close relationship between vector subdivision schemes and a generalized notion of scalar subdivision schemes based on bi-infinite matrices with certain periodicity properties. For the latter type of subdivision scheme we will derive criteria for convergence and Hölder regularity of the limit function, which mainly depend on the spectral radius of a bi-infinite matrix induced by the subdivision operator, and we will show that differentiability of the limit functions can be characterized by factorization properties of the subdivision operator. By switching back to vector subdivision we will transfer these results to refinable vectors fields and obtain characterizations of regularity by factorization and spectral radius properties of the symbol associated to the refinable vector field. Finally, we point out how multiwavelets can be generated from orthonormal refinable bi-infinite vector fields.     

The Higgs factorization of a geometric strong map

The Higgs factorization of a strong map between matroids on a fixed set is that factorization into elementary maps in which each matroid is the Higgs lift of its successor. This factorization is characterized by properties of the modular filters which induce the elementary maps of the factorizations in two different ways. It is also shown to be minimal in a natural order on factorizations arising from the weak-map partial order on matroids.The notion of essential nullity of flats of a matroid is introduced; this quantity is nonzero precisely for the cyclic flats, and is shown to be related to the minimal flats of the modular filters inducing the maps of the Higgs factorization.     

Hermite Subdivision Schemes and Taylor Polynomials

We propose a general study of the convergence of a Hermite subdivision scheme ℋ of degree d>0 in dimension 1. This is done by linking Hermite subdivision schemes and Taylor polynomials and by associating a so-called Taylor subdivision (vector) scheme . The main point of investigation is a spectral condition. If the subdivision scheme of the finite differences of is contractive, then is C ⁰ and ℋ is C ^d . We apply this result to two families of Hermite subdivision schemes. The first one is interpolatory; the second one is a kind of corner cutting. Both of them use the Tchakalov-Obreshkov interpolation polynomial.      

Noninterpolatory Hermite subdivision schemes

Bivariate interpolatory Hermite subdivision schemes have recently been applied to build free-form subdivision surfaces. It is well known to geometric modelling practitioners that interpolatory schemes typically lead to ``unfair" surfaces--surfaces with unwanted wiggles or undulations--and noninterpolatory (a.k.a. approximating in the CAGD community) schemes are much preferred in geometric modelling applications. In this article, we introduce, analyze and construct noninterpolatory Hermite subdivision schemes, a class of vector subdivision schemes which can be applied to iteratively refine Hermite data in a not necessarily interpolatory fashion. We also study symmetry properties of such subdivision schemes which are crucial for application in free-form subdivision surfaces.

A key step in our mathematical analysis of Hermite type subdivision schemes is that we make use of the strong convergence theory of refinement equations to convert a prescribed geometric condition on the subdivision scheme--namely, the subdivision scheme is of Hermite type--to an algebraic condition on the subdivision mask. The latter algebraic condition can then be used in a computational framework to construct specific schemes.

     

Convergent Vector and Hermite Subdivision Schemes

Hermite subdivision schemes have been studied by Merrien, Dyn, and Levin and they appear to be very different from subdivision schemes analyzed before since the rules depend on the subdivision level. As suggested by Dyn and Levin, it is possible to transform the initial scheme into a uniform stationary vector subdivision scheme which can be handled more easily.With this transformation, the study of convergence of Hermite subdivision schemes is reduced to that of vector stationary subdivision schemes. We propose a first criterion for C⁰-convergence for a large class of vector subdivision schemes. This gives a criterion for C¹-convergence of Hermite subdivision schemes. It can be noticed that these schemes do not have to be interpolatory. We conclude by investigating spectral properties of Hermite schemes and other necessary/sufficient conditions of convergence.     

Hermite subdivision on manifolds via parallel transport

We propose a new adaption of linear Hermite subdivision schemes to the manifold setting. Our construction is intrinsic, as it is based solely on geodesics and on the parallel transport operator of the manifold. The resulting nonlinear Hermite subdivision schemes are analyzed with respect to convergence and C ¹ smoothness. Similar to previous work on manifold-valued subdivision, this analysis is carried out by proving that a so-called proximity condition is fulfilled. This condition allows to conclude convergence and smoothness properties of the manifold-valued scheme from its linear counterpart, provided that the input data are dense enough. Therefore the main part of this paper is concerned with showing that our nonlinear Hermite scheme is “close enough”, i.e., in proximity, to the linear scheme it is derived from.     

Factorization of Hermite subdivision operators preserving exponentials and polynomials

In this paper we focus on Hermite subdivision operators that act on vector valued data interpreting their components as function values and associated consecutive derivatives. We are mainly interested in studying the exponential and polynomial preservation capability of such kind of operators, which can be expressed in terms of a generalization of the spectral condition property in the spaces generated by polynomials and exponential functions. The main tool for our investigation are convolution operators that annihilate the aforementioned spaces, which apparently is a general concept in the study of various types of subdivision operators. Based on these annihilators, we characterize the spectral condition in terms of factorization of the subdivision operator.     

Building a completely positive factorization

A symmetric matrix of order n is called completely positive if it has a symmetric factorization by means of a rectangular matrix with n columns and no negative entries (a so-called cp factorization), i.e., if it can be interpreted as a Gram matrix of n directions in the positive orthant of another Euclidean space of possibly different dimension. Finding this factor therefore amounts to angle packing and finding an appropriate embedding dimension. Neither the embedding dimension nor the directions may be unique, and so many cp factorizations of the same given matrix may coexist. Using a bordering approach, and building upon an already known cp factorization of a principal block, we establish sufficient conditions under which we can extend this cp factorization to the full matrix. Simulations show that the approach is promising also in higher dimensions.

     

Plancherel-type estimates and sharp spectral multipliers

We study general spectral multiplier theorems for self-adjoint positive definite operators on L²(X,μ), where X is any open subset of a space of homogeneous type. We show that the sharp Hörmander-type spectral multiplier theorems follow from the appropriate estimates of the L² norm of the kernel of spectral multipliers and the Gaussian bounds for the corresponding heat kernel. The sharp Hörmander-type spectral multiplier theorems are motivated and connected with sharp estimates for the critical exponent for the Riesz means summability, which we also study here. We discuss several examples, which include sharp spectral multiplier theorems for a class of scattering operators on R³ and new spectral multiplier theorems for the Laguerre and Hermite expansions.     

On the sensitivity of the LU factorization

This paper gives sensitivity analyses by two approaches forL andU in the factorizationA=LU for general perturbations inA which are sufficiently small in norm. By the matrix-vector equation approach, we derive the condition numbers for theL andU factors. By the matrix equation approach we derive corresponding condition estimates. We show how partial pivoting and complete pivoting affect the sensitivity of the LU factorization. The material presented here is a part of the first author's PhD thesis under the supervision of the second author. This research was supported by NSERC of Canada Grant OGP0009236.     

On the regularity analysis of interpolatory Hermite subdivision schemes

It is well known that the critical Hölder regularity of a subdivision schemes can typically be expressed in terms of the joint-spectral radius (JSR) of two operators restricted to a common finite-dimensional invariant subspace. In this article, we investigate interpolatory Hermite subdivision schemes in dimension one and specifically those with optimal accuracy orders. The latter include as special cases the well-known Lagrange interpolatory subdivision schemes by Deslauriers and Dubuc. We first show how to express the critical Hölder regularity of such a scheme in terms of the joint-spectral radius of a matrix pair {F₀,F₁} given in a very explicit form. While the so-called finiteness conjecture for JSR is known to be not true in general, we conjecture that for such matrix pairs arising from Hermite interpolatory schemes of optimal accuracy orders a “strong finiteness conjecture” holds: ρ(F₀,F₁)=ρ(F₀)=ρ(F₁). We prove that this conjecture is a consequence of another conjectured property of Hermite interpolatory schemes which, in turn, is connected to a kind of positivity property of matrix polynomials. We also prove these conjectures in certain new cases using both time and frequency domain arguments; our study here strongly suggests the existence of a notion of “positive definiteness” for non-Hermitian matrices.     

How to obtain higher-order multivariate Hermite expansion of Maxwell–Boltzmann distribution by using Taylor expansion?

We obtain the higher-order multivariate Hermite expansion of the Maxwell–Boltzmann distribution by using a new, compact tensorial notation and present a method to obtain the nth order multivariate Taylor expansion, which is identical to the nth order multivariate Hermite expansion of the Maxwell–Boltzmann distribution. This study enables us to find higher-order models of discrete kinetic theories such as the lattice Boltzmann theory.     

On the stability of polynomial transformations between Taylor,Bernstein and Hermite forms

The stability of transformations between Taylor and Hermite and Bernstein and Hermite forms of the polynomials are investigated. The results are analogous to Farouki's concerning the stability of the transformation between Taylor and Bernstein form. An exact asymptotic is given for the condition numbers in thel ¹ case.Research was partially supported by the Copernicus grant RECCAD 94-1068 and by the National Research Foundation of the Hungarian Academy of Sciences grant 16420.     

Tight frames of compactly supported multivariate multi-wavelets

This paper is devoted to the study and construction of compactly supported tight frames of multivariate multi-wavelets. In particular, a necessary condition for their existence is derived to provide some useful guide for constructing such MRA tight frames, by reducing the factorization task of the associated polyphase matrix-valued Laurent polynomial to that of certain scalar-valued non-negative ones. We illustrate our construction method with examples of both multivariate scalar- and vector-valued subdivision schemes. Since our constructions for C¹ and C² piecewise cubic schemes are quite involved, we also include the corresponding Matlab code in the Appendix.     

Weinbaum factorizations of primitive words

C. M. Weinbaum [1] showed the following: Let w be a primitive word and a be letter in w. Then a conjugate of w can be written as uv such that a is a prefix and a suffix of u, but v neither starts nor ends with a, and u and v have a unique position in w as cyclic factors. The latter condition means that there is exactly one conjugate of w having u as a prefix and there is exactly one conjugate of w having v as a prefix. It is this condition which makes the result non-trivial. We give a simplified proof for Weinbaum’s result. Guided by this proof we exhibit quite different, but still simple, proofs for more general statements. For this purpose we introduce the notion of Weinbaum factor and Weinbaum factorization.     

On symbolic factorization of partitioned sparse symmetric matrices

Partitioning a sparse matrix A is a useful device employed by a number of sparse matrix techniques. An important problem that arises in connection with some of these methods is to determine the block structure of the Cholesky factor L of A, given the partitioned A. For the scalar case, the problem of determining the structure of L from A, so-called symbolic factorization, has been extensively studied. In this paper we study the generalization of this problem to the block case. The problem is interesting because an assumption relied on in the scalar case no longer holds; specifically, the product of two nonzero scalars is always nonzero, but the product of two nonnull sparse matrices may yield a zero matrix. Thus, applying the usual symbolic factorization techniques to a partitioned matrix, regarding each submatrix as a scalar, may yield a block structure of L which is too full. In this paper an efficient algorithm is provided for determining the block structure of the Cholesky factor of a partitioned matrix A, along with some bounds on the execution time of the algorithm.     

One-step 9-stage Hermite–Birkhoff–Taylor ODE solver of order 10

A one-step 9-stage Hermite–Birkhoff–Taylor method of order 10, denoted by HBT(10)9, is constructed for solving nonstiff systems of first-order differential equations of the form y′=f(x,y), y(x ₀)=y ₀. The method uses y′ and higher derivatives y ⁽²⁾ to y ⁽⁴⁾ as in Taylor methods and is combined with a 9-stage Runge–Kutta method. Forcing a Taylor expansion of the numerical solution to agree with an expansion of the true solution leads to Taylor- and Runge–Kutta-type order conditions which are reorganized into Vandermonde-type linear systems whose solutions are the coefficients of the method. The new method has a larger scaled interval of absolute stability than Dormand–Prince DP(8,7)13M. The stepsize is controlled by means of y ⁽²⁾ and y ⁽⁴⁾. HBT(10)9 is superior to DP(8,7)13M and Taylor method of order 10 in solving several problems often used to test high-order ODE solvers on the basis of the number of steps, CPU time, and maximum global error. These numerical results show the benefits of adding high-order derivatives to Runge–Kutta methods.     

On the sensitivity of generators for the QR factorization of quasiseparable matrices with total nonpositivity

In this paper, we provide a relatively robust representation for the QR factorization of quasiseparable matrices with total nonpositivity. This representation allows us to develop a structure-preserving perturbation analysis. Consequently, stronger perturbation bounds are obtained to show that its generators determine the factors Q and R to high relative accuracy, independent of any conventional condition number. This means that it is possible to accurately compute the QR factorization by operating on these generators.