arXiv Open Access 2017

Sparse Rational Function Interpolation with Finitely Many Values for the Coefficients

Qiao-Long Huang Xiao-Shan Gao

Lihat Sumber

Abstrak

In this paper, we give new sparse interpolation algorithms for black box univariate and multivariate rational functions h=f/g whose coefficients are integers with an upper bound. The main idea is as follows: choose a proper integer beta and let h(beta) = a/b with gcd(a,b)=1. Then f and g can be computed by solving the polynomial interpolation problems f(beta)=ka and g(beta)=ka for some integer k. It is shown that the univariate interpolation algorithm is almost optimal and multivariate interpolation algorithm has low complexity in T but the data size is exponential in n.

Topik & Kata Kunci

cs.SC

Penulis (2)

Qiao-Long Huang

Xiao-Shan Gao

Format Sitasi

APA MLA BibTeX

Huang, Q., Gao, X. (2017). Sparse Rational Function Interpolation with Finitely Many Values for the Coefficients. https://arxiv.org/abs/1706.00914

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