On feasible multivariate polynomial interpolations over arbitrary fields
Željko Žilić, Katarzyna Radecka · 1999
In th,is paper, we consider a problem of interpolating a multivariate polynomial from its values at arbitrary t points ouf:r a field F. We derive a deterministic algorithm that finds an interpolating polynomial with at most t terms.Relative to the univariate inteq&otzon, minimal degree selection of terms and wxiqw:ness cannot be gualonteed.Our construction uses the nullspaces of th,e mlrltivnriate genwralized Vanderm.ondematrix associated ,with.the problem to make this mutrk nonsingulw in u series of stepas.Th.e strwtwe of this matrix ullows us to deterministicully find the terms thet increase the rank of this matrix.We pl'esent u pwctical algorithm for finite field interpolations, togeth,er with a set of heuristics for obtairhg fast CL small-de,gree interpolation polynomial.As a special case of interpolation a1gori.th.m. we propose the qlLadratic time algorithm for interpolation over GF(2) field.