Search

In this paper, we consider the structure-preserving model order reduction problem for multi-input/multi-output bilinear control systems by tangential interpolation. We propose a new type of tangential interpolation problem for structured bilinear systems, for which we develop a new structure-preserving interpolation framework. This new framework extends and generalizes different formulations of tangential interpolation for bilinear systems from the literature and also provides a unifying framework. We then derive explicit conditions on the projection spaces to enforce tangential interpolation in different settings, including conditions for tangential Hermite interpolation. The analysis is illustrated by means of three numerical examples. [ABSTRACT FROM AUTHOR]

We introduce interpolation operators with approximation and stability properties suited for parabolic problems in primal and mixed formulations. We derive localized error estimates for tensor product meshes (occurring in classical time-marching schemes) as well as locally in space-time refined meshes. [ABSTRACT FROM AUTHOR]

The barycentric forms of polynomial and rational interpolation have recently gained popularity, because they can be computed with simple, efficient, and numerically stable algorithms. In this paper, we show more generally that the evaluation of any function that can be expressed as r (x) = ∑ i = 0 n a i (x) f i / ∑ j = 0 m b j (x) in terms of data values f i and some functions a i and b j for i = 0 , ... , n and j = 0 , ⋯ , m with a simple algorithm that first sums up the terms in the numerator and the denominator, followed by a final division, is forward and backward stable under certain assumptions. This result includes the two barycentric forms of rational interpolation as special cases. Our analysis further reveals that the stability of the second barycentric form depends on the Lebesgue constant associated with the interpolation nodes, which typically grows with n, whereas the stability of the first barycentric form depends on a similar, but different quantity, that can be bounded in terms of the mesh ratio, regardless of n. We support our theoretical results with numerical experiments. [ABSTRACT FROM AUTHOR]

