@article{imamoglu_kaltofen_yang_2018, title={Sparse Polynomial Interpolation With Arbitrary Orthogonal Polynomial Bases}, DOI={10.1145/3208976.3208999}, abstractNote={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.}, journal={ISSAC'18: PROCEEDINGS OF THE 2018 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION}, author={Imamoglu, Erdal and Kaltofen, Erich L. and Yang, Zhengfeng}, year={2018}, pages={223–230} }
 @article{kaltofen_may_yang_zhi_2008, title={Approximate factorization of multivariate polynomials using singular value decomposition}, volume={43}, ISSN={["0747-7171"]}, DOI={10.1016/j.jsc.2007.11.005}, abstractNote={We describe the design, implementation and experimental evaluation of new algorithms for computing the approximate factorization of multivariate polynomials with complex coefficients that contain numerical noise. Our algorithms are based on a generalization of the differential forms introduced by W. Ruppert and S. Gao to many variables, and use singular value decomposition or structured total least squares approximation and Gauss–Newton optimization to numerically compute the approximate multivariate factors. We demonstrate on a large set of benchmark polynomials that our algorithms efficiently yield approximate factorizations within the coefficient noise even when the relative error in the input is substantial (10−3).}, number={5}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Kaltofen, Erich and May, John P. and Yang, Zhengfeng and Zhi, Lihong}, year={2008}, month={May}, pages={359–376} }
 @inproceedings{kaltofen_yang_2007, title={On exact and approximate interpolation of sparse rational functions}, ISBN={9781595937438}, DOI={10.1145/1277548.1277577}, abstractNote={The black box algorithm for separating the numerator from the denominator of a multivariate rational function can be combined with sparse multivariate polynomial interpolation algorithms to interpolate a sparse rational function. domization and early termination strategies are exploited to minimize the number of black box evaluations. In addition, rational number coefficients are recovered from modular images by rational vector recovery. The need for separate numerator and denominator size bounds is avoided via correction, and the modulus is minimized by use of lattice basis reduction, a process that can be applied to sparse rational function vector recovery itself. Finally, one can deploy sparse rational function interpolation algorithm in the hybrid symbolic-numeric setting when the black box for the function returns real and complex values with noise. We present and analyze five new algorithms for the above problems and demonstrate their effectiveness on a mark implementation.}, booktitle={ISSAC 2007: International Symposium for Symbolic and Algebraic Computation: Proceedings}, publisher={New York: ACM Press}, author={Kaltofen, E. and Yang, Z.-F.}, year={2007} }
 @inproceedings{kaltofen_yang_zhi_2007, title={On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms}, ISBN={9781595937445}, booktitle={International Workshop on Symbolic-Numeric Computation: Proceedings}, publisher={New York: ACM Press}, author={Kaltofen, E. and Yang, Z.-F. and Zhi, L.-H.}, year={2007} }