Search

Standard interpolatory subdivision schemes and their underlying interpolating refinable functions are of interest in CAGD, numerical PDEs, and approximation theory. Generalizing these notions, we introduce and study n s -step interpolatory M -subdivision schemes and their interpolating M -refinable functions with n s ∈ N ∪ { ∞ } and a dilation factor M ∈ N \ { 1 } . We completely characterize C m -convergence and smoothness of n s -step interpolatory subdivision schemes and their interpolating M -refinable functions in terms of their masks. Inspired by n s -step interpolatory stationary subdivision schemes, we further introduce the notion of r-mask quasi-stationary subdivision schemes, and then we characterize their C m -convergence and smoothness properties using only their masks. Moreover, combining n s -step interpolatory subdivision schemes with r-mask quasi-stationary subdivision schemes, we can obtain r n s -step interpolatory subdivision schemes. Examples and construction procedures of convergent n s -step interpolatory M -subdivision schemes are provided to illustrate our results with dilation factors M = 2 , 3 , 4 . In addition, for the dyadic dilation M = 2 and r = 2 , 3 , using r masks with only two-ring stencils, we provide examples of C r -convergent r-step interpolatory r-mask quasi-stationary dyadic subdivision schemes. [ABSTRACT FROM AUTHOR]

Interpolation-based methods are well-established and effective approaches for the efficient generation of accurate reduced-order surrogate models. Common challenges for such methods are the automatic selection of good or even optimal interpolation points and the appropriate size of the reduced-order model. An approach that addresses the first problem for linear, unstructured systems is the iterative rational Krylov algorithm (IRKA), which computes optimal interpolation points through iterative updates by solving linear eigenvalue problems. However, in the case of preserving internal system structures, optimal interpolation points are unknown, and heuristics based on nonlinear eigenvalue problems result in numbers of potential interpolation points that typically exceed the reasonable size of reduced-order systems. In our work, we propose a projection-based iterative interpolation method inspired by IRKA for generally structured systems to adaptively compute near-optimal interpolation points as well as an appropriate size for the reduced-order system. Additionally, the iterative updates of the interpolation points can be chosen such that the reduced-order model provides an accurate approximation in specified frequency ranges of interest. For such applications, our new approach outperforms the established methods in terms of accuracy and computational effort. We show this in numerical examples with different structures. [ABSTRACT FROM AUTHOR]

High-dimensional/high-fidelity nonlinear dynamical systems appear naturally when the goal is to accurately model real-world phenomena. Many physical properties are thereby encoded in the internal differential structure of these resulting large-scale nonlinear systems. The high dimensionality of the dynamics causes computational bottlenecks, especially when these large-scale systems need to be simulated for a variety of situations such as different forcing terms. This motivates model reduction where the goal is to replace the full-order dynamics with accurate reduced-order surrogates. Interpolation-based model reduction has been proven to be an effective tool for the construction of cheap-to-evaluate surrogate models that preserve the internal structure in the case of weak nonlinearities. In this paper, we consider the construction of multivariate interpolants in frequency domain for structured quadratic-bilinear systems. We propose definitions for structured variants of the symmetric subsystem and generalized transfer functions of quadratic-bilinear systems and provide conditions for structure-preserving interpolation by projection. The theoretical results are illustrated using two numerical examples including the simulation of molecular dynamics in crystal structures. [ABSTRACT FROM AUTHOR]

We consider new degrees of freedom for higher order differential forms on cubical meshes. The approach is inspired by the idea of Rapetti and Bossavit to define higher order Whitney forms and their degrees of freedom using small simplices. We show that higher order differential forms on cubical meshes can be defined analogously using small cubes and prove that these small cubes yield unisolvent degrees of freedom. Importantly, this approach is compatible with discrete exterior calculus and expands the framework to cover higher order methods on cubical meshes, complementing the earlier strategy based on simplices. [ABSTRACT FROM AUTHOR]

We describe a general approach for constructing a broad class of operators approximating high-dimensional curves based on geometric Hermite data. The geometric Hermite data consists of point samples and their associated tangent vectors of unit length. Extending the classical Hermite interpolation of functions, this geometric Hermite problem has become popular in recent years and has ignited a series of solutions in the 2D plane and 3D space. Here, we present a method for approximating curves, which is valid in any dimension. A basic building block of our approach is a Hermite average — a notion introduced in this paper. We provide an example of such an average and show, via an illustrative interpolating subdivision scheme, how the limits of the subdivision scheme inherit geometric properties of the average. Finally, we prove the convergence of this subdivision scheme, whose limit interpolates the geometric Hermite data and approximates the sampled curve. We conclude the paper with various numerical examples that elucidate the advantages of our approach. [ABSTRACT FROM AUTHOR]

