Analysis of stationary subdivision schemes for curve design based on radial basis function interpolation

This paper provides a large family of interpolatory stationary subdivision schemes based on radial basis functions (RBFs) which are positive definite or conditionally positive definite. A radial basis function considered in this study has a tension parameter λ>0 such that it provides design flexibility. We prove that for a sufficiently large , the proposed 2L-point (L∈N) scheme has the same smoothness as the well-known 2L-point Deslauriers-Dubuc scheme, which is based on 2L-1 degree polynomial interpolation. Some numerical examples are presented to illustrate the performance of the new schemes, adapting subdivision rules on bounded intervals in a way of keeping the same smoothness and accuracy of the pre-existing schemes on R. We observe that, with proper tension parameters, the new scheme can alleviate undesirable artifacts near boundaries, which usually appear to interpolatory schemes with irregularly distributed control points.     

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.     

Shape Preserving Interpolatory Subdivision Schemes for Nonuniform Data

This article is concerned with a class of shape preserving four-point subdivision schemes which are stationary and which interpolate nonuniform univariate data {(x_i, f_i)}. These data are functional data, i.e., x_i≠x_j if i≠j. Subdivision for the strictly monotone x-values is performed by a subdivision scheme that makes the grid locally uniform. This article is concerned with constructing suitable subdivision methods for the f-data which preserve convexity; i.e., the data at the kth level, {x^(k)_i, f_i(k)} is a convex data set for all k provided the initial data are convex. First, a sufficient condition for preservation of convexity is presented. Additional conditions on the subdivision methods for convergence to a C¹ limit function are given. This leads to explicit rational convexity preserving subdivision schemes which generate continuously differentiable limit functions from initial convex data. The class of schemes is further restricted to schemes that reproduce quadratic polynomials. It is proved that these schemes are third order accurate. In addition, nonuniform linear schemes are examined which extend the well-known linear four-point scheme to the case of nonuniform data. Smoothness of the limit function generated by these linear schemes is proved by using the well-known smoothness criteria of the uniform linear four-point scheme.     

Approximation order of interpolatory nonlinear subdivision schemes

Linear interpolatory subdivision schemes of C^r smoothness have approximation order at least r+1. The present paper extends this result to nonlinear univariate schemes which are in proximity with linear schemes in a certain specific sense. The results apply to nonlinear subdivision schemes in Lie groups and in surfaces which are obtained from linear subdivision schemes. We indicate how to extend the results to the multivariate case.     

A unified framework for interpolating and approximating univariate subdivision

In this paper we show that the refinement rules of interpolating and approximating univariate subdivision schemes with odd-width masks of finite support can be derived ones from the others by simple operations on the mask coefficients. These operations are formalized as multiplication/division of the associated generating functions by a proper link polynomial.We then apply the proposed result to some families of stationary and non-stationary subdivision schemes, showing that it also provides a constructive method for the definition of novel refinement algorithms.     

Analysis of subdivision schemes for nets of functions by proximity and controllability

In this paper we develop tools for the analysis of net subdivision schemes, schemes which recursively refine nets of bivariate continuous functions defined on grids of lines, and generate denser and denser nets. Sufficient conditions for the convergence of such a sequence of refined nets, and for the smoothness of the limit function, are derived in terms of proximity to a bivariate linear subdivision scheme refining points, under conditions controlling some aspects of the univariate functions of the generated nets. Approximation orders of net subdivision schemes, which are in proximity with positive schemes refining points are also derived. The paper concludes with the construction of a family of blending spline-type net subdivision schemes, and with their analysis by the tools presented in the paper. This family is a new example of net subdivision schemes generating C¹ limits with approximation order 2.     

Modified form of binary and ternary 3-point subdivision schemes

Binary 3-point scheme, developed by Hormann and Sabin [Hormann, K. and Sabin, Malcolm A., 2008, A family of subdivision schemes with cubic precision, Computer Aided Geometric Design, 25, 41-52], has been modified by introducing a tension parameter which generates a family of C¹ limiting curves for certain range of tension parameter. Ternary 3-point scheme, introduced by Siddiqi and Rehan [Siddiqi, Shahid S. and Rehan, K., 2009, A ternary three point scheme for curve designing, International Journal of Computer Mathematics, In Press, DOI: 10.1080/00207160802428220], has also been modified by introducing a tension parameter which generates family of C¹ and C² limiting curves for certain range of tension parameter. Laurent polynomial method is used to investigate the continuity of the subdivision schemes. The performance of modified schemes has been demonstrated by considering different examples along with its comparison with the established subdivision schemes.     

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.     

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.     

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.     

Subdivision Schemes of Sets and the Approximation of Set-Valued Functions in the Symmetric Difference Metric

In this work we construct subdivision schemes refining general subsets of ? ⁿ and study their applications to the approximation of set-valued functions. Differently from previous works on set-valued approximation, our methods are developed and analyzed in the metric space of Lebesgue measurable sets endowed with the symmetric difference metric. The construction of the set-valued subdivision schemes is based on a new weighted average of two sets, which is defined for positive weights (corresponding to interpolation) and also when one weight is negative (corresponding to extrapolation). Using the new average with positive weights, we adapt to sets spline subdivision schemes computed by the Lane–Riesenfeld algorithm, which requires only averages of pairs of numbers. The averages of numbers are then replaced by the new averages of pairs of sets. Among other features of the resulting set-valued subdivision schemes, we prove their monotonicity preservation property. Using the new weighted average of sets with both positive and negative weights, we adapt to sets the 4-point interpolatory subdivision scheme. Finally, we discuss the extension of the results obtained in metric spaces of sets, to general metric spaces endowed with an averaging operation satisfying certain properties.     

A family of non-oscillatory 6-point interpolatory subdivision schemes

In this paper we propose and analyze a new family of nonlinear subdivision schemes which can be considered non-oscillatory versions of the 6-point Deslauries-Dubuc (DD) interpolatory scheme, just as the Power _p schemes are considered nonlinear non-oscillatory versions of the 4-point DD interpolatory scheme. Their design principle may be related to that of the Power _p schemes and it is based on a weighted analog of the Power _p mean. We prove that the new schemes reproduce exactly polynomials of degree three and stay ’close’ to the 6-point DD scheme in smooth regions. In addition, we prove that the first and second difference schemes are well defined for each member of the family, which allows us to give a simple proof of the uniform convergence of these schemes and also to study their stability as in [19, 22]. However our theoretical study of stability is not conclusive and we perform a series of numerical experiments that seem to point out that only a few members of the new family of schemes are stable. On the other hand, extensive numerical testing reveals that, for smooth data, the approximation order and the regularity of the limit function may be similar to that of the 6-point DD scheme and larger than what is obtained with the Power _p schemes.     

Exponential polynomial reproducing property of non-stationary symmetric subdivision schemes and normalized exponential B-splines

An important capability for a subdivision scheme is the reproducing property of circular shapes or parts of conics that are important analytical shapes in geometrical modeling. In this regards, this study first provides necessary and sufficient conditions for a non-stationary subdivision to have the reproducing property of exponential polynomials. Then, the approximation order of such non-stationary schemes is discussed to quantify their approximation power. Based on these results, we see that the exponential B-spline generates exponential polynomials in the associated spaces, but it may not reproduce any exponential polynomials. Thus, we present normalized exponential B-splines that reproduce certain sets of exponential polynomials. One interesting feature is that the set of exponential polynomials to be reproduced is varied depending on the normalization factor. This provides us with the necessary accuracy and flexibility in designing target curves and surfaces. Some numerical results are presented to support the advantages of the normalized scheme by comparing them to the results without normalization.     

A Unified Ternary Curve Subdivision Scheme

A unified $m\,(m>2)$-point ternary scheme with some parameter is proposed. The continuity of subdivision scheme is analyzed based on the relationship between the subdivision scheme and difference scheme. Moreover, the proposed subdivision is extended to asymmetric multi-parameter subdivision and the asymmetric schemes in four cases are presented in detail. Some examples are given to show that the presented scheme has better approximating effect.     

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.     

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.     

A family of explicit parallel Runge-Kutta-Nyström methods

A procedure for the construction of high-order explicit parallel Runge-Kutta-Nyström (RKN) methods for solving second-order nonstiff initial value problems (IVPs) is analyzed. The analysis reveals that starting the procedure with a reference symmetric RKN method it is possible to construct high-order RKN schemes which can be implemented in parallel on a small number of processors. These schemes are defined by means of a convex combination of k disjoint s_i-stage explicit RKN methods which are constructed by connecting s_i steps of a reference explicit symmetric method. Based on the reference second-order Störmer-Verlet methods we derive a family of high-order explicit parallel schemes which can be implemented in variable-step codes without additional cost. The numerical experiments carried out show that the new parallel schemes are more efficient than some sequential and parallel codes proposed in the scientific literature for solving second-order nonstiff IVPs.     

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.

     

Exact evaluation of limits and tangents for interpolatory subdivision surfaces at rational points

This paper presents a new method for exact evaluation of a limit surface generated by stationary interpolatory subdivision schemes and its associated tangent vectors at arbitrary rational points. The algorithm is designed on the basis of the parametric m-ary expansion and construction of the associated matrix sequence. The evaluation stencil of the control points on the initial mesh is obtained, through computation, by multiplying the finite matrices in a sequence corresponding to the expansion sequence and eigendecomposition of the contractive matrix related to the period of rational numbers. The method proposed in this paper works for other non-polynomial subdivision schemes as well.