»ã±¨Ö÷Ì⣺ÓÃÇбÈÑ©·ò»ùÍÆËã´ø¾À´íµÄÏ¡ÉÙ²åÖµ

»ã±¨ÈË£º 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.

Ó­½ÓÀÏʦ¡¢Ñ§Éú²ÎÓë £¡