Computational Complexity of Sparse Rational Interpolation
Title | Computational Complexity of Sparse Rational Interpolation |
Publication Type | Technical Report |
Year of Publication | 1991 |
Authors | Grigoriev, D. Yu., Karpinski M., & Singer M. F. |
Other Numbers | 648 |
Keywords | Algorithms, Arithmetic Complexity, Computational Complexity, Sparse Rational Interpolation |
Abstract | We analyze the computational complexity of sparse rational interpolation, and give the first genuine time (arithmetic complexity does not depend on the size of the coefficients) algorithm for this problem. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1991/tr-91-018.pdf |
Bibliographic Notes | ICSI Technical Report TR-91-018 |
Abbreviated Authors | D. Grigoriev, M. Karpinski, and M. F. Singer |
ICSI Publication Type | Technical Report |