Numerical analysts and scientists working in applications often observe that once they improve their techniques to get a better accuracy, some instability of the evaluation creeps in through the back door. This paper shows for a large class of numerical methods that such a Trade-off Principle between error and evaluation stability is unavoidable. It is an instance of a no free lunch theorem. Here, evaluation is the mathematical map that takes input data to output data. This is independent from the numerical routine that calculates the output. Therefore, evaluation stability is different from computational stability. The setting is confined to recovery of functions from data, but it includes solving differential equations by writing such methods as a recovery of functions under constraints imposed by differential operators and boundary values. The trade-off principle bounds the product of two terms from below. The first is related to errors, and the second turns out to be related to evaluation instability. Under certain conditions satisfied for splines and kernel-based interpolation, both can be minimized. Then the lower bound is attained, and the error term is the inverse of the instability term. As a byproduct, it is shown that Kansa’s Unsymmetric Collocation Method sacrifices accuracy for improved evaluation stability, when compared to symmetric collocation. [ABSTRACT FROM AUTHOR]

This paper deals with the construction of the Algebraic Trigonometric Pythagorean Hodograph (ATPH) cubic-like Hermite interpolant. A characterization of solutions according to the tangents at both ends and a global free shape parameter α is performed. Since this degree of freedom can be used for adjustments, we study how the curve evolves with respect to α. Several examples illustrating the construction process and a simple fitting method to determine the unique ATPH curve passing through a given point are proposed. [ABSTRACT FROM AUTHOR]

Panel-based, kernel-split quadrature is currently one of the most efficient methods available for accurate evaluation of singular and nearly singular layer potentials in two dimensions. However, it can fail completely for the layer potentials belonging to the modified Helmholtz, modified biharmonic, and modified Stokes equations. These equations depend on a parameter, denoted α, and kernel-split quadrature loses its accuracy rapidly when this parameter grows beyond a certain threshold. This paper describes an algorithm that remedies this problem, using per-target adaptive sampling of the source geometry. The refinement is carried out through recursive bisection, with a carefully selected rule set. This maintains accuracy for a wide range of the parameter α, at an increased cost that scales as log α . Using this algorithm allows kernel-split quadrature to be both accurate and efficient for a much wider range of problems than previously possible. [ABSTRACT FROM AUTHOR]

The algebraic characterization of dual univariate interpolating subdivision schemes is investigated. Specifically, we provide a constructive approach for finding dual univariate interpolating subdivision schemes based on the solutions of certain associated polynomial equations. The proposed approach also makes it possible to identify conditions for the existence of the sought schemes. [ABSTRACT FROM AUTHOR]

In this paper, we extendthe structure-preserving interpolatory model reduction framework, originally developed for linear systems, to structured bilinear control systems. Specifically, we give explicit construction formulae for the model reduction bases to satisfy different types of interpolation conditions. First, we establish the analysis for transfer function interpolation for single-input single-output structured bilinear systems. Then, we extend these results to the case of multi-input multi-output structured bilinear systems by matrix interpolation. The effectiveness of our structure-preserving approach is illustrated by means of various numerical examples. [ABSTRACT FROM AUTHOR]

We study worst-case optimal approximation of positive linear functionals in reproducing kernel Hilbert spaces induced by increasingly flat Gaussian kernels. This provides a new perspective and some generalisations to the problem of interpolation with increasingly flat radial basis functions. When the evaluation points are fixed and unisolvent, we show that the worst-case optimal method converges to a polynomial method. In an additional one-dimensional extension, we allow also the points to be selected optimally and show that in this case convergence is to the unique Gaussian quadrature–type method that achieves the maximal polynomial degree of exactness. The proofs are based on an explicit characterisation of the reproducing kernel Hilbert space of the Gaussian kernel in terms of exponentially damped polynomials. [ABSTRACT FROM AUTHOR]

