报告主题：用切比雪夫基计算带纠错的稀疏插值

报告人： Erich Kaltofen 教授 （美国北卡罗琳娜大学数学系）

报告时间：2018年 6月8日（周五）10:00

报告地点：校本部G507

邀请人：曾振柄

主办部门：理学院数学系

报告摘要：We present an error-correcting interpolation algorithm for a univariate black-box polynomial that has a sparse representation using Chebyshev polynomials as a term basis. Our algorithm assumes that an upper bound on the number of erroneous evaluations is given as input. Our method is a generalization of the algorithm by Lakshman and Saunders [SIAM J. Comput., vol. 24 (1995)] for interpolating sparse Chebyshev polynomials, as well as techniques in error-correcting sparse interpolation in the usual basis of consecutive powers of the variable due to Comer, Kaltofen, and Pernet [Proc. ISSAC 2012, 2014]. We prove the correctness of our list-decoder-based algorithm with a Descartes-rule-of-signs-like property for sparse polynomials in the Chebyshev basis. We show that this list decoder requires fewer evaluations than a naïve majority-rule block decoder in the case when the interpolant is known to have at most two terms. We also give a new algorithm that reduces sparse interpolation in the Chebyshev basis to that in the power basis, thus making the many techniques for the sparse interpolation in the power basis, for instance, supersparse (lacunary) interpolation over large finite fields, available to interpolation in the Chebyshev basis. Furthermore, we can customize the randomized early termination algorithms from Kaltofen and Lee [J. Symb. Comput., vol. 36 (2003)] to our new approach.

欢迎教师、学生参加 ！