
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 19851989  Copyright 19851989 Universität Bonn, Institut für Informatik, 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
English 
Universität Bonn > Institut für Informatik > Abteilung V 