
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 University of Bonn, Department of Computer Science, Abt. V  
8538 10.12.2008 
The Interpolation Problem for kSparse 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 ksparse multivariate polynomials can be formulated and proved in the general setting of ksparse sums of characters of abelian monoids. In this note we describe another conceptual framework for the interpolation problem. In this framework, we consider Ralgebras of functions A_{1},...,A_{n} on integral domain R, together with Rlinear operators D_{i}: A_{i} → A_{i}. We then consider functions f from R^{n} to R that can be expressed as the sum of k terms, each term being an Rmultiple of an nfold product f_{1}(x_{1})⋅...⋅f_{n}(x_{n}) where each f_{i} is an eigenfunction for D_{i}. We show how these functions can be thought of as ksums of characters on an associated abelian monoid. This allows one to use the results of [DG 89] to solve interpolation problems for ksparse sums of functions which, at first glance, do not seem to be characters. 

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