×

Sparse shifts for univariate polynomials. (English) Zbl 0953.12006

Appl. Algebra Eng. Commun. Comput. 7, No. 5, 351-364 (1996); erratum ibid. 7, No. 6, 561-562 (1996).
A \(t\)-sparse shift for a polynomial \(f(x)\) over the rationals with degree greater than or equal to \(t\) is an algebraic number \(\alpha\) such that \(f(x)= \sum a_i (x- \alpha)^i\) with at most \(t\) of the coefficients \(a_i\) nonzero.
The authors develop some condition on the uniqueness and rationality of the \(t\)-sparse shift and an algorithm for computing a sparse shift for a given polynomial. In addition, a criterion is given for distinguishing two polynomials which are sparse with respect to bounded shifts together with a description of a polynomial time algorithm for computing sparse decomposition of univariate polynomials.

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
68W30 Symbolic computation and algebraic computation
65H05 Numerical computation of solutions to single equations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ben Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynomial interpolation. Proc. 20th Symp. Theory Comput. ACM Press, pp. 301-309 (1988)
[2] Borodin, A., Tiwari, P.: On the decidability of sparse univariate polynomial interpolation. Proc. 22nd Symp. Theory Comput. ACM Press, pp. 535-545 (1990)
[3] Fried, M. D., MacRae, R. E.: On the invariance of chains of fields. Ill. J. Math.,13, 165-171 (1969) · Zbl 0174.07302
[4] von zur Gathen, J., Kozen, D., Landau, S.: Functional decomposition of polynomials. Proc. 28th IEEE Symp. Found. Comp. Sci., pp. 127-131. Nov 1987
[5] Clausen, M., Dress, A., Grabmeier, J., Karpinski, M: On zero testing and interpolation ofk-sparse multivariate polynomials over finite fields. TR 88.06.006, IBM Germany, Heidelberg Scientific Center. June 1988 · Zbl 0737.65002
[6] Grigoriev, D. Yu., Karpinski, M.: The matching problem for bipartite graphs with polynomially bounded permanents is in NC. Proc. 28th IEEE Symp. Foundations Comp. Sci. pp. 166-172 (1987)
[7] Grigoriev, D., Karpinski, M., Singer, M.: Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. SIAM J. Comp.19, 1059-1063 (1990) · Zbl 0711.68059 · doi:10.1137/0219073
[8] Grigoriev, D., Karpinski, M., Singer, M.: Computational complexity of sparse rational interpolations. SIAM J. Comp.23, 1-11 (1994) · Zbl 0802.68060 · doi:10.1137/S0097539791194069
[9] Grigoriev, D., Karpinski, M., Singer, M.: Computational complexity of sparse real algebraic function interpolation. Proc. MEGA ’92, Progress in Mathematics, Birkhauser, Basel Vol. 109, pp. 91-104 · Zbl 0801.68087
[10] Grigoriev, D., Karpinski, M., Singer, M.: The interpolation problem for k-sparse sums of eigenfunctions of operators. Adv Appl Math12, 76-81 (1991) · Zbl 0785.12004 · doi:10.1016/0196-8858(91)90005-4
[11] Grigoriev, D., Karpinski, M.: A zero-test and an interpolation algorithm for the shifted sparse polynomials. Proc. AAECC-93, Lect. Notes in Comp. Sci., Vol. 673, pp. 162-169. Berlin, Heidelberg, New York, Springer 1993 · Zbl 0809.68072
[12] Grigoriev, D., Karpinski, M., Odlyzko, A. M.: Existence of short proofs of non-divisibility of sparse polynomials under the extended Riemann hypothesis. Proc. ISSAC 92, ACM Press, pp. 117-122 (1992a) · Zbl 0963.68508
[13] Kaltofen, E.: Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials. Proc. 19th Symp. Theory of Computing, ACM Press, pp. 443-452 (1987)
[14] Kaltofen, E., Lakshman, Y. N.: Improved sparse multivariate polynomial interpolation algorithms, Proc. ISSAC 1988, Rome, Italy, Berlin, Heidelberg, New york. Springer LNCS vol. 358, pp. 167-474 (1988)
[15] Kaltofen, E., Trager, B.: Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. J. Symb. Comp.9, 301-320 (1990) · Zbl 0712.12001 · doi:10.1016/S0747-7171(08)80015-6
[16] Kaplanski, I.: An introduction to differential algebra. Hermann, Paris. · Zbl 1182.76259
[17] Kozen, D., Landau, S.: Polynomial decomposition algorithms. JSC, Vol. 7, (5), 445-456 · Zbl 0691.68030
[18] Lakshman, Y. N., Saunders, B. D.: Sparse polynomial interpolation in non-standard bases. SIAM J. Comp.24, (2), 387-397 (1995) · Zbl 0827.68058 · doi:10.1137/S0097539792237784
[19] Lakshman, Y. N., Saunders, B. D.: On computing sparse shifts for univariate polynomials. Proc. ISSAC 1994, Oxford, OK, ACM Press · Zbl 0921.12004
[20] Loos, R.: Computing rational zeros of integral polynomials byp-adic expansion. SIAM J. Comp.,12, 286-293 · Zbl 0536.68045
[21] Mansour, Y.: Randomized interpolation and approximation of sparse polynomials. SIAM J. Comp.,24, (2), 357-368 (1995) · Zbl 0826.65005 · doi:10.1137/S0097539792239291
[22] Muir, T. (enlarged by Metzler, H.): A treatise on the theory of determinants, Dover Publishing, New York (1960)
[23] Ritt, J. F.: Prime and composite polynomials. Trans. Am. Math. Soc.23, 51-66 (1922) · JFM 48.0079.01 · doi:10.1090/S0002-9947-1922-1501189-9
[24] Zippel, R.: Interpolating polynomials from their values. J. Symb. Comp.,9, (3), 375-403 (1990) · Zbl 0702.65011 · doi:10.1016/S0747-7171(08)80018-1
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.