Department of Computer Science
Chair V

University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V


The Interpolation Problem for k-Sparse Sums of Eigenfunctions of Operators
Dima Grigoriev, Marek Karpinski and Miachel Singer
[Download PostScript] [Download PDF]

In [DG 89], the authors show that many results concerning the problem of efficient interpolation of k-sparse multivariate polynomials can be formulated and proved in the general setting of k-sparse sums of characters of abelian monoids. In this note we describe another conceptual framework for the interpolation problem. In this framework, we consider R-algebras of functions A1,...,An on integral domain R, together with R-linear operators Di: AiAi. We then consider functions f from Rn to R that can be expressed as the sum of k terms, each term being an R-multiple of an n-fold product f1(x1)⋅...⋅fn(xn) where each fi is an eigenfunction for Di. We show how these functions can be thought of as k-sums of characters on an associated abelian monoid. This allows one to use the results of [DG 89] to solve interpolation problems for k-sparse sums of functions which, at first glance, do not seem to be characters.

Last Change: 12/10/08 at 16:58:49
University of Bonn -> Department of Computer Science -> Chair V