It is known that discrete sets of uniformly distributed points on the hypersphere S d ⊂ ℝ d + 1 can be obtained from minimizing the energy functional corresponding to Riesz s-kernels k s (x , y) = ∥ x − y ∥ − s (s > 0) or the logarithmic kernel k log (x , y) = − log ∥ x − y ∥ + log 2 . We prove the same for the kernel k log (x , y) = ∥ x − y ∥ (log ∥ x − y ∥ 2 − 1) + 2 which is a front-extension of the sequence of derivatives k log , k 1 , k 2 , k 3 , ... , up to sign and constants. The boundedness of the kernel simplifies the classical potential-theoretical proof of the asymptotic uniformity of the point distributions. Still, the property of a singular derivative for x → y is preserved, with the physical interpretation of infinite repulsive forces for touching particles. The quality of the resulting point distributions is exemplary compared with that of Riesz- and classical logarithmic point sets, and found to be competitive. Originally motivated by problems of high-dimensional data, the applicability of log -optimal point sets with a novel concentric interpolation and differentiation scheme is demonstrated. The method is significantly optimized by the introduction of symmetrized kernels for both the generation of the minimum energy points and the spherical basis functions. Both the point generation and the Concentric Interpolation software are available as Open Source software and selected point sets are provided. [ABSTRACT FROM AUTHOR]

This paper studies well-definedness and convergence of subdivision schemes which operate on Riemannian manifolds with nonpositive sectional curvature. These schemes are constructed from linear ones by replacing affine averages by the Riemannian centre of mass. In contrast to previous work, we consider schemes without any sign restriction on the mask, and our results apply to all input data. We also analyse the Hölder continuity of the resulting limit curves. Our main result states that if the norm of the derived scheme (resp. iterated derived scheme) is smaller than the corresponding dilation factor then the adapted scheme converges. In this way, we establish that convergence of a linear subdivision scheme is almost equivalent to convergence of its nonlinear manifold counterpart. [ABSTRACT FROM AUTHOR]

We introduce a new class of Pythagorean-Hodograph (PH) space curves - called Algebraic-Trigonometric Pythagorean-Hodograph (ATPH) space curves - that are defined over a six-dimensional space mixing algebraic and trigonometric polynomials. After providing a general definition for this new class of curves, their quaternion representation is introduced and the fundamental properties are discussed. Then, as previously done with their quintic polynomial counterpart, a constructive approach to solve the first-order Hermite interpolation problem in ℝ3 is provided. Comparisons with the polynomial case are illustrated to point out the greater flexibility of ATPH curves with respect to polynomial PH curves. [ABSTRACT FROM AUTHOR]

A low dissipative framework is given to construct high order entropy stable flux by addition of suitable numerical diffusion operator into entropy conservative flux. The framework is robust in the sense that it allows the use of high order reconstructions which satisfy the sign property only across the discontinuities. The third order weighted essentially non-oscillatory (WENO) interpolations and high order total variation diminishing (TVD) reconstructions are shown to satisfy the sign property across discontinuities. Third order accurate entropy stable schemes are constructed by using third order WENO and high order TVD reconstructions procedures in the diffusion operator. These schemes are efficient and less diffusive since the diffusion is actuated only in the sign stability region of the used reconstruction which includes discontinuities. Numerical results with constructed schemes for various test problems are given which show the third order accuracy and less dissipative nature of the schemes. [ABSTRACT FROM AUTHOR]

The aim of the paper is to construct a multiresolution analysis of L2(IRd) based on generalized kernels which are fundamental solutions of differential operators of the form ∏ℓ=1m(−Δ+κℓ2I). We study its properties and provide a set of pre-wavelets associated with it, as well as the filters which are indispensable to perform decomposition and reconstruction of a given signal, being very useful in applied problems thanks to the presence of the tension parameters κℓ. [ABSTRACT FROM AUTHOR]

Bernstein-Bézier techniques for analyzing polynomial spline fields in n variables and their divergence are developed. Dimension and a minimal determining set for continuous piecewise divergence-free spline fields on the Alfeld split of a simplex in ℝ are obtained using the new techniques, as well as the dimension formula for continuous piecewise divergence-free splines on the Alfeld refinement of an arbitrary simplicial partition in ℝ. [ABSTRACT FROM AUTHOR]

