Title :
Interpolation of sparse rational functions without knowing bounds on exponents
Author :
Grigoriev, Dima Yu ; Karpinski, Marek ; Singer, Michael F.
Author_Institution :
Steklov Inst. of Math., Acad. of Sci., Lenningrad, USSR
Abstract :
The authors present the first algorithm for the (black box) interpolation of t-sparse, n-variate, rational functions without knowing bounds on exponents of their sparse representation, with the number of queries independent of exponents. In fact, the algorithm uses O(ntt) queries to the black box, and it can be implemented for a fixed t in a polynomially bounded storage (or polynomial parallel time)
Keywords :
computational complexity; function approximation; interpolation; black box; interpolation; polynomial parallel time; polynomially bounded storage; queries; sparse rational functions; sparse representation; Computer science; Concurrent computing; Interpolation; Mathematics; Polynomials;
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
DOI :
10.1109/FSCS.1990.89616