A fast algorithm for multivariate Hermite interpolation

Multivariate Hermite interpolation is widely applied in many fields, such as finite element construction, inverse engineering, CAD etc.. For arbitrarily given Hermite interpolation conditions, the typical method is to compute the vanishing ideal I （the set of polynomials satisfying all the homogeneous interpolation conditions are zero） and then use a complete residue system modulo I as the interpolation basis. Thus the interpolation problem can be converted into solving a linear equation system. A generic algorithm was presented in [18], which is a generalization of BM algorithm [22] and the complexity is O（τ^3） where r represents the number of the interpolation conditions. In this paper we derive a method to obtain the residue system directly from the relative position of the points and the corresponding derivative conditions （presented by lower sets） and then use fast GEPP to solve the linear system with O（（τ ＋ 3）τ^2） operations, where τ is the displacement-rank of the coefficient matrix. In the best case τ = 1 and in the worst case τ = [τ/n], where n is the number of variables.     

Bases for Splines on a Subdivided Domain

Let S^r() be the module of all splines of smoothness r on the rectilinear partition which subdivides some domain D. Further, let S^r() be the module of all splines of smoothness r on which also subdivides D, where is a finer subdivision of . We study the relationship between a generating set of S^r() and a generating set for S^r(). This paper gives an algorithm for extending a generating set for S^r() to one for for S^r(). This method is built on algebraic properties of splines and the Gröbner Basis Algorithm.     

Gröbner-Shirshov basis of the Adyan extension of the Novikov group

The goal of this paper is to give a comparatively short and simple analysis of the Adyan origional group constraction (S.I. Adyan, Unsolvability of some algorithmic problems in the theory of groups, Trudy MMO 6 (1957) 231-298).     

The Neville-like form of the Fitzpatrick algorithm for rational interpolation

The Fitzpatrick algorithm, which seeks a Gr?bner basis for the solution of a system of polynomial congruences, can be applied to compute a rational interpolant. Based on the Fitzpatrick algorithm and the properties of an Hermite interpolation basis, we present a Neville-like algorithm for multivariate osculatory rational interpolation. It may be used to compute the values of osculatory rational interpolants at some points directly without computing the rational interpolation function explicitly.     

An algebraic geometry algorithm for scheduling in presence of setups and correlated demands

We study here a problem of schedulingn job types onm parallel machines, when setups are required and the demands for the products are correlated random variables. We model this problem as a chance constrained integer program.Methods of solution currently available—in integer programming and stochastic programming—are not sufficient to solve this model exactly. We develop and introduce here a new approach, based on a geometric interpretation of some recent results in Gröbner basis theory, to provide a solution method applicable to a general class of chance constrained integer programming problems.Out algorithm is conceptually simple and easy to implement. Starting from a (possibly) infeasible solution, we move from one lattice point to another in a monotone manner regularly querying a membership oracle for feasibility until the optimal solution is found. We illustrate this methodology by solving a problem based on a real system.Corresponding author.     

Homological Computations in PBW Modules

In this paper the Poincaré–Birkhoff–Witt (PBW) rings are characterized. Gröbner bases techniques are also developed for these rings. An explicit presentation of Ext ⁱ (M,N) is provided when N is a centralizing bimodule.     

Eigenvalue problems to compute almost optimal points for rational interpolation with prescribed poles

Explicit formulas exist for the (n,m) rational function with monic numerator and prescribed poles that has the smallest possible Chebyshev norm. In this paper we derive two different eigenvalue problems to obtain the zeros of this extremal function. The first one is an ordinary tridiagonal eigenvalue problem based on a representation in terms of Chebyshev polynomials. The second is a generalised tridiagonal eigenvalue problem which we derive using a connection with orthogonal rational functions. In the polynomial case (m = 0) both problems reduce to the tridiagonal eigenvalue problem associated with the Chebyshev polynomials of the first kind. Postdoctoral researcher FWO-Flanders.     

Bivariate composite vector valued rational interpolation

In this paper we point out that bivariate vector valued rational interpolants (BVRI) have much to do with the vector-grid to be interpolated. When a vector-grid is well-defined, one can directly design an algorithm to compute the BVRI. However, the algorithm no longer works if a vector-grid is ill-defined. Taking the policy of ``divide and conquer', we define a kind of bivariate composite vector valued rational interpolant and establish the corresponding algorithm. A numerical example shows our algorithm still works even if a vector-grid is ill-defined.

     

A Krylov subspace algorithm for multiquadric interpolation in many dimensions

We consider the version of multiquadric interpolation wherethe interpolation conditions are the equations s(x_i) = f_i, i= 1,2,..., n, and where the interpolant has the form s(x) =_j=1ⁿ _j (||x – x_j ||² + c²)^1/2 + x R^d, subject to theconstraint _j=1ⁿ _j = 0. The points x_i R^d, the right-hand sidesf_i, i = 1,2,...,n, and the constant c are data. The equationsand the constraint define the parameters _j, j = 1,2,...,n, and. The resultant approximation s f is useful in many applications,but the calculation of the parameters by direct methods requiresO (n³) operations, and n may be large. Therefore iterative proceduresfor this calculation have been studied at Cambridge since 1993,the main task of each iteration being the computation of s(x_i),i = 1,2,...,n, for trial values of the required parameters.These procedures are based on approximations to Lagrange functions,and often they perform very well. For example, ten iterationsusually provide enough accuracy in the case d = 2 and c = 0,for general positions of the data points, but the efficiencydeteriorates if d and c are increased. Convergence can be guaranteedby the inclusion of a Krylov subspace technique that employsthe native semi-norm of multiquadric functions. An algorithmof this kind is specified, its convergence is proved, and carefulattention is given to the choice of the operator that definesthe Krylov subspace, which is analogous to pre-conditioningin the conjugate gradient method. Finally, some numerical resultsare presented and discussed, for values of d and n from theintervals [2,40] and [200,10 000], respectively.     

On some aspects of multivariate polynomial interpolation

The purpose of this paper is to present some aspects of multivariate Hermite polynomial interpolation. We do not focus on algebraic considerations, combinatoric and geometric aspects, but on explicitation of formulas for uniform and non-uniform bivariate interpolation and some higher dimensional problems. The concepts of similar and equivalent interpolation schemes are introduced and some differential aspects related to them are also investigated. This revised version was published online in June 2006 with corrections to the Cover Date.     

Rational radial basis function interpolation with applications to antenna design

Functions with poles occur in many branches of applied mathematics which involve resonance phenomena. Such functions are challenging to interpolate, in particular in higher dimensions. In this paper we develop a technique for interpolation with quotients of two radial basis function (RBF) expansions to approximate such functions as an alternative to rational approximation. Since the quotient is not uniquely determined we introduce an additional constraint, the sum of the RBF-norms of the numerator and denominator squared should be minimal subjected to a norm condition on the function values. The method was designed for antenna design applications and we show by examples that the scattering matrix for a patch antenna as a function of some design parameters can be approximated accurately with the new method. In many cases, e.g. in antenna optimization, the function evaluations are time consuming, and therefore it is important to reduce the number of evaluations but still obtain a good approximation. A sensitivity analysis of the new interpolation technique is carried out and it gives indications how efficient adaptation methods could be devised. A family of such methods are evaluated on antenna data and the results show that much performance can be gained by choosing the right method.     

Gröbner Bases for Complete Uniform Families

We describe (reduced) Gröbner bases of the ideal of polynomials over a field, which vanish on the set of characterisic vectors of the complete unifom families . An interesting feature of the results is that they are largely independent of the monomial order selected. The bases depend only on the ordering of the variables. We can thus use past results related to the lex order in the presence of degree-compatible orders, such as deglex. As applications, we give simple proofs of some known results on incidence matrices.     

Bayesian networks for discrete multivariate data: an algebraic approach to inference

In this paper we demonstrate how Gröbner bases and other algebraic techniques can be used to explore the geometry of the probability space of Bayesian networks with hidden variables. These techniques employ a parametrisation of Bayesian network by moments rather than conditional probabilities. We show that whilst Gröbner bases help to explain the local geometry of these spaces a complimentary analysis, modelling the positivity of probabilities, enhances and completes the geometrical picture. We report some recent geometrical results in this area and discuss a possible general methodology for the analyses of such problems.     

A new approach to vector-valued rational interpolation

In this work we propose three different procedures for vector-valued rational interpolation of a function F(z), where , and develop algorithms for constructing the resulting rational functions. We show that these procedures also cover the general case in which some or all points of interpolation coalesce. In particular, we show that, when all the points of interpolation collapse to the same point, the procedures reduce to those presented and analyzed in an earlier paper (J. Approx. Theory 77 (1994) 89) by the author, for vector-valued rational approximations from Maclaurin series of F(z). Determinant representations for the relevant interpolants are also derived.     

A weighted bivariate blending rational interpolation based on function values

This paper presents a new weighted bivariate blending rational spline interpolation based on function values. This spline interpolation has the following advantages: firstly, it can modify the shape of the interpolating surface by changing the parameters under the condition that the values of the interpolating nodes are fixed; secondly, the interpolating function is C¹-continuous for any positive parameters; thirdly, the interpolating function has a simple and explicit mathematical representation; fourthly, the interpolating function only depends on the values of the function being interpolated, so the computation is simple. In addition, this paper discusses some properties of the interpolating function, such as the bases of the interpolating function, the matrix representation, the bounded property, the error between the interpolating function and the function being interpolated.     

A Newton type rational interpolation formula

We give a Newton type rational interpolation formula (Theorem 2.2). It contains as a special case the original Newton interpolation, as well as the interpolation formula of Liu, which allows to recover many important classical q-series identities. We show in particular that some bibasic identities are a consequence of our formula.     

A new algorithm for osculatory rational interpolation

Summary A new algorithm is derived for computing continued fractions whose convergents form the elements of the osculatory rational interpolation table.