The paper provides an approach for constructing multivariate radial kernels satisfying higher-order generalized Strang-Fix conditions from a given univariate generator. There are three key features of the approach. First, the kernels are explicitly expressed only by the derivatives of the f-form of the generator without computing any Fourier transforms. Second, it includes the radial kernels with the highest-order generalized Strang-Fix conditions. Finally, it requires only computing univariate derivatives of the f-form. Therefore, the approach is simple, efficient and easy to implement. As examples, the paper constructs radial kernels from some commonly used generators, including the Gaussian functions, the inverse multiquadric functions and compactly supported positive definite functions. [ABSTRACT FROM AUTHOR]

Because physical phenomena on Earth's surface occur on many different length scales, it makes sense when seeking an efficient approximation to start with a crude global approximation, and then make a sequence of corrections on finer and finer scales. It also makes sense eventually to seek fine scale features locally, rather than globally. In the present work, we start with a global multiscale radial basis function (RBF) approximation, based on a sequence of point sets with decreasing mesh norm, and a sequence of (spherical) radial basis functions with proportionally decreasing scale centered at the points. We then prove that we can 'zoom in' on a region of particular interest, by carrying out further stages of multiscale refinement on a local region. The proof combines multiscale techniques for the sphere from Le Gia, Sloan and Wendland, SIAM J. Numer. Anal. 48 (2010) and Applied Comp. Harm. Anal. 32 (2012), with those for a bounded region in ℝ from Wendland, Numer. Math. 116 (2010). The zooming in process can be continued indefinitely, since the condition numbers of matrices at the different scales remain bounded. A numerical example illustrates the process. [ABSTRACT FROM AUTHOR]

Kernel-based methods in Numerical Analysis have the advantage of yielding optimal recovery processes in the 'native' Hilbert space $\mathcal {H}$ in which they are reproducing. Continuous kernels on compact domains have an expansion into eigenfunctions that are both L -orthonormal and orthogonal in $\mathcal {H}$ (Mercer expansion). This paper examines the corresponding eigenspaces and proves that they have optimality properties among all other subspaces of $\mathcal {H}$ . These results have strong connections to n-widths in Approximation Theory, and they establish that errors of optimal approximations are closely related to the decay of the eigenvalues. Though the eigenspaces and eigenvalues are not readily available, they can be well approximated using the standard n-dimensional subspaces spanned by translates of the kernel with respect to n nodes or centers. We give error bounds for the numerical approximation of the eigensystem via such subspaces. A series of examples shows that our numerical technique via a greedy point selection strategy allows to calculate the eigensystems with good accuracy. [ABSTRACT FROM AUTHOR]

In this paper, the state-of-the-art interpolation-based model order reduction methods are applied to parameterized circuit equations. We analyze these methods in great details, through which the advantages and disadvantages of each method are illuminated. The presented model reduction methods are then tested on two circuit models. [ABSTRACT FROM AUTHOR]

Given optimal interpolation points σ,..., σ, the $\mathcal {H}_{2}$-optimal reduced order model of order r can be obtained for a linear time-invariant system of order n≫ r by simple projection (whereas it is not a trivial task to find those interpolation points). Our approach to linear time-invariant systems depending on parameters $p\in \mathbb {R}^{d}$ is to approximate their parametric dependence as a so-called metamodel, which in turn allows us to set up the corresponding parametrized reduced order models. The construction of the metamodel we suggest involves the coefficients of the characteristic polynomial and radial basis function interpolation, and thus allows for an accurate and efficient approximation of σ( p),..., σ( p). As the computation of the projection still includes large system solves, this metamodel is not sufficient to construct a fast and truly parametric reduced system. Setting up a medium-size model without extra cost, we present a possible answer to this. We illustrate the proposed method with several numerical examples. [ABSTRACT FROM AUTHOR]

We introduce an extension of the Newton formula for bivariate generalized Berzolari-Radon sets and suggest a generalization of the divided differences for that kind of sets. We apply this formula to two bivariate problems where the nodes are distributed on lines or concentric circles respectively. Some examples are provided. [ABSTRACT FROM AUTHOR]

We generate various new radial kernels by taking derivatives of known kernels with respect to scale. This is different from the well-known scale mixtures used before. In addition, we provide a simple recipe that explicitly constructs new kernels from the negative Laplacian of known kernels. Surprisingly, these two methods for generating new kernels can be proven to coincide for certain standard classes of radial kernels. The resulting radial kernels are positive definite, and a few illustrations are provided. [ABSTRACT FROM AUTHOR]