The classical serendipity and mixed finite element spaces suffer from poor approximation on nondegenerate, convex quadrilaterals. In this paper, we develop families of direct serendipity and direct mixed finite element spaces, which achieve optimal approximation properties and have minimal local dimension. The set of local shape functions for either the serendipity or mixed elements contains the full set of scalar or vector polynomials of degree r, respectively, defined directly on each element (i.e., not mapped from a reference element). Because there are not enough degrees of freedom for global H 1 or H (div) conformity, exactly two supplemental shape functions must be added to each element when r ≥ 2 , and only one when r = 1 . The specific choice of supplemental functions gives rise to different families of direct elements. These new spaces are related through a de Rham complex. For index r ≥ 1 , the new families of serendipity spaces DS r + 1 are the precursors under the curl operator of our direct mixed finite element spaces, which can be constructed to have reduced or full H (div) approximation properties. One choice of direct serendipity supplements gives the precursor of the recently introduced Arbogast–Correa spaces (SIAM J Numer Anal 54:3332–3356, 2016. https://doi.org/10.1137/15M1013705). Other fully direct serendipity supplements can be defined without the use of mappings from reference elements, and these give rise in turn to fully direct mixed spaces. Our development is constructive, so we are able to give global bases for our spaces. Numerical results are presented to illustrate their properties. [ABSTRACT FROM AUTHOR]

In this paper we study an iterative approach to the Hermite interpolation problem, which first constructs an interpolant of the function values at n+1 nodes and then successively adds m correction terms to fit the data up to the mth derivatives. In the case of polynomial interpolation, this simply reproduces the classical Hermite interpolant, but the approach is general enough to be used in other settings. In particular, we focus on the family of rational Floater-Hormann interpolants, which are based on blending local polynomial interpolants of degree d with rational blending functions. For this family, the proposed method results in rational Hermite interpolants, which depend linearly on the data, with numerator and denominator of degree at most (m+1)(n+1)-1 and (m+1)(n-d), respectively. They converge at the rate of O(h(m+1)(d+1)) as the mesh size h converges to 0. After deriving the barycentric form of these interpolants, we prove the convergence rate for m=1 and m=2, and show that the approximation results compare favourably with other constructions. [ABSTRACT FROM AUTHOR]

We present and analyze an approximation scheme for a class of highly oscillatory kernel functions, taking the 2D and 3D Helmholtz kernels as examples. The scheme is based on polynomial interpolation combined with suitable pre- and post-multiplication by plane waves. It is shown to converge exponentially in the polynomial degree and supports multilevel approximation techniques. Our convergence analysis may be employed to establish exponential convergence of certain classes of fast methods for discretizations of the Helmholtz integral operator that feature polylogarithmic-linear complexity. [ABSTRACT FROM AUTHOR]

We present a new analysis of the stability of extended Floater-Hormann interpolants, in which both noisy data and rounding errors are considered. Contrary to what is claimed in the current literature, we show that the Lebesgue constant of these interpolants can grow exponentially with the parameters that define them, and we emphasize the importance of using the proper interpretation of the Lebesgue constant in order to estimate correctly the effects of noise and rounding errors. We also present a simple condition that implies the backward instability of the barycentric formula used to implement extended interpolants. Our experiments show that extended interpolants mentioned in the literature satisfy this condition and, therefore, the formula used to implement them is not backward stable. Finally, we explain that the extrapolation step is a significant source of numerical instability for extended interpolants based on extrapolation. [ABSTRACT FROM AUTHOR]

We analyze the effects of rounding errors in the nodes on polynomial barycentric interpolation. These errors are particularly relevant for the first barycentric formula with the Chebyshev points of the second kind. Here, we propose a method for reducing them. [ABSTRACT FROM AUTHOR]

We develop a constructive piecewise polynomial approximation theory in weighted Sobolev spaces with Muckenhoupt weights for any polynomial degree. The main ingredients to derive optimal error estimates for an averaged Taylor polynomial are a suitable weighted Poincaré inequality, a cancellation property and a simple induction argument. We also construct a quasi-interpolation operator, built on local averages over stars, which is well defined for functions in $$L^1$$ . We derive optimal error estimates for any polynomial degree on simplicial shape regular meshes. On rectangular meshes, these estimates are valid under the condition that neighboring elements have comparable size, which yields optimal anisotropic error estimates over $$n$$ -rectangular domains. The interpolation theory extends to cases when the error and function regularity require different weights. We conclude with three applications: nonuniform elliptic boundary value problems, elliptic problems with singular sources, and fractional powers of elliptic operators. [ABSTRACT FROM AUTHOR]

Let a sufficiently smooth function $$f$$ on $$[-1,1]$$ be sampled at $$n+1$$ equispaced points, and let $$k\ge 0$$ be given. An Euler-Maclaurin interpolant to the data is defined, consisting of a sum of a degree $$k$$ algebraic polynomial and a degree $$n$$ trigonometric polynomial, which deviates from $$f$$ by $$O(n^{-k})$$ and whose integral is equal to the order $$k$$ Euler-Maclaurin approximation of the integral of $$f$$ . This interpolant makes use of the same derivatives $$f^{( j)}(\pm 1)$$ as the Euler-Maclaurin formula. A variant Gregory interpolant is also defined, based on finite difference approximations to the derivatives, whose integral (for $$k$$ odd) is equal to the order $$k$$ Gregory approximation to the integral. [ABSTRACT FROM AUTHOR]

This paper is aimed at developing new shape functions adapted to the scalar wave equation with smooth (possibly vanishing) coefficients and investigates the numerical analysis of their interpolation properties. The interpolation is local, but high order convergence is shown with respect to the size of the domain considered. The new basis functions are then implemented in a numerical method to solve a scalar wave equation problem with a mixed boundary condition. The main theoretical result states that any given order of approximation can be achieved by an appropriate choice of parameters for the design of the shape functions. The convergence is studied with respect to the size of the domain, which is referred to in the literature as $$h$$ -convergence. [ABSTRACT FROM AUTHOR]

We present a novel theoretical approach to the analysis of adaptive quadratures and adaptive Simpson quadratures in particular which leads to the construction of a new algorithm for automatic integration. For a given function $$f\in C^4$$ with $$f^{(4)}\ge 0$$ and possible endpoint singularities the algorithm produces an approximation to $$\int _a^bf(x)\,{\mathrm d}x$$ within a given $$\varepsilon $$ asymptotically as $$\varepsilon \rightarrow 0$$ . Moreover, it is optimal among all adaptive Simpson quadratures, i.e., needs the minimal number $$n(f,\varepsilon )$$ of function evaluations to obtain an $$\varepsilon $$ -approximation and runs in time proportional to $$n(f,\varepsilon )$$ . [ABSTRACT FROM AUTHOR]

In this article, the construction of nested bases approximations to discretizations of integral operators with oscillatory kernels is presented. The new method has log-linear complexity and generalizes the adaptive cross approximation method to high-frequency problems. It allows for a continuous and numerically stable transition from low to high frequencies. [ABSTRACT FROM AUTHOR]

We present a new analysis of the stability of the first and second barycentric formulae for interpolation at the Chebyshev points of the second kind. Our theory shows that the second formula is more stable than previously thought and our experiments confirm its stability in practice.We also extend our current understanding regarding the accuracy problems of the first barycentric formula. [ABSTRACT FROM AUTHOR]

We consider an algebraic method for reconstruction of a harmonic function in the unit disk via a finite number of values of its Radon projections. The approach is to seek a harmonic polynomial which matches given values of Radon projections along some chords of the unit circle. We prove an analogue of the famous Marr's formula for computing the Radon projection of the basis orthogonal polynomials in our setting of harmonic polynomials. Using this result, we show unique solvability for a family of schemes where all chords are chosen at equal distance to the origin. For the special case of chords forming a regular convex polygon, we prove error estimates on the unit circle and in the unit disk. We present an efficient reconstruction algorithm which is robust with respect to noise in the input data and provide numerical examples. [ABSTRACT FROM AUTHOR]

We study scalar multivariate non-stationary subdivision schemes with a general integer 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. [ABSTRACT FROM AUTHOR]

In this paper, the theoretical convergence rate of the trapezoidal rule combined with the double-exponential (DE) transformation is given for a class of functions for which the single-exponential (SE) transformation is suitable. It is well known that the DE transformation enables the rule to achieve a much higher rate of convergence than the SE transformation, and the convergence rate has been analyzed and justified theoretically under a proper assumption. Here, it should be emphasized that the assumption is more severe than the one for the SE transformation, and there actually exist some examples such that the trapezoidal rule with the SE transformation achieves its usual rate, whereas the rule with DE does not. Such cases have been observed numerically, but no theoretical analysis has been given thus far. This paper reveals the theoretical rate of convergence in such cases, and it turns out that the DE's rate is almost the same as, but slightly lower than that of the SE. By using the analysis technique developed here, the theoretical convergence rate of the Sinc approximation with the DE transformation is also given for a class of functions for which the SE transformation is suitable. The result is quite similar to above; the convergence rate in the DE case is slightly lower than in the SE case. Numerical examples which support those two theoretical results are also given. [ABSTRACT FROM AUTHOR]

In this paper, we consider the particular case of the general rational Hermite interpolation problem where only the value of the function is interpolated at some points, and where the function and its first derivatives agree at the origin. Thus, the interpolants constructed in this way possess a Padé-type property at 0. Numerical examples show the interest of the procedure. The interpolation procedure can be easily modified to introduce a partial knowledge on the poles and the zeros of the function to approximated. A strategy for removing the spurious poles is explained. A formula for the error is proved in the real case. Applications are given. [ABSTRACT FROM AUTHOR]

Error estimates with explicit constants are given for approximations of functions, definite integrals and indefinite integrals by means of the Sinc approximation. Although in the literature various error estimates have already been given for these approximations, those estimates were basically for examining the rates of convergence, and several constants were left unevaluated. Giving more explicit estimates, i.e., evaluating these constants, is of great practical importance, since by this means we can reinforce the useful formulas with the concept of 'verified numerical computations.' In this paper we reveal the explicit form of all constants in a computable form under the same assumptions of the existing theorems: the function to be approximated is analytic in a suitable region. We also improve some formulas themselves to decrease their computational costs. Numerical examples that confirm the theory are also given. [ABSTRACT FROM AUTHOR]

We construct trivariate $$C^r$$ macro-elements for any $$r\ge 1$$ over the Worsey-Farin refinement of any tetrahedral partition. This extends the construction of $$C^1$$ cubic Worsey-Farin elements and $$C^2$$ elements of degree nine to the $$C^r$$ situation with $$r>2$$. We also show that the degree of polynomials used for our macro-elements is the lowest. [ABSTRACT FROM AUTHOR]

In this article, a method for constructing nested bases approximations to large-scale fully populated discretizations of integral operators is introduced. The scheme uses only few of the matrix entries for approximating the whole matrix. In this sense, it is similar to the adaptive cross approximation method. However, its computational complexity is improved. [ABSTRACT FROM AUTHOR]

Recent results reveal that the family of barycentric rational interpolants introduced by Floater and Hormann is very well-suited for the approximation of functions as well as their derivatives, integrals and primitives. Especially in the case of equidistant interpolation nodes, these infinitely smooth interpolants offer a much better choice than their polynomial analogue. A natural and important question concerns the condition of this rational approximation method. In this paper we extend a recent study of the Lebesgue function and constant associated with Berrut's rational interpolant at equidistant nodes to the family of Floater-Hormann interpolants, which includes the former as a special case. [ABSTRACT FROM AUTHOR]

Given a function f defined on a bounded polygonal domain $${\Omega \subset \mathbb{R}^2}$$ and a number N > 0, we study the properties of the triangulation $${\mathcal{T}_N}$$ that minimizes the distance between f and its interpolation on the associated finite element space, over all triangulations of at most N elements. The error is studied in the W semi-norm for 1 ≤ p < ∞, and we consider Lagrange finite elements of arbitrary polynomial order m − 1. We establish sharp asymptotic error estimates as N → +∞ when the optimal anisotropic triangulation is used. A similar problem has been studied in Babenko et al. (East J Approx. 12(1):71-101, ), Cao (J Numer Anal. 45(6):2368-2391, ), Chen et al. (Math Comput. 76:179-204, ), Cohen (Multiscale, Nonlinear and Adaptive Approximation. Springer, Berlin, ), Mirebeau (Constr Approx. 32(2):339-383, ), but with the error measured in the L norm. The extension of this analysis to the W norm is required in order to match more closely the needs of numerical PDE analysis, and it is not straightforward. In particular, the meshes which satisfy the optimal error estimate are characterized by a metric describing the local aspect ratio of each triangle and by a geometric constraint on their maximal angle, a second feature that does not appear for the L error norm. Our analysis also provides with practical strategies for designing meshes such that the interpolation error satisfies the optimal estimate up to a fixed multiplicative constant. [ABSTRACT FROM AUTHOR]

In this paper we introduce a generalized Sobolev space by defining a semi-inner product formulated in terms of a vector distributional operator P consisting of finitely or countably many distributional operators P, which are defined on the dual space of the Schwartz space. The types of operators we consider include not only differential operators, but also more general distributional operators such as pseudo-differential operators. We deduce that a certain appropriate full-space Green function G with respect to L := P P now becomes a conditionally positive function. In order to support this claim we ensure that the distributional adjoint operator P of P is well-defined in the distributional sense. Under sufficient conditions, the native space (reproducing-kernel Hilbert space) associated with the Green function G can be embedded into or even be equivalent to a generalized Sobolev space. As an application, we take linear combinations of translates of the Green function with possibly added polynomial terms and construct a multivariate minimum-norm interpolant s to data values sampled from an unknown generalized Sobolev function f at data sites located in some set $${X \subset \mathbb{R}^d}$$. We provide several examples, such as Matérn kernels or Gaussian kernels, that illustrate how many reproducing-kernel Hilbert spaces of well-known reproducing kernels are equivalent to a generalized Sobolev space. These examples further illustrate how we can rescale the Sobolev spaces by the vector distributional operator P. Introducing the notion of scale as part of the definition of a generalized Sobolev space may help us to choose the 'best' kernel function for kernel-based approximation methods. [ABSTRACT FROM AUTHOR]

We recently showed that the class of Quasi Extended Chebyshev spaces is the largest class of sufficiently differentiable functions permitting design. In previous articles we mentioned a simple procedure to build such spaces by means of both generalised derivatives associated with non-vanishing weight functions and two-dimensional Chebyshev spaces. In the present one we prove that, conversely, on a closed bounded interval, any Quasi Extended Chebyshev space can be obtained via the latter procedure. We then draw a few interesting consequences from the latter result. [ABSTRACT FROM AUTHOR]

We present a method able to recover location and residue of poles of functions meromorphic in a half-plane from samples of the function on the real positive semi-axis. The function is assumed to satisfy appropriate asymptotic conditions including, in particular, that required by Carlson's theorem. The peculiar features of the present procedure are: (a) it does not make use of the approximation of meromorphic functions by rational functions; (b) it does not use the standard methods of regularization of ill-posed problems. The data required for the determination of the pole parameters (i.e., location and residue) are the approximate values of the meromorphic function on a finite set of equidistant points on the real positive semi-axis. We show that this method is numerically stable by proving that the algorithm is convergent as the number of data points tends to infinity and the noise on the input data goes to zero. Moreover, we can also evaluate the degree of approximation of the estimates of pole location and residue which we obtain from the knowledge of a finite number of noisy samples. [ABSTRACT FROM AUTHOR]

We show that many spaces of multivariate splines possess additional smoothness (supersmoothness) at certain faces where polynomial pieces join together. This phenomenon affects the dimension and interpolating properties of splines spaces. The supersmoothness is caused by the geometry of the underlying partition. [ABSTRACT FROM AUTHOR]

We present a non-stationary, non-uniform scheme for two-point Hermite subdivision. The novelty of this approach relies on a geometric interpretation of the subdivision steps—related to generalized Bernstein bases—which permits to overcome the usually unavoidable analytical difficulties. The main advantages consist in extra smoothness conditions, which in turn produce highly regular limit curves, and in an elegant structure of the subdivision—described by three de Casteljau type matrices. As a by-product, the scheme is inherently shape preserving. [ABSTRACT FROM AUTHOR]

We propose a method for filling a n-sided hole, $5\leq n\leq 8$ , that interpolates n connected boundary curves of a given net of patches. This method allows the joining with patches defined in many different ways. A new class of blowing up pole-functions is introduced in order to build a G $^{2}$ -continuous n-sided filling surface. This filling surface is in one piece, image of $[0,1]^{2}$ . [ABSTRACT FROM AUTHOR]

In this paper we investigate a stability estimate needed in hybrid finite and boundary element methods, especially in hybrid coupled domain decomposition methods including mortar finite elements. This stability estimate is equivalent to the stability of a generalized $L_2$ projection in certain Sobolev spaces. Using piecewise linear trial spaces and appropriate piecewise constant test spaces, the stability of the generalized $L_2$ projection is proved assuming some mesh conditions locally. [ABSTRACT FROM AUTHOR]

Summary. Macro-elements of smoothness $C^r$ on Clough-Tocher triangle splits are constructed for all $r \ge 0$ . These new elements are improvements on elements constructed in [11] in that (disproving a conjecture made there) certain unneeded degrees of freedom have been removed. Numerical experiments on Hermite interpolation with the new elements are included. [ABSTRACT FROM AUTHOR]

We prove a priori anisotropic estimates for the $L^2$ and $H^1$ interpolation error on linear finite elements. The full information about the mapping from a reference element is employed to separate the contribution to the elemental error coming from different directions. This new $H^1$ error estimate does not require the “maximal angle condition”. The analysis has been carried out for the 2D case, but may be extended to three dimensions. Numerical experiments have been carried out to test our theoretical results. [ABSTRACT FROM AUTHOR]

The paper deals with a non-conforming finite element method on a class of anisotropic meshes. The Crouzeix-Raviart element is used on triangles and tetrahedra. For rectangles and prismatic (pentahedral) elements a novel set of trial functions is proposed. Anisotropic local interpolation error estimates are derived for all these types of element and for functions from classical and weighted Sobolev spaces. The consistency error is estimated for a general differential equation under weak regularity assumptions. As a particular application, an example is investigated where anisotropic finite element meshes are appropriate, namely the Poisson problem in domains with edges. A numerical test is described. [ABSTRACT FROM AUTHOR]

In this paper we prove the stability of the $L_2$ projection onto the finite element trial space of piecewise polynomial, in particular, piecewise linear basis functions in $H^s(\Omega) $ for $ s \in (0,1] $ . We formulate explicit and computable local mesh conditions to be satisfied which depend on the Sobolev index s. In conclusion we prove a stability condition needed in the numerical analysis of mixed and hybrid boundary element methods as well as in the construction of efficient preconditioners in adaptive boundary and finite element methods. [ABSTRACT FROM AUTHOR]

This article considers the problem of approximating a general asymptotically smooth function in two variables, typically arising in integral formulations of boundary value problems, by a sum of products of two functions in one variable. From these results an iterative algorithm for the low-rank approximation of blocks of large unstructured matrices generated by asymptotically smooth functions is developed. This algorithm uses only few entries from the original block and since it has a natural stopping criterion the approximative rank is not needed in advance. [ABSTRACT FROM AUTHOR]

Weakly coupled systems of inequalities arise frequently in the consideration of so-called direct methods for shape preserving interpolation. In this paper, a composition based staircase algorithm for bidiagonal systems subject to boundary conditions is developed. Using the compositions of the corresponding relations instead of their projections, we are able to derive a necessary and sufficient solvability criterion. Further, all solutions of the system can be constructed in a backward pass. To illustrate the general approach, we consider in detail the problem of convex interpolation by cubic $C^1$ splines. For this problem, an algorithm of the complexity O( n) in the number n of data points is obtained. [ABSTRACT FROM AUTHOR]

Using a method based on quadratic nodal spline interpolation, we define a quadrature rule with respect to arbitrary nodes, and which in the case of uniformly spaced nodes corresponds to the Gregory rule of order two, i.e. the Lacroix rule, which is an important example of a trapezoidal rule with endpoint corrections. The resulting weights are explicitly calculated, and Peano kernel techniques are then employed to establish error bounds in which the associated error constants are shown to grow at most linearly with respect to the mesh ratio parameter. Specializing these error estimates to the case of uniform nodes, we deduce non-optimal order error constants for the Lacroix rule, which are significantly smaller than those calculated by cruder methods in previous work, and which are shown here to compare favourably with the corresponding error constants for the Simpson rule. [ABSTRACT FROM AUTHOR]

Motivated by earlier considerations of interval interpolation problems as well as a particular application to the reconstruction of railway bridges, we deal with the problem of univariate convexity preserving interval interpolation. To allow convex interpolation, the given data intervals have to be in (strictly) convex position. This property is checked by applying an abstract three-term staircase algorithm, which is presented in this paper. Additionally, the algorithm provides strictly convex ordinates belonging to the data intervals. Therefore, the known methods in convex Lagrange interpolation can be used to obtain interval interpolants. In particular, we refer to methods based on polynomial splines defined on grids with additional knots. [ABSTRACT FROM AUTHOR]

The main result of this paper is an abstract version of the Kowalewski– Ciarlet– Wagschal multipoint Taylor formula for representing the pointwise error in multivariate Lagrange interpolation. Several applications of this result are given in the paper. The most important of these is the construction of a multipoint Taylor error formula for a general finite element, together with the corresponding $L_p$ –error bounds. Another application is the construction of a family of error formulæ for linear interpolation (indexed by real measures of unit mass) which includes some recently obtained formulæ. It is also shown how the problem of constructing an error formula for Lagrange interpolation from a D–invariant space of polynomials with the property that it involves only derivatives which annihilate the interpolating space can be reduced to the problem of finding such a formula for a ‘simpler’ one–point interpolation map. [ABSTRACT FROM AUTHOR]

The recovery step is the most expensive algorithmic ingredient in modern essentially non-oscillatory (ENO) shock capturing methods on triangular meshes for the numerical simulation of compressible fluid flow. While recovery polynomials in Newton form are used in one-dimensional ENO schemes it is a priori not clear whether such useful as well as numerically stable form of polynomials exists in multiple dimensions. As was observed in [1] a very general answer to this question was provided by Mühlbach in two subsequent papers [15] and [16]. We generalise his interpolation theory further to the general recovery problem and outline the use of Mühlbach's expansion in ENO schemes. Numerical examples show the usefulness of this approach in the problem of recovery from cell average data. [ABSTRACT FROM AUTHOR]

Usually, the minimal dimension of a finite element space is closely related to the geometry of the physical object of interest. This means that sometimes the resolution of small micro-structures in the domain requires an inadequately fine finite element grid from the viewpoint of the desired accuracy. This fact limits also the application of multi-grid methods to practical situations because the condition that the coarsest grid should resolve the physical object often leads to a huge number of unknowns on the coarsest level. We present here a strategy for coarsening finite element spaces independently of the shape of the object. This technique can be used to resolve complicated domains with only few degrees of freedom and to apply multi-grid methods efficiently to PDEs on domains with complex boundary. In this paper we will prove the approximation property of these generalized FE spaces. [ABSTRACT FROM AUTHOR]

We describe algorithms for constructing point sets at which interpolation by spaces of bivariate splines of arbitrary degree and smoothness is possible. The splines are defined on rectangular partitions adding one or two diagonals to each rectangle. The interpolation sets are selected in such a way that the grid points of the partition are contained in these sets, and no large linear systems have to be solved. Our method is to generate a net of line segments and to choose point sets in these segments which satisfy the Schoenberg-Whitney condition for certain univariate spline spaces such that a principle of degree reduction can be applied. In order to include the grid points in the interpolation sets, we give a sufficient Schoenberg-Whitney type condition for interpolation by bivariate splines supported in certain cones. This approach is completely different from the known interpolation methods for bivariate splines of degree at most three. Our method is illustrated by some numerical examples. [ABSTRACT FROM AUTHOR]

We present a new ``second generation" reconstruction algorithm for irregular sampling, i\@.e\@. for the problem of recovering a band-limited function from its non-uniformly sampled values. The efficient new method is a combination of the adaptive weights method which was developed by the two first named authors and the method of conjugate gradients for the solution of positive definite linear systems. The choice of "adaptive weights" can be seen as a simple but very efficient method of preconditioning. Further substantial acceleration is achieved by utilizing the Toeplitz-type structure of the system matrix. This new algorithm can handle problems of much larger dimension and condition number than have been accessible so far. Furthermore, if some gaps between samples are large, then the algorithm can still be used as a very efficient extrapolation method across the gaps. [ABSTRACT FROM AUTHOR]

The Gregory rule is a well-known example in numerical quadrature of a trapezoidal rule with endpoint corrections of a given order. In the literature, the methods of constructing the Gregory rule have, in contrast to Newton-Cotes quadrature, not been based on the integration of an interpolant. In this paper, after first characterizing an even-order Gregory interpolant by means of a generalized Lagrange interpolation operator, we proceed to explicitly construct such an interpolant by employing results from nodal spline interpolation, as established in recent work by the author and C.H. Rohwer. Nonoptimal order error estimates for the Gregory rule of even order are then easily obtained. [ABSTRACT FROM AUTHOR]

In this paper, we derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Given n distinct points z in the unit disk | z|<1 and n complex numbers w satisfying the Pick condition for 1≦ i≦ n, the new Nevanlinna-Pick interpolation algorithm requires only O(n) arithmetic operations to evaluate the interpolatory rational function at a particular value of z, in contrast to the classical algorithm which requires O( n) arithmetic operations to compute the so-called Fenyves array (which is inherent in the classical algorithm). The new algorithm bypasses the generation of the Fenyves array to speed up the computation, and also yields a parallel scheme requiring only O(log n) arithmetic operations on a concurrent-read, exclusive-write parallel random access machine with n processors. We must remark that the rational function f(z) computed by the new algorithm is one degree higher than the function computed by the classical algorithm. [ABSTRACT FROM AUTHOR]

We describe an algorithm for (bivariate) cardinal interpolation which can be applied to translates of 'basis functions' which include box splines or radial basis functions. The algorithm is based on a representation of the Fourier transform of the fundamental interpolant, hence Fast Fourier Transform methods are available. In numerical tests the 4-directional box spline (transformed to the characteristical submodule of ℤ), the thin plate spline, and the multiquadric case give comparably equal and good results. [ABSTRACT FROM AUTHOR]

The authors construct some extended interpolation formulae to approximate the derivatives of a function in uniform norm. They prove theorems on uniform convergence and give estimates of pointwise type and of simultaneous approximation. [ABSTRACT FROM AUTHOR]

Construction of optimal triangular meshes for controlling the errors in gradient estimation for piecewise linear interpolation of data functions in the plane is discussed. Using an appropriate linear coordinate transformation, rigorously optimal meshes for controlling the error in quadratic data functions are constructed. It is shown that the transformation can be generated as a curvilinear coordinate transformation for any C data function with nonsingular Hessian matrix. Using this transformation, a construction of nearly optimal meshes for general data functions is described and the error equilibration properties of these meshes discussed. In particular, it is shown that equilibration of errors is not a sufficient condition for optimality. A comparison of meshes generated under several different criteria is made, and their equilibrating properties illustrated. [ABSTRACT FROM AUTHOR]