Maria Charina

Maria Charina, Costanza Conti, Lucia Romani

We study scalar multivariate non-stationary subdivision schemes with a general dilation matrix. We characterize the capability of such schemes to reproduce exponential polynomials in terms of simple algebraic conditions on their symbols. These algebraic conditions provide a useful theoretical tool for checking the reproduction properties of existing schemes and for constructing new schemes with desired reproduction capabilities and other enhanced properties. We illustrate our results with several examples.

Maria Charina, Costanza Conti

A stationary subdivision scheme generates the full space of polynomials of degree up to $k$ if and only if its mask satisfies sum rules of order $k+1$, or its symbol satisfies zero conditions of order $k+1$. This property is often called the polynomial reproduction property of the subdivision scheme. It is a well-known fact that this property is, in general, only necessary for the associated refinable function to have approximation order $k+1$. In this paper we study a different polynomial reproduction property of multivariate scalar subdivision scheme with dilation matrix $mI$, $|m| \ge 2$. Namely, we are interested in capability of a subdivision scheme to reproduce in the limit exactly the same polynomials from which the data is sampled. The motivation for this paper are the results by Adi Levin that state that such a reproduction property of degree $k$ of the subdivision scheme is sufficient for having approximation order $k+1$. Our main result yields simple algebraic conditions on the subdivision symbol for computing the exact degree of such polynomial reproduction and also for determining the associated parametrization. The parametrization determines the grid points to which the newly computed values are attached at each subdivision iteration to ensure the higher degree of polynomial reproduction. We illustrate our results with several examples.

Maria Charina, Costanza Conti, Nicola Guglielmi et al.

In this paper, we present a new matrix approach for the analysis of subdivision schemes whose non-stationarity is due to linear dependency on parameters whose values vary in a compact set. Indeed, we show how to check the convergence in $C^{\ell}(\RR^s)$ and determine the Hölder regularity of such level and parameter dependent schemes efficiently via the joint spectral radius approach. The efficiency of this method and the important role of the parameter dependency are demonstrated on several examples of subdivision schemes whose properties improve the properties of the corresponding stationary schemes. Moreover, we derive necessary criteria for a function to be generated by some level dependent scheme and, thus, expose the limitations of such schemes.

Maria Charina, Costanza Conti, Nicola Guglielmi et al.

In this paper, we study scalar multivariate non-stationary subdivision schemes with integer dilation matrix M=mI, m >=2, and present a general approach for checking their convergence and for determining their Hölder regularity. The combination of the concepts of asymptotic similarity and approximate sum rules allows us to link stationary and non-stationary settings and to employ recent advances in methods for exact computation of the joint spectral radius. As an application, we prove a recent conjecture on the Hölder regularity of the generalized Daubechies wavelets. We illustrate our results with several examples.

Maria Charina, Thomas Mejstrik

This paper extends the matrix based approach to the setting of multiple subdivision schemes studied in [Sauer 2012]. Multiple subdivision schemes, in contrast to stationary and non-stationary schemes, allow for level dependent subdivision weights and for level dependent choice of the dilation matrices. The latter property of multiple subdivision makes the standard definition of the transition matrices, crucial ingredient of the matrix approach in the stationary and non-stationary settings, inapplicable. We show how to avoid this obstacle and characterize the convergence of multiple subdivision schemes in terms of the joint spectral radius of certain square matrices derived from subdivision weights. We illustrate our results with several examples.

Maria Charina, Lucia Romani

In this paper we study scalar multivariate subdivision schemes with general integer expanding dilation matrix. Our main result yields simple algebraic conditions on the symbols of such schemes that characterize their polynomial reproduction, i.e. their capability to generate exactly the same polynomials from which the initial data is sampled. These algebraic conditions also allow us to determine the approximation order of the associated refinable functions and to choose the "correct" parametrization, i.e. the grid points to which the newly computed values are attached at each subdivision iteration. We use this special choice of the parametrization to increase the degree of polynomial reproduction of known subdivision schemes and to construct new schemes with given degree of polynomial reproduction.

Maria Charina, Geir Dahl

We link regularity and smoothness analysis of multivariate vector subdivision schemes with network flow theory and with special linear optimization problems. This connection allows us to prove the existence of what we call optimal difference masks that posses crucial properties unifying the regularity analysis of univariate and multivariate subdivision schemes. We also provide efficient optimization algorithms for construction of such optimal masks. Integrality of the corresponding optimal values leads to purely analytic proofs of $C^k-$regularity of subdivision.

