Algorithms for computing the sparsest shifts of polynomials via the Berlekamp/Massey algorithm

ABSTRACT

As a sub-procedure our algorithm executes the Berlekamp/Massey algorithm on a sequence of large integers or polynomials. We give a fraction-free version of the Berlekamp/Massey algorithm, which does not require rational numbers or functions and GCD operations on the arising numerators and denominators. The relationship between the solution of Toeplitz systems, Padé approximations, and the Euclidean algorithm is classical. Fraction-free versions [3] can be obtained from the subresultant PRS algorithm [2]. Dornstetter [6] gives an interpretation of the Berlekamp/Massey algorithm as a partial extended Euclidean algorithm. We map the subresultant PRS algorithm onto Dornstetter's formulation. We note that the Berlekamp/Massey algorithm is more efficient than the classical extended Euclidean algorithm.

REFERENCES

• 1: Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
• 2: W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
• 3: S. Cabay , P. Kossowski, Power series remainder sequences and Pade´ fractions over an integral domain, Journal of Symbolic Computation, v.10 n.2, p.139-163, Aug. 1990 [doi>10.1016/S0747-7171(08)80038-7]
• 4: DEMILLO, R. A., AND LIPTON, R. J. A probabilistic remark on algebraic program testing. Information Process. Letters 7, 4 (1978), 193-195.
• 5: Angel Díaz , Erich Kaltofen, FOXBOX: a system for manipulating symbolic objects in black box representation, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.30-37, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281538]
• 6: Jean Louis Dornstetter, On the equivalence between Berlekamp's and Euclid's algorithms, IEEE Transactions on Information Theory, v.33 n.3, p.428-431, May 1, 1987 [doi>10.1109/TIT.1987.1057299]
• 7: Dima Grigoriev , Marek Karpinski, A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.162-169, May 10-14, 1993
• 8: Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM Journal on Computing, v.19 n.6, p.1059-1063, Dec. 1990 [doi>10.1137/0219073]
• 9: Dima Grigoriev , Marek Karpinski , Michael F. Singer, Computational Complexity of Sparse Rational Interpolation, SIAM Journal on Computing, v.23 n.1, p.1-12, Feb. 1994 [doi>10.1137/S0097539791194069]
• 10: GRIGORIEV, D. Y., AND LAKSHMAN, Y. N. Algorithms for computing sparse shifts for multivariate polynomials. Applic. Algebra Engin. Commun. Comput. 11, 1 (2000), 43-67.
• 11: Dima Yu. Grigoriev , Y. N. Lakshman, Algorithms for computing sparse shifts for multivariate polynomials, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.96-103, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220359]
• 12: Erich Kaltofen , Wen-shin Lee , Austin A. Lobo, Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.192-201, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345629]
• 13: Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
• 14: Donald E. Knuth , Daniel H. Greene, Mathematics for the Analysis of Algorithms, Birkhauser Boston, 1999
• 15: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 16: LAKSHMAN Y. N., AND SAUNDERS, B. D. Sparse shifts for univariate polynomials. Applic. Algebra Engin. Commun. Comput. 7, 5 (1996), 351-364.
• 17: Wen-Shin Lee , Erich Kaltofen, Early termination strategies in sparse interpolation algorithms, 2001
• 18: MASSEY, J. L. Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory IT-15 (1969), 122-127.
• 19: ROSSER, J. B., AND SCHOENFELD, L. Approximate formulas for some functions of prime numbers. Ill. J. Math. 6 (1962), 64-94.
• 20: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 21: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.2 Compression (Coding)
          Subjects: Approximate methods

General Terms:
Algorithms, Theory