In this article we define a new class of Pythagorean-Hodograph curves built-upon a six-dimensional mixed algebraic-trigonometric space, we show their fundamental properties and compare them with their well-known quintic polynomial counterpart. A complex representation for these curves is introduced and constructive approaches are provided to solve different application problems, such as interpolating C Hermite data and constructing spirals as G transition elements between a line segment and a circle, as well as between a pair of external circles. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of designing piecewise polynomial local interpolants of non-uniformly spaced data. We provide a constructive approach that, for any assigned degree of polynomial reproduction, continuity order, and support width, allows for generating the fundamental spline functions of minimum degree having the desired properties. Finally, the proposed construction is extended to handle open sets of data and to the case of multiple knots. [ABSTRACT FROM AUTHOR]

We present a novel predictor-corrector method, called , for the numerical solutions of fractional ordinary differential equations, which are based on the polynomial interpolation and the Gauss-Lobatto quadrature w.r.t. the Jacobi-weight function $\omega (s)=(1-s)^{\alpha -1} (1+s)^{0}$. This method has the computational cost O( N) and the convergent order N, where N and N are, respectively, the total computational steps and the number of used interpolation points. The detailed error analysis is performed, and the extensive numerical experiments confirm the theoretical results and show the robustness of this method. [ABSTRACT FROM AUTHOR]

This paper describes an algebraic construction of bivariate interpolatory subdivision masks induced by three-directional box spline subdivision schemes. Specifically, given a three-directional box spline, we address the problem of defining a corresponding interpolatory subdivision scheme by constructing an appropriate correction mask to convolve with the three-directional box spline mask. The proposed approach is based on the analysis of certain polynomial identities in two variables and leads to interesting new interpolatory bivariate subdivision schemes. [ABSTRACT FROM AUTHOR]

In a similar fashion to estimates shown for Harmonic, Wachspress, and Sibson coordinates in Gillette et al. (Adv Comput Math 37(3), 417-439, ), we prove interpolation error estimates for the mean value coordinates on convex polygons suitable for standard finite element analysis. Our analysis is based on providing a uniform bound on the gradient of the mean value functions for all convex polygons of diameter one satisfying certain simple geometric restrictions. This work makes rigorous an observed practical advantage of the mean value coordinates: unlike Wachspress coordinates, the gradients of the mean value coordinates do not become large as interior angles of the polygon approach π. [ABSTRACT FROM AUTHOR]

Monotonicity-preserving approximation methods are used in numerous applications. These methods are expected to reconstruct a function from a discrete set of data preserving Monotonicity properties (i.e., the reconstructed function has to be monotone wherever the discrete data are). Most Monotonicity-preserving methods sacrifice accuracy in order to obtain Monotonicity. In this work we propose and analyze a Monotonicity-preserving Hermite interpolant that does not fully sacrifice accuracy. A key ingredient in the proposed technique is the approximation of derivatives using ENO (Essentially Non Oscillatory) and WENO (Weighted Essentially Non Oscillatory) interpolatory techniques. Then, an appropriate filtering process ensures the preservation of Monotonicity while maintaining, at the same time, the order of accuracy as high as possible. We perform several numerical experiments which confirm the properties of the proposed algorithms and compare them to other standard interpolatory approximation techniques. [ABSTRACT FROM AUTHOR]

This paper simultaneously generalizes two standard classes of radial kernels, the polyharmonic kernels related to the differential operator ( − Δ) and the Whittle-Matérn kernels related to the differential operator ( − Δ + I). This is done by allowing general differential operators of the form $\prod_{j=1}^m(-\Delta+\kappa_j^2I)$ with nonzero κ and calculating their associated kernels. It turns out that they can be explicity given by starting from scaled Whittle-Matérn kernels and taking divided differences with respect to their scale. They are positive definite radial kernels which are reproducing kernels in Hilbert spaces norm-equivalent to $W_2^m(\ensuremath{\mathbb{R}}^d)$. On the side, we prove that generalized inverse multiquadric kernels of the form $\prod_{j=1}^m(r^2+\kappa_j^2)^{-1}$ are positive definite, and we provide their Fourier transforms. Surprisingly, these Fourier transforms lead to kernels of Whittle-Matérn form with a variable scale κ( r) between κ,..., κ. We also consider the case where some of the κ vanish. This leads to conditionally positive definite kernels that are linear combinations of the above variable-scale Whittle-Matérn kernels and polyharmonic kernels. Some numerical examples are added for illustration. [ABSTRACT FROM AUTHOR]

