Sparse Polynomial Interpolation With Arbitrary Orthogonal Polynomial Bases
Sparse Polynomial Interpolation With Arbitrary Orthogonal Polynomial Bases
复制标题
任意正交多项式基的稀疏多项式插值
DOI：
10.1145/3208976.3208999
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Yang, Zhengfeng
中科院分区：
文献类型：
--
作者：
Imamoglu, Erdal;Kaltofen, Erich L.;Yang, Zhengfeng
Lakshman Y. N. 和 Saunders 给出了一种从评估点插值多项式 f 的算法，该算法的运行时间取决于多项式表示为具有非零标量系数的第一类 t 个切比雪夫多项式之和时的稀疏性 t。 24，nr。 2（1995）]；卡尔托芬和李 [JSC，卷。 36，nr。 3--4 (2003)] 分析计算稀疏性 t 的随机提前终止版本。这些算法将标准功率基础的普罗尼算法映射到第一类切比雪夫基础。 Arnold 和 Kaltofen 的替代算法 [Proc. ISSAC 2015 年，第二节4] 使用 Prony 的原始算法来计算标准幂项。这里我们给出广义切比雪夫多项式的稀疏插值算法，其中包括第二类、第三类和第四类切比雪夫基。我们的算法也简化为 Prony 的算法。如果在输入上给出稀疏度的边界 B >= t，我们的新算法将准确地从 t + B 评估中恢复第一类、第二类、第三类和第四类切比雪夫表示中的稀疏表示。最后，我们将我们的算法推广到切比雪夫递推具有参数标量的基。我们还展示了如何计算那些优化相应基础中表示的稀疏性的参数值，类似于计算最稀疏移位。
An algorithm for interpolating a polynomial f from evaluation points whose running time depends on the sparsity t of the polynomial when it is represented as a sum of t Chebyshev Polynomials of the First Kind with non-zero scalar coefficients is given by Lakshman Y. N. and Saunders [SIAM J. Comput., vol. 24, nr. 2 (1995)]; Kaltofen and Lee [JSC, vol. 36, nr. 3--4 (2003)] analyze a randomized early termination version which computes the sparsity t. Those algorithms mirror Prony's algorithm for the standard power basis to the Chebyshev Basis of the First Kind. An alternate algorithm by Arnold's and Kaltofen's [Proc. ISSAC 2015, Sec. 4] uses Prony's original algorithm for standard power terms. Here we give sparse interpolation algorithms for generalized Chebyshev polynomials, which include the Chebyshev Bases of the Second, Third and Fourth Kind. Our algorithms also reduce to Prony's algorithm. If given on input a bound B >= t for the sparsity, our new algorithms deterministically recover the sparse representation in the First, Second, Third and Fourth Kind Chebyshev representation from exactly t + B evaluations. Finally, we generalize our algorithms to bases whose Chebyshev recurrences have parametric scalars. We also show how to compute those parameter values which optimize the sparsity of the representation in the corresponding basis, similar to computing a sparsest shift.
DOI：
10.1016/s0747-7171(85)80029-8
发表时间：
1985-03
期刊：
J. Symb. Comput.
影响因子：
--
作者：
E. Kaltofen
通讯作者：
E. Kaltofen