APPLYING QUANTIFIER ELIMINATION TO THE BIRKHOFF INTERPOLATION PROBLEM

This paper is devoted to show how to use Computer Algebra and Quantifi er Elimination to solve some particular instances of the Birkhoff Inte rpolation Problem. In particular, this problem is completely solved fo r degrees less than or equal to 3 and any number of nodes and several instances of degree 4 and 5 by computing all the incidence normal pois ed matrices with such characteristics. The used Computer Algebra and Q uantifier Elimination includes manipulation of multivariate polynomial s, computation of determinants of matrices with polynomial entries and the formal manipulation of univariate polynomial inequalities by usin g Sturm-Habicht sequences and the Sign Determination Scheme. (C) 1996 Academic Press Limited