In this paper we study subdivision schemes that both interpolate and preserve the monotonicity of the input data, and we derive a simple ratio condition that guarantees the continuous differentiability of the limit function. We then show that the condition holds for both a scheme of Kuijt and van Damme, based on rational functions, and a scheme of Sabin and Dodgson, based on square roots. [ABSTRACT FROM AUTHOR]

We introduce a vector differential operator P and a vector boundary operator B to derive a reproducing kernel along with its associated Hilbert space which is shown to be embedded in a classical Sobolev space. This reproducing kernel is a Green kernel of differential operator L: = P P with homogeneous or nonhomogeneous boundary conditions given by B, where we ensure that the distributional adjoint operator P of P is well-defined in the distributional sense. We represent the inner product of the reproducing-kernel Hilbert space in terms of the operators P and B. In addition, we find relationships for the eigenfunctions and eigenvalues of the reproducing kernel and the operators with homogeneous or nonhomogeneous boundary conditions. These eigenfunctions and eigenvalues are used to compute a series expansion of the reproducing kernel and an orthonormal basis of the reproducing-kernel Hilbert space. Our theoretical results provide perhaps a more intuitive way of understanding what kind of functions are well approximated by the reproducing kernel-based interpolant to a given multivariate data sample. [ABSTRACT FROM AUTHOR]

This paper solves the Laplace equation Δ u = 0 on domains Ω ⊂ ℝ by meshless collocation on scattered points of the boundary $\partial\Omega$. Due to the use of new positive definite kernels K( x, y) which are harmonic in both arguments and have no singularities for x = y, one can directly interpolate on the boundary, and there is no artificial boundary needed as in the Method of Fundamental Solutions. In contrast to many other techniques, e.g. the Boundary Point Method or the Method of Fundamental Solutions, we provide a solid and comprehensive mathematical foundation which includes error bounds and works for general star-shaped domains. The convergence rates depend only on the smoothness of the domain and the boundary data. Some numerical examples are included. [ABSTRACT FROM AUTHOR]

A new nonlinear representation of multiresolution decompositions and new thresholding adapted to the presence of discontinuities are presented and analyzed. They are based on a nonlinear modification of the multiresolution details coming from an initial (linear or nonlinear) scheme and on a data dependent thresholding. Stability results are derived. Numerical advantages are demonstrated on various numerical experiments. [ABSTRACT FROM AUTHOR]

We prove the optimal convergence estimate for first-order interpolants used in finite element methods based on three major approaches for generalizing barycentric interpolation functions to convex planar polygonal domains. The Wachspress approach explicitly constructs rational functions, the Sibson approach uses Voronoi diagrams on the vertices of the polygon to define the functions, and the Harmonic approach defines the functions as the solution of a PDE. We show that given certain conditions on the geometry of the polygon, each of these constructions can obtain the optimal convergence estimate. In particular, we show that the well-known maximum interior angle condition required for interpolants over triangles is still required for Wachspress functions but not for Sibson functions. [ABSTRACT FROM AUTHOR]

We consider four-point subdivision schemes of the form with any M that is originally defined as a positive-valued function for positive arguments and is extended to the whole of ℝ by setting $M(x,y):=- M(\left|x\right|,\left|y\right|)$ if x < 0, y < 0 and M( x, y) : = 0 if xy ≤ 0. For these schemes, we study analytic properties, such as convexity preservation, convergence, smoothness of the limit function, stability and approximation order, in terms of simple and easily verifiable conditions on M. Fourth-order approximation on intervals of strict convexity is also investigated. All the results known for the most frequently used schemes, the PPH scheme and the power- p schemes, are included as special cases or improved, and extended to more general situations. The various statements are illustrated by two examples and tested by numerial experiments. [ABSTRACT FROM AUTHOR]

The problem of geometric interpolation by Pythagorean-hodograph (PH) curves of general degree n is studied independently of the dimension d ≥ 2. In contrast to classical approaches, where special structures that depend on the dimension are considered (complex numbers, quaternions, etc.), the basic algebraic definition of a PH property together with geometric interpolation conditions is used. The analysis of the resulting system of nonlinear equations exploits techniques such as the cylindrical algebraic decomposition and relies heavily on a computer algebra system. The nonlinear equations are written entirely in terms of geometric data parameters and are independent of the dimension. The analysis of the boundary regions, construction of solutions for particular data and homotopy theory are used to establish the existence and (in some cases) the number of admissible solutions. The general approach is applied to the cubic Hermite and Lagrange type of interpolation. Some known results are extended and numerical examples provided. [ABSTRACT FROM AUTHOR]

