A fast algorithm for the multivariate Birkhoff interpolation problem

Multivariate Birkhoff interpolation is the most complicated polynomial interpolation problem and the theory about it is far from systematic and complete. In this paper we derive an Algorithm B-MB (Birkhoff-Monomial Basis) and prove B-MB giving the minimal interpolation monomial basis w.r.t. the lexicographical order of the multivariate Birkhoff problem. This algorithm is the generalization of Algorithm MB in [L. Cerlinco, M. Mureddu, From algebraic sets to monomial linear bases by means of combinatorial algorithms, Discrete Math. 139 (1995) 73–87] which is a well known fast algorithm used to compute the interpolation monomial basis of the Hermite interpolation problem.     

The proper interpolation space for multivariate Birkhoff interpolation

Multivariate Birkhoff interpolation problem has many important applications, such as in finite element method. In this paper two algorithms are given to compute the basis of the minimal interpolation space and the lower interpolation space respectively for an arbitrary given node set and the corresponding interpolation conditions on each node. We can get the monomial basis, Newton-type basis as well as Lagrange-type basis. The interpolation polynomial can be derived from the basis directly.     

Newton basis for multivariate Birkhoff interpolation

Multivariate Birkhoff interpolation is the most complex polynomial interpolation problem and people know little about it so far. In this paper, we introduce a special new type of multivariate Birkhoff interpolation and present a Newton paradigm for it. Using the algorithms proposed in this paper, we can construct a Hermite system for any interpolation problem of this type and then obtain a Newton basis for the problem w.r.t. the Hermite system.     

Bidiagonal decomposition of totally positive Bernstein-Vandermonde matrices

The class of Bernstein-Vandermonde matrices (a generalization of Vandermonde matrices arising when the monomial basis is replaced by the Bernstein basis) is considered. A convenient ordering of their rows makes these matrices strictly totally positive. By using results related to total positivity and Neville elimination, an algorithm for computing the bidiagonal decomposition of a Bernstein-Vandermonde matrix is constructed. The use of explicit expressions for the determinants involved in the process serves to make the algorithm both fast and accurate. One of the applications of our algorithm is the design of fast and accurate algorithms for solving Lagrange interpolation problems when using the Bernstein basis, an approach useful for the field of Computer Aided Geometric Design since it avoids the stability problems involved with basis transformations between the Bernstein and the monomial bases. A different application consists of the use of the bidiagonal decomposition as an intermediate step of the computation of the eigenvalues and the singular value decomposition of a totally positive Bernstein-Vandermonde matrix. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

AN EXTREMAL APPROACH TO BIRKHOFF QUADRATURE FORMULAS