Maria Charina, Costanza Conti, Lucia Romani et al.

The regularity of refinable functions has been investigated deeply in the past 25 years using Fourier analysis, wavelet analysis, restricted and joint spectral radii techniques. However the shift-invariance of the underlying regular setting is crucial for these approaches. We propose an efficient method based on wavelet tight frame decomposition techniques for estimating Hölder-Zygmund regularity of univariate semi-regular refinable functions generated, e.g., by subdivision schemes defined on semi-regular meshes $\mathbf{t}\;=\;-h_\ell\mathbb{N}\cup\{0\}\cup h_r\mathbb{N}$, $h_\ell,h_r \in (0,\infty)$. To ensure the optimality of this method, we provide a new characterization of Hölder-Zygmund spaces based on suitable irregular wavelet tight frames. Furthermore, we present proper tools for computing the corresponding frame coefficients in the semi-regular setting. We also propose a new numerical approach for estimating the optimal Hölder-Zygmund exponent of refinable functions which is more efficient than the linear regression method. We illustrate our results with several examples of known and new semi-regular subdivision schemes with a potential use in blending curve design.

Maria Charina, Costanza Conti, Kurt Jetter et al.

We study scalar $d$-variate subdivision schemes, with dilation matrix 2I, satisfying the sum rules of order $k$. Using the results of Möller and Sauer, stated for general expanding dilation matrices, we characterize the structure of the mask symbols of such schemes by showing that they must be linear combinations of shifted box spline generators of some quotient polynomial ideal. The directions of the corresponding box splines are columns of certain unimodular matrices. The quotient ideal is determined by the given order of the sum rules or, equivalently, by the order of the zero conditions. The results presented in this paper open a way to a systematic study of subdivision schemes, since box spline subdivisions turn out to be the building blocks of any reasonable multivariate subdivision scheme. As in the univariate case, the characterization we give is the proper way of matching the smoothness of the box spline building blocks with the order of polynomial reproduction of the corresponding subdivision scheme. However, due to the interaction of the building blocks, convergence and smoothness properties may change, if several convergent schemes are combined.

Maria Charina

In this paper, motivated by applications in computer graphics and animation, we study the numerical methods for checking $C^k-$regularity of vector multivariate subdivision schemes with dilation 2I. These numerical methods arise from the joint spectral radius and restricted spectral radius approaches, which were shown in Charina (Charina, 2011) to characterize $W^k_p-$regularity of subdivision in terms of the same quantity. Namely, the $(k,p)-$joint spectral radius and the $(k,p)-$restricted spectral radius are equal. We show that the corresponding numerical methods in the univariate scalar and vector cases even yield the same upper estimate for the $(k,\infty)-$joint spectral radius for a certain choice of a matrix norm. The difference between the two approaches becomes apparent in the multivariate case and we confirm that they indeed offer different numerical schemes for estimating the regularity of subdivision. We illustrate our results with several examples.

Maria Charina, Marco Donatelli, Lucia Romani et al.

In this paper, we present a family of multivariate grid transfer operators appropriate for anisotropic multigrid methods. Our grid transfer operators are derived from a new family of anisotropic interpolatory subdivision schemes. We study the minimality, polynomial reproduction and convergence properties of these interpolatory schemes and link their properties to the convergence and optimality of the corresponding multigrid methods. We compare the performance of our interpolarory grid transfer operators with the ones derived from a family of corresponding approximating subdivision schemes.

Maria Charina, Marco Donatelli, Lucia Romani et al.

The convergence rate of a multigrid method depends on the properties of the smoother and the so-called grid transfer operator. In this paper we define and analyze new grid transfer operators with a generic cutting size which are applicable for high order problems. We enlarge the class of available geometric grid transfer operators by relating the symbol analysis of the coarse grid correction with the approximation properties of univariate subdivision schemes. We show that the polynomial generation property and stability of a subdivision scheme are crucial for convergence and optimality of the corresponding multigrid method. We construct a new class of grid transfer operators from primal binary and ternary pseudo-spline symbols. Our numerical results illustrate the behavior of the new grid transfer operators.