The Birkhoff Interpolation Problem

F. Rouillier, M. Safey El Din, É. Schost

F. Rouillier : LORIA INRIA-Lorraine, Nancy, France
É. Schost : Laboratoire GAGE, École polytechnique, Palaiseau, France.

Abstract: Following the work of Gonzalez-Vega [3], we show how to use recent algorithmic tools of computational real algebraic geometry to solve the Birkhoff Interpolation Problem originally given in [6] and [1]. These algorithms are used to solve the Birkhoff Interpolation Problem in a case which is presented as an open problem in [4]. The solution is available here.

Download the paper : here (submitted to Proceedings of ADG'2000)
Download the solutions : here (under the form of poised matrices, see below, in Maple format)
Download the singular hypersurfaces : here

In the following Q denotes the field of rationals, R is the field of real numbers, and C the field of complex numbers.

1 The Problem

The problem of interpolating a function f:R¾®R by a univariate polynomial from the values of f and some of its derivatives on a set of sample points is one of the main questions in Numerical Analysis and Approximation Theory.

Let c={x₁, ..., x_n} be a set of real numbers such that x₁ < ... < x_n, r an integer, and let IÌ {1,...,n}× {0,...,r} be the set of pairs (i,j) such that the value f_i_,j=f^(j)(x_i) is known. The problem of determining the existence and uniqueness of a polynomial Q in R[X] of degree bounded by r such that :

" (i,j)ÎI Q^(j)(x_i)=f_i_,j is called the Birkhoff Interpolation Problem.

In [3], Gonzalez-Vega focuses on determining, for fixed integers n and r, the family of I's for which this question is solvable for any choice of c and the values f_i_,j. To this end, he shows that the problem can be reduced to decide if some hypersurfaces contain real points with non null coordinates. In [3] the cases n=2, rÎ {1,2,3,4,5,6}, n=3, rÎ {1,2,3} and n=4, rÎ{1,2,3,4} are solved, using techniques adapted from the Cylindrical Algebraic Decomposition. In 1998, the case n=5 and r=4 is presented as an open problem in [4].

We follow closely [3], and adopt his convenient matricial formulation.

Consider the matrix E= ( e_i_,j) with n lines and r+1 columns [3], filled with 0's and 1's, such that e_i_,j=1 if and only if (i,j)ÎI. The problem admits a solution only if E has as many 1's as columns. This amounts to saying that the coefficients of the interpolating polynomial Q are solution of a linear square system, with associated matrix M_E. This matrix is parametrized by c and its shape depends on E. We are interested in determining the matrices E for which the determinant of M_E is non-zero for all c, in which case the matrix E is said to be poised. We give the list of poised matrices in the case n=5 and r=4, here, in Maple format.
Example 1 Let n=4 and r=3 and consider the matrix:

æ
ç
ç
è

1	1	0
0	0	1
0	1	0

ö
÷
÷
ø

Let Q(x)=a₀+a₁ x +a₂ x² + a₃ x³ be the generic polynomial of degree 3. Writing Q^(j)(x_i)=f_i,j if and only if e_i,j=1, we obtain the following linear system:

ì
ï
í
ï
î

a₀+a₁ x₁ +a₂ x₁² + a₃ x₁³ = f_1,1

a₁ + 2 a₂ x₁ + 3 a₃ x₁² = f_1,2

a₁ + 2 a₂ x₃ + 3 a₃ x₃² = f_3,2

2 a₂ + 6 a₃ x₂ = f_3,2

whose matrix is:

æ
ç
ç
ç
è

1	x₁	x₁²	x₁³
0	1	2x₁	3x₁²
0	1	2x₃	3x₃²
0	0	2	6x₂

ö
÷
÷
÷
ø

The interpolation problem is solvable if and only if 12 x₃ x₂+6x₁²-12x₂ x₁-6x₃² does not vanish for all values x₁, x₂ , x₃ satisfying x₁ < x₂ < x₃.

In [3], Gonzalez-Vega shows that the question can be reduced to test if a particular factor of the determinant of the matrix M_E has real roots with non zero coordinates. Replacing (x₁, ..., x_n) by (x₁, x₁+t₁²,..., x₁+t₁²+...+t_n_-1²) yields a homogeneous polynomial in (t₁,...,t_n_-1). Letting t₁=1, we are brought to test if a hypersurface defined by a polynomial P ÎR[t₂, ..., t_n_-1] has real roots with non zero coordinates.

2 The Resolution

In order to determine all the poised matrices in the case n=5 and r=4, we have to study quasi-algebraic sets defined by a unique equation in R[t₂, t₃, t₄] and several inequations.

Given a polynomial P in Q[t₂,t₃,t₄], we adopt the following scheme.

First step.

We study the hypersurface defined by P=0, using either the algorithms described in [6] or [1]. If this subroutine returns no real point, or a real point with non zero coordinates, we can give a positive (resp. negative) answer to the Interpolation Problem.

Second step.

If we are in the case when all the obtained real points have at least one null coordinate, one could study the polynomial system P=0 and Tt₁ t₂t₃-1=0.

3 The Solutions

All the computations have been perfomed on the computers of the UMS MEDICIS.

3.1 Used softwares

Gb/AGb : implemented in C++ by J.-C. Faugère and devoted to Gröbner basis computations;
RS : implemented in C by F. Rouillier, devoted to computing Rational Univariate Representations (see [5]), and to counting and isolating real roots of univariate polynomials (see [7]);
Kronecker : implemented in Magma by G. Lecerf [2], devoted to compute Geometric Resolutions, from which we borrowed the formal Newton iterator.

A subroutine performing a radical equi-dimensional decompoisiton was also implemented using Maple and a file connection with Gb (see [8]).

3.2 Results

The case n=5, r=4 of Birkhoff's problem generates 53130 matrices, which produces as many hypersurfaces of C³ to study.

42925 of these hypersurfaces are defined by constant polynomials.
For the non-constant polynomials, to avoid unnecessary computations, we specialized all variables but one at random non-zero values and applied Uspensky's algorithm on the univariate polynomials we obtained, looking for non-zero real roots. At the end of this preprocessing, about one thousand hypersurfaces remained to study.
About 900 of these hypersurfaces had zero or a finite number of singularities.

There remained 102 hypersurfaces containing an infinity of singularities. You can download these singular hypersurfaces here

As a conclusion, 19092 out of the 53130 matrices are poised. Their complete list can be found here (in Maple format).

References

[1]: P. Aubry, F. Rouillier, M. Safey El Din,Real Solving for positive dimensional systems, Rapport de Recherche du Laboratoire d'Informatique de Paris VI, Mars 2000.
[2]: M. Giusti, G. Lecerf, B. Salvy, A Gröbner free alternative for solving polynomial systems, Journal of Complexity, 2000.
[3]: L. Gonzalez-Vega, Applying quantifier elimination to the Birkhoff Interpolation Problem, Journal of Symbolic Computation, 1996.
[4]: M.-J. Gonzalez-Lopez and L. Gonzalez-Vega, Project 2 : The Birkhoff Interpolation Problem, In: Some tapas of computer algebra, A. Cohen ed. Springer, 297-310, (1999).
[5]: F. Rouillier,Solving Zero-Dimensional Systems through the Rational Univariate Representation, AAECC Journal.9 : 433-461 (1999).
[6]: F. Rouillier, M.-F. Roy, M. Safey El Din,Finding at least one point in each connected component of a real algebraic set defined by a single equation, to appear in Journal of Complexity, 1999.
[7]: F. Rouillier, P. Zimmermann,Uspensky's algorithm : improvements and applications, in preparation (2000).
[8]: M. Safey El Din, Résolution réelle des systèmes polynomiaux en dimension positive, Doctoral thesis, in preparation, University Paris VI.
[9]: É. Schost, Computing parametric geometric resolutions, preprint École polytechnique, January 2000.
[10]: É. Schost, Sur la résolution des systèmes polynomiaux à paramètres, Doctoral thesis École polytechnique, 2000.

This document was translated from L^AT_EX by H^EV^EA.