In this paper we describe a general, computationally feasible strategy to deduce a family of interpolatory non-stationary subdivision schemes from a symmetric non-stationary, non-interpolatory one satisfying quite mild assumptions. To achieve this result we extend our previous work (Conti et al., Linear Algebra Appl 431(10):1971-1987, ) to full generality by removing additional assumptions on the input symbols. For the so obtained interpolatory schemes we prove that they are capable of reproducing the same space of exponential polynomials as the one generated by the original approximating scheme. Moreover, we specialize the computational methods for the case of symbols obtained by shifted non-stationary affine combinations of exponential B-splines, that are at the basis of most non-stationary subdivision schemes. In this case we find that the associated family of interpolatory symbols can be determined to satisfy a suitable set of generalized interpolating conditions at the set of the zeros (with reversed signs) of the input symbol. Finally, we discuss some computational examples by showing that the proposed approach can yield novel smooth non-stationary interpolatory subdivision schemes possessing very interesting reproduction properties. [ABSTRACT FROM AUTHOR]

This paper is devoted to the convergence and stability analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms. As soon as a nonlinear scheme can be written as a specific perturbation of a linear and convergent subdivision scheme, we show that if some contractivity properties are satisfied, then stability and convergence can be achieved. This approach is applied to various schemes, which give different new results. More precisely, we study uncentered Lagrange interpolatory linear schemes, WENO scheme (Liu et al., J Comput Phys 115:200-212, ), PPH and Power-P schemes (Amat and Liandrat, Appl Comput Harmon Anal 18(2):198-206, ; Serna and Marquina, J Comput Phys 194:632-658, ) and a nonlinear scheme using local spherical coordinates (Aspert et al., Comput Aided Geom Des 20:165-187, ). Finally, a stability proof is given for the multiresolution transform associated to a nonlinear scheme of Marinov et al. (). [ABSTRACT FROM AUTHOR]

The impact of the scaling parameter c on the accuracy of interpolation schemes using radial basis functions (RBFs) has been pointed out by several authors. Rippa (Adv Comput Math 11:193-210, ) proposes an algorithm based on the idea of cross validation for selecting a good such parameter value. In this paper we present an alternative procedure, that can be interpreted as a refinement of Rippa's algorithm for a cost function based on the euclidean norm. We point out how this method is related to the procedure of maximum likelihood estimation, which is used for identifying covariance parameters of stochastic processes in spatial statistics. Using the same test functions as Rippa we show that our algorithm compares favorably with cross validation in many cases and discuss its limitations. Finally we present some computational aspects of our algorithm. [ABSTRACT FROM AUTHOR]

It is often observed that interpolation based on translates of radial basis functions or non-radial kernels is numerically unstable due to exceedingly large condition of the kernel matrix. But if stability is assessed in function space without considering special bases, this paper proves that kernel-based interpolation is stable. Provided that the data are not too wildly scattered, the L2 or L ∞ norms of interpolants can be bounded above by discrete ℓ2 and ℓ ∞ norms of the data. Furthermore, Lagrange basis functions are uniformly bounded and Lebesgue constants grow at most like the square root of the number of data points. However, this analysis applies only to kernels of limited smoothness. Numerical examples support our bounds, but also show that the case of infinitely smooth kernels must lead to worse bounds in future work, while the observed Lebesgue constants for kernels with limited smoothness even seem to be independent of the sample size and the fill distance. [ABSTRACT FROM AUTHOR]

We present a concrete method to build discrete biorthogonal systems such that the wavelet filters have any number of vanishing moments. Several algorithms are proposed to construct multivariate biorthogonal wavelets with any general dilation matrix and arbitrary order of vanishing moments. Examples are provided to illustrate the general theory and the advantages of the algorithms. [ABSTRACT FROM AUTHOR]

We discuss polynomial interpolation in several variables from a polynomial ideal point of view. One of the results states that if I is a real polynomial ideal with real variety and if its codimension is equal to the cardinality of its variety, then for each monomial order there is a unique polynomial that interpolates on the points in the variety. The result is motivated by the problem of constructing cubature formulae, and it leads to a theorem on cubature formulae which can be considered an extension of Gaussian quadrature formulae to several variables. [ABSTRACT FROM AUTHOR]

