zbMATH — the first resource for mathematics

Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases. (English) Zbl 1074.68078
Summary: We give a new class of algorithms for computing sparsest shifts of a given polynomial. Our algorithms are based on the early termination version of sparse interpolation algorithms: For a symbolic set of interpolation points, a sparsest shift must be a root of the first possible zero discrepancy that can be used as the early termination test. Through reformulating as multivariate shifts in a designated set, our algorithms can compute the sparsest shifts that simultaneously minimize the terms of a given set of polynomials. Our algorithms can also be applied to the Pochhammer and Chebyshev bases for the polynomials, and potentially to other bases as well. For a given univariate polynomial, we give a lower bound for the optimal sparsity. The efficiency of our algorithms can be further improved by imposing such a bound and pruning the highest degree terms.

68W30 Symbolic computation and algebraic computation
13P05 Polynomials, factorization in commutative rings
Full Text: DOI
[1] Ben-Or, M.; Tiwari, P., A deterministic algorithm for sparse multivariate polynomial interpolation, (), 301-309
[2] Brent, R.P.; Gustavson, F.G.; Yun, D.Y.Y., Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. algorithms, 1, 259-295, (1980) · Zbl 0475.65018
[3] DeMillo, R.A.; Lipton, R.J., A probabilistic remark on algebraic program testing, Inform. process. lett., 7, 4, 193-195, (1978) · Zbl 0397.68011
[4] Dı́az, A.; Kaltofen, E., Foxbox a system for manipulating symbolic objects in black box representation, (), 30-37 · Zbl 0918.68049
[5] Evans, R.J.; Isaacs, I.M., Generalized Vandermonde determinants and roots of unity of prime order, Proc. amer. math. soc., 58, 51-54, (1976) · Zbl 0337.12006
[6] Giesbrecht, M.; Kaltofen, E.; Lee, W.-s., Algorithms for computing the sparsest shifts for polynomials via the berlekamp/Massey algorithm, (), 101-108 · Zbl 1072.68669
[7] Grigoriev, D.Y.; Karpinski, M., A zero-test and an interpolation algorithm for the shifted sparse polynomials, (), 162-169 · Zbl 0809.68072
[8] Grigoriev, D.Y.; Karpinski, M.; Singer, M.F., Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM J. comput., 19, 6, 1059-1063, (1990) · Zbl 0711.68059
[9] Grigoriev, D.Y.; Karpinski, M.; Singer, M.F., Computational complexity of sparse rational function interpolation, SIAM J. comput., 23, 1-11, (1994) · Zbl 0802.68060
[10] Grigoriev, D.Y.; Lakshman, Y.N., Algorithms for computing sparse shifts for multivariate polynomials, (), 96-103 · Zbl 0924.68105
[11] Grigoriev, D.Y.; Lakshman, Y.N., Algorithms for computing sparse shifts for multivariate polynomials, Appl. algebra engrg. comm. comput., 11, 1, 43-67, (2000) · Zbl 0968.68199
[12] Kaltofen, E., Lee, W.-s., 2003. Early termination in sparse interpolation algorithms. J. Symbolic Comput., 40. In the special issues on papers of the 2003 Internat. Symp. Symbolic Algebraic Comput. (2003) (doi: 10.1016/S0747-7171(03)00088-9) · Zbl 1074.68080
[13] Kaltofen, E.; Lee, W.-s.; Lobo, A.A., Early termination in ben-or/tiwari sparse interpolation and a hybrid of zippel’s algorithm, (), 192-201 · Zbl 1326.68358
[14] Kaltofen, E.; Trager, B., Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, J. symbolic comput., 9, 3, 301-320, (1990) · Zbl 0712.12001
[15] Knuth, D.E., Mathematics for the analysis of algorithms, (1983), Birkhäuser
[16] Knuth, D.E., Seminumerical algorithms, () · Zbl 0191.17903
[17] Lakshman, Y.N.; Saunders, B.D., Sparse shifts for univariate polynomials, Appl. algebra engrg. comm. comput., 7, 5, 364, (1996) · Zbl 0953.12006
[18] Rosser, J.B.; Schoenfeld, L., Approximate formulas for some functions of prime numbers, Ill. J. math., 6, 64-94, (1962) · Zbl 0122.05001
[19] Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 701-717, (1980) · Zbl 0452.68050
[20] Zippel, R., Probabilistic algorithms for sparse polynomials, (), 216-226
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.