1. Introduction and Main ResultsIn tfor paPer we shaJl use the ddstions and notations of [3l. Let E = (e'k)7t' kt. be anincidence matrir with entries consisting of zeros and ones and satisfying lEl:= Z.,* ei* = n + 1(here we allow a zero row ). Furthermore, in wha follOws we assume that(A) E satisfies the P6lya condition(B) all sequences of E in the interior rows, 0 < i < m + 1, are even.Let Sm denote the set of poiats X = (xo, z1 l "') xm, x.+1) fOr whichand Sm its clOusure. If some O…     

Birkhoff型三角插值

1 引言 Birkhoff三角插值是近年来比较活跃的一个研究课题,涉及Birkhoff三角插值的研究文献也很多(如G.G.Lorentz~([1]),沈燮昌~([2])等综合性文章).     

Lagrange‐type basis for multivariate uniform integrable tensor‐product Birkhoff interpolation

Birkhoff interpolation is the most general interpolation scheme. We study the Lagrange‐type basis for uniform integrable tensor‐product Birkhoff interpolation. We prove that the Lagrange‐type basis of multivariate uniform tensor‐product Birkhoff interpolation can be obtained by multiplying corresponding univariate Lagrange‐type basis when the integrable condition is satisfied. This leads to less computational complexity, which drops to from .     

Approximation order of bivariate spline interpolation for arbitrary smoothness

By using the algorithm of Nürnberger and Riessinger (1995), we construct Hermite interpolation sets for spaces of bivariate splines S_q^r(Δ¹) of arbitrary smoothness defined on the uniform type triangulations. It is shown that our Hermite interpolation method yields optimal approximation order for q 3.5r + 1. In order to prove this, we use the concept of weak interpolation and arguments of Birkhoff interpolation.     

Interpolation by periodic splines with Birkhoff knots

Summary We give a complete characterization of the Hermite interpolation problem by periodic splines with Birkhoff knots. As a dual result we derive the characterization of the Birkhoff interpolation by periodic splines with multiple knots.Sponsored by the Bulgarian Ministry of Education and Science under Contract No. MM-15     

Polynomial algebra for Birkhoff interpolants

We introduce a unifying formulation of a number of related problems which can all be solved using a contour integral formula. Each of these problems requires finding a non-trivial linear combination of possibly some of the values of a function f, and possibly some of its derivatives, at a number of data points. This linear combination is required to have zero value when f is a polynomial of up to a specific degree p. Examples of this type of problem include Lagrange, Hermite and Hermite–Birkhoff interpolation; fixed-denominator rational interpolation; and various numerical quadrature and differentiation formulae. Other applications include the estimation of missing data and root-finding.     

Approximations for node-weighted Steiner tree in unit disk graphs

Given a node-weighted connected graph and a subset of terminals, the problem node-weighted Steiner tree (NWST) seeks a lightest tree connecting a given set of terminals in a node-weighted graph. While NWST in general graphs are as hard as Set Cover, NWST restricted to unit-disk graphs (UDGs) admits constant-approximations. Recently, Zou et al. (Lecture notes in computer science, vol 5165, COCOA, 2008, pp 278–285) showed that any μ-approximation algorithm for the classical edge-weighted Steiner tree problem can be used to produce 2.5 μ-approximation algorithm for NWST restricted to UDGs. With the best known approximation bound 1.55 for the classical Steiner tree problem, they obtained an approximation bound 3.875 for NWST restricted to UDGs. In this paper, we present three approximation algorithms for NWST restricted to UDGs, the k-Restricted Relative Greedy Algorithm whose approximation bound converges to 1 + ln 5 ≈ 2.61 as k → ∞, the 3-Restricted Greedy Algorithm with approximation bound 4\frac13{4\frac{1}{3}} , and the k-Restricted Variable Metric Algorithm whose approximation bound converges to 3.9334 as k → ∞.     

Dynamical recursive algorithms for Lg-spline interpolation of EHB data

Lg-splines find application in many areas of mathematics, physics, and engineering. Especially in the last, there is need for recursive algorithms suitable for real-time application. In this paper we investigate a dynamical structure of the Hilbert space underlying the spline interpolation problem. We use these insights to develop a recursive algorithm for computing Lg-splines interpolating extended Hermite- Birkhoff data. We also investigate the relationship of our algorithm to a basic theorem due to Jerome and Schumaker regarding the smoothness properties of such splines and to algorithms based on their theorem.     

Solvability problems of bivariate interpolation I

This paper is devoted to bivariate interpolation. The problem is to find a polynomialP(x, y) whose values and the values of whose derivatives at given points match given data. Methods of Birkhoff interpolation are used throughout. We define interpolation matricesE, their regularity, their almost regularity, and finally the regularity of the pairE, Z for a given set of knotsZ. Many concrete examples and applications are possible.     

在等距节点处的反周期函数的(0,m_1,m_2,…,m_p)三角插值

研究了以π为周期的反周期函数的Birkhoff三角插值,解决了在等距节点处的反周期函数的(0,m1,m2,…,mp)三角插值问题,得到了解存在的条件.     

Memory‐efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis

Novel memory‐efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so‐called quadratic Arnoldi method and two‐level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift‐and‐invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright © 2013 John Wiley & Sons, Ltd.     

On Birkhoff interpolation by polynomials in several variables

Chui and Lai (1987) have discussed a kind of multivariate polynomial interpolation problem defined on the straight line type node configuration C (SLTNCC). In this paper, we define general Birkhoff interpolation problems for the SLTNCC, and show, under some restrictions, that these interpolation problems are unisolvent. Also we give some generalizations of the SLTNCC.     

A bivariate preprocessing paradigm for the Buchberger-Möller algorithm

For the last almost three decades, since the famous Buchberger-Möller (BM) algorithm emerged, there has been wide interest in vanishing ideals of points and associated interpolation polynomials. Our paradigm is based on the theory of bivariate polynomial interpolation on cartesian point sets that gives us a related degree reducing interpolation monomial and Newton bases directly. Since the bases are involved in the computation process as well as contained in the final output of the BM algorithm, our paradigm obviously simplifies the computation and accelerates the BM process. The experiments show that the paradigm is best suited for the computation over finite prime fields that have many applications.     

Order regularity of two-node Birkhoff interpolation with lacunary polynomials

In this short work we study the existence and uniqueness of solution for some Birkhoff interpolation problems with lacunary polynomials. First we solve the one-node problem; next we solve the two-node problem in the restricted case where one of the nodes is null.     

An error term and uniqueness for Hermite–Birkhoff interpolation involving only function values and/or first derivative values

This paper discusses various aspects of Hermite–Birkhoff interpolation that involve prescribed values of a function and/or its first derivative. An algorithm is given that finds the unique polynomial satisfying the given conditions if it exists. A mean value type error term is developed which illustrates the ill-conditioning present when trying to find a solution to a problem that is close to a problem that does not have a unique solution. The interpolants we consider and the associated error term may be useful in the development of continuous approximations for ordinary differential equations that allow asymptotically correct defect control. Expressions in the algorithm are also useful in determining whether certain specific types of problems have unique solutions. This is useful, for example, in strategies involving approximations to solutions of boundary value problems by collocation.     

B-splines with Birkhoff knots

A natural extension of the Curry-SchoenbergB-splines is given, which preserves such critical properties as variation diminishing and total positivity. Using this tool we give a characterization of the Birkhoff interpolation problem for spline functions.Communicated by Dietrich Braess.