The H-basis concept allows, similarly to the Gröbner basis concept, a reformulation of nonlinear problems in terms of linear algebra. We exhibit parallels of the two concepts, show properties of H-bases, discuss their construction and uniqueness questions, and prove that n polynomials in n variables are, under mild conditions, already H-bases. We apply H-bases to the solution of polynomial systems by the eigenmethod and to multivariate interpolation. [ABSTRACT FROM AUTHOR]

An algorithm is derived for generating the information needed to pass efficiently between multi-indices of neighboring degrees, of use in the construction and evaluation of interpolating polynomials and in the construction of good bases for polynomial ideals. [ABSTRACT FROM AUTHOR]

We study polynomial interpolation on a d-dimensional cube, where d is large. We suggest to use the least solution at sparse grids with the extrema of the Chebyshev polynomials. The polynomial exactness of this method is almost optimal. Our error bounds show that the method is universal, i.e., almost optimal for many different function spaces. We report on numerical experiments for d = 10 using up to 652 065 interpolation points. [ABSTRACT FROM AUTHOR]

It is well known that the degree raised Bernstein–Bézier coefficients of degree n of a polynomial g converge to g at the rate 1/ n. In this paper we consider the polynomial A n( g) of degree ⩼ n interpolating the coefficients. We show how A n can be viewed as an inverse to the Bernstein polynomial operator and that the derivatives A n( g)(r) converge uniformly to g(r) at the rate 1/ n for all r. We also give an asymptotic expansion of Voronovskaya type for A n( g) and discuss some shape preserving properties of this polynomial. [ABSTRACT FROM AUTHOR]

We study multivariate integration and approximation for various classes of functions of d variables with arbitrary d. We consider algorithms that use function evaluations as the information about the function. We are mainly interested in verifying when integration and approximation are tractable and strongly tractable. Tractability means that the minimal number of function evaluations needed to reduce the initial error by a factor of ɛ is bounded by C( d)ɛ− p for some exponent p independent of d and some function C( d). Strong tractability means that C( d) can be made independent of d. The exponents of tractability and strong tractability are defined as the smallest powers of ɛ{-1} in these bounds. We prove that integration is strongly tractable for some weighted Korobov and Sobolev spaces as well as for the Hilbert space whose reproducing kernel corresponds to the covariance function of the isotropic Wiener measure. We obtain bounds on the exponents, and for some cases we find their exact values. For some weighted Korobov and Sobolev spaces, the strong exponent is the same as the exponent for d=1, whereas for the third space it is 2. For approximation we also consider algorithms that use general evaluations given by arbitrary continuous linear functionals as the information about the function. Our main result is that the exponents are the same for general and function evaluations. This holds under the assumption that the orthonormal eigenfunctions of the covariance operator have uniformly bounded L∞ norms. This assumption holds for spaces with shift-invariant kernels. Examples of such spaces include weighted Korobov spaces. For a space with non shift invariant kernel, we construct the corresponding space with shift-invariant kernel and show that integration and approximation for the non-shift-invariant kernel are no harder than the corresponding problems with the shift-invariant kernel. If we apply this construction to a weighted Sobolev space, whose kernel is non-shift-invariant, then we obtain the corresponding Korobov space. This enables us to derive the results for weighted Sobolev spaces. [ABSTRACT FROM AUTHOR]

A new C ∞ interpolant is presented for the univariate Hermite interpolation problem. It differs from the classical solution in that the interpolant is of non polynomial nature. Its basis functions are a set of simple, compact support, transcendental functions. The interpolant can be regarded as a truncated Multipoint Taylor series. It has essential singularities at the sample points, but is well behaved over the real axis and satisfies the given functional data. The interpolant converges to the underlying real analytic function when (i) the number of derivatives at each point tends to infinity and the number of sample points remains finite, and when (ii) the spacing between sample points tends to zero and the number of specified derivatives at each sample point remains finite. A comparison is made between the numerical results achieved with the new method and those obtained with polynomial Hermite interpolation. In contrast with the classical polynomial solution, the new interpolant does not suffer from any ill conditioning, so it is always numerically stable. In addition, it is a much more computationally efficient method than the polynomial approach. [ABSTRACT FROM AUTHOR]