DocumentCode :
2787896
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
fYear :
1990
fDate :
22-24 Oct 1990
Firstpage :
8409
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
Type :
conf
DOI :
10.1109/FSCS.1990.89616
Filename :
89616
Link To Document :
بازگشت