Subdivision Schemes for Positive Definite Matrices

The class of symmetric positive definite matrices is an important class both in theory and application. Although this class is well studied, little is known about how to efficiently interpolate such data within the class. We extend the 4-point interpolatory subdivision scheme, as a method of interpolation, to data consisting of symmetric positive definite matrices. This extension is based on an explicit formula for calculating a binary “geodetic average”. Our method generates a smooth curve of matrices, which retain many important properties of the interpolated matrices. Furthermore, the scheme is robust and easy to implement.     

Sign Regular Matrices of Order Two

A matrix is called sign regular of order k if every minor of order i has the same sign for each i = 1,2,<, k . If an m × n matrix is sign regular of order k for k = min { m,n } then it is called sign regular. This paper studies some properties of sign regular matrices of order two. Remarkable properties are proved when the row sums of these matrices form a monotone vector.     

双参数六点细分法

提出了一类包含两个形状参数的双参数六点细分法,可以构造光滑插值曲线和光滑逼近曲线,并且可以通过对两个参数取值的调整使得曲线达到一致收敛,C1或C2.讨论了形状参数对细分法的收敛性及连续性的影响,给出了细分法一致收敛、C1连续、C2连续的充分条件,并给出了一些数值算例.     

SIA Matrices and Non-Negative Subdivision

We reprove and extend results for uniform convergence of non-negative subdivision using results from infinite products of stochastic matrices as they appear in the study of non-homogeneous finite Markov processes. Geometric convergence of such products to rank one matrices, based on the notions of SIA matrices and of the so-called ergodic coefficient, is discussed. We also point to the properties of the directed graphs of such matrices. In this way the existing convergence results for non-negative subdivision are put into the context of such processes.     

Distribution of Eigenvalues of Real Symmetric Palindromic Toeplitz Matrices and Circulant Matrices

Consider the ensemble of real symmetric Toeplitz matrices, each independent entry an i.i.d. random variable chosen from a fixed probability distribution p of mean 0, variance 1, and finite higher moments. Previous investigations showed that the limiting spectral measure (the density of normalized eigenvalues) converges weakly and almost surely, independent of p, to a distribution which is almost the standard Gaussian. The deviations from Gaussian behavior can be interpreted as arising from obstructions to solutions of Diophantine equations. We show that these obstructions vanish if instead one considers real symmetric palindromic Toeplitz matrices, matrices where the first row is a palindrome. A similar result was previously proved for a related circulant ensemble through an analysis of the explicit formulas for eigenvalues. By Cauchy’s interlacing property and the rank inequality, this ensemble has the same limiting spectral distribution as the palindromic Toeplitz matrices; a consequence of combining the two approaches is a version of the almost sure Central Limit Theorem. Thus our analysis of these Diophantine equations provides an alternate technique for proving limiting spectral measures for certain ensembles of circulant matrices. A. Massey’s current address: Department of Mathematics, UCLA, Los Angeles, CA 90095, USA. e-mail: amassey3102@math.ucla.edu.     

Subdivision Schemes and Irregular Grids

The present paper deals with subdivision schemes associated with irregular grids. We first give a sufficient condition concerning the difference scheme to obtain convergence. This condition generalizes a necessary and sufficient condition for convergence known in the case of uniform and stationary schemes associated with a regular grid. Through this sufficient condition, convergence of a given subdivision scheme can be proved by comparison with another scheme. Indeed, when two schemes are equivalent in some sense, and when one satisfies the sufficient condition for convergence, the other also satisfies it and it therefore converges too. We also study the smoothness of the limit functions produced by a scheme which satisfies the sufficient condition. Finally, the results are applied to the study of Lagrange interpolating subdivision schemes of any degree, with respect to particular irregular grids.     

Exponentials Reproducing Subdivision Schemes

This paper is concerned with a family of nonstationary, interpolatory subdivision schemes that have the capability of reproducing functions in a finite-dimensional subspace of exponential polynomials. We give conditions for the existence and uniqueness of such schemes, and analyze their convergence and smoothness. It is shown that the refinement rules of an even-order exponentials reproducing scheme converge to the Dubuc—Deslauriers interpolatory scheme of the same order, and that both schemes have the same smoothness. Unlike the stationary case, the application of a nonstationary scheme requires the computation of a different rule for each refinement level. We show that the rules of an exponentials reproducing scheme can be efficiently derived by means of an auxiliary orthogonal scheme , using only linear operations. The orthogonal schemes are also very useful tools in fitting an appropriate space of exponential polynomials to a given data sequence.     

Distribution of Eigenvalues of Highly Palindromic Toeplitz Matrices

Consider the ensemble of real symmetric Toeplitz matrices whose entries are i.i.d. random variables chosen from a fixed probability distribution p of mean 0, variance 1, and finite higher moments. Previous work (Bryc et al., Ann. Probab. 34(1):1–38, 2006; Hammond and Miller, J. Theor. Probab. 18(3):537–566, 2005) showed that the spectral measures (the density of normalized eigenvalues) converge almost surely to a universal distribution almost that of the Gaussian, independent of p. The deficit from the Gaussian distribution is due to obstructions to solutions of Diophantine equations and can be removed (see Massey et al., J. Theor. Probab. 20(3):637–662, 2007) by making the first row palindromic. In this paper we study the case where there is more than one palindrome in the first row of real symmetric Toeplitz matrices. Using the method of moments and an analysis of the resulting Diophantine equations, we show that the spectral measures converge almost surely to a universal distribution. Assuming a conjecture on the resulting Diophantine sums (which is supported by numerics and some theoretical arguments), we prove that the limiting distribution has a fatter tail than any previously seen limiting spectral measure.     

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 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.      

Convexity Preserving Interpolatory Subdivision Schemes

We construct local subdivision schemes that interpolate functional univariate data and that preserve convexity. The resulting limit function of these schemes is continuous and convex for arbitrary convex data. Moreover this class of schemes is restricted to a subdivision scheme that generates a limit function that is convex and continuously differentiable for strictly convex data. The approximation order of this scheme is four. Some generalizations, such as tension control and piecewise convexity preservation, are briefly discussed. November 29, 1996. Date revised: May 28, 1997.     

L~p空间中的多变量Subdivision算法(英文)

本文讨论了与一般伸缩矩阵Ｍ相关的Ｓｕｂｄｉｖｓｉｏｎ算法的Ｌｐ－收敛性,多个细分方程的解可由一个给定的细分函数通过迭代算法得到。     

Analysis and Convergence of Hermite Subdivision Schemes

Foundations of Computational Mathematics - Hermite interpolation property is desired in applied and computational mathematics. Hermite and vector subdivision schemes are of interest in CAGD for...     

一类保凸的细分格式

提出了一类新的具有高阶连续性和保凸性的5-点二重细分格式.可以证明在参数的某些取值范围内,极限曲线是$C^k~(k=0,1,\ldots,7)$连续的.本文还给出了极限曲线保凸时的参数的取值范围.数值例子表明该格式是灵活有效的.     

Nonlinear Subdivision Schemes on Irregular Meshes

The present article deals with convergence and smoothness analysis of geometric, nonlinear subdivision schemes in the presence of extraordinary points. We discuss when the existence of a proximity condition between a linear scheme and its nonlinear analogue implies convergence of the nonlinear scheme (for dense enough input data). Furthermore, we obtain C ¹ smoothness of the nonlinear limit function in the vicinity of an extraordinary point over Reif’s characteristic parametrization. The results apply to the geometric analogues of well-known subdivision schemes such as Doo–Sabin or Catmull–Clark schemes.     

L^p空间中的多变量Subdivision算法

本文讨论了与一般伸缩矩阵M相关的Subdivsion算法的L^p-收敛性,多个细分方程的解可由一个给定的细分函数通过迭代算法得到。     

Generalized and Unified Families of Interpolating Subdivision Schemes

We present generalized and unified families of $(2n)$-point and $(2n-1)$-point $p$-ary interpolating subdivision schemes originated from Lagrange polynomial for any integers $n ≥ 2$ and $p ≥ 3$. Almost all existing even-point and odd-point interpolating schemes of lower and higher arity belong to this family of schemes. We also present tensor product version of generalized and unified families of schemes. Moreover, error bounds between limit curves and control polygons of schemes are also calculated. It has been observed that error bounds decrease when complexity of the scheme decrease and vice versa. Furthermore, error bounds decrease with the increase of arity of the schemes. We also observe that in general the continuity of interpolating scheme do not increase by increasing complexity and arity of the scheme.     

Smoothness Analysis of Subdivision Schemes by Proximity

Linear curve subdivision schemes may be perturbed in various ways, for example, by modifying them such as to work in a manifold, surface, or group. The analysis of such perturbed and often nonlinear schemes "T" is based on their proximity to the linear schemes "S" which they are derived from. This paper considers two aspects of this problem: One is to find proximity inequalities which together with C^k smoothness of S imply C^k smoothness of T. The other is to verify these proximity inequalities for several ways to construct the nonlinear scheme T analogous to the linear scheme S. The first question is treated for general k, whereas the second one is treated only in the case k = 2. The main result of the paper is that convergent geodesic/projection/Lie group analogues of a certain class of factorizable linear schemes have C² limit curves.