McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome.
DATE: Friday, November 27th, 1998
TIME: 11:00-12:00
PLACE: McConnell 320
TITLE: A Deterministic Multivariate Interpolation Algorithm via Generalized Vandermonde Matrix Nullspaces
SPEAKER: Zeljko Zilic, McGill University
We consider the multivariate polynomial interpolation over a field. In the univariate case, the Lagrange or Newton algorithm produces a polynomial with at most t lowest degree terms fitting a function at arbitrary t points. In the multivariate case, as the problem is harder, mostly the restricted classes of problems have been considered, such as the "black box" interpolations by which the algorithm chooses the points freely.

In this talk, we present an interpolation algorithm which preserves many good properties of univariate interpolations. Given function values at arbitrary t points, we obtain in deterministic polynomial time the interpolating polynomial with at most t terms. Relative to the univariate interpolation, only the minimal degree selection of terms cannot be guaranteed.

The algorithm uses the structure of the multivariate generalized Vandermonde matrix associated with the problem to find the terms of the interpolating polynomial. Since there is no known characterization of this matrix, the algorithm uses its nullspaces to find a term that increases the rank of the matrix by one. There is at most t such steps; each step obtains the matrix nullspaces and in O(t) time finds the term.

Our construction is especially useful for interpolations over small finite fields, where it was first applied. We show that the problem can be decomposed into smaller problems over subspaces of GF(q)n, and solved in a subspace inclusion partial order. In the binary case, the decomposition alone produces the quadratic time interpolation algorithm.

We applied the algorithm in the logic synthesis and analysis of Boolean and discrete functions via Reed-Muller transform. We outline the incremental and parallel interpolation algorithms, as well as the use of shifted polynomials in such interpolations.

This is a joint seminar with the Department of Electrical and Computer Engineering.
This information is available at http://cgm.cs.mcgill.ca/~therese/seminar.
Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to Therese Biedl at therese@cgm.cs.mcgill.ca.