Article

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

Authors:

Mark Giesbrecht,

Erich Kaltofen,

Wen-shin LeeAuthors Info & Claims

ISSAC '02: Proceedings of the 2002 international symposium on Symbolic and algebraic computation

Pages 101 - 108

https://doi.org/10.1145/780506.780519

Published: 10 July 2002 Publication History

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]

BEN-OR, M., AND TIWARI, P. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proc. Twentieth Annual ACM Symp. Theory Comput. (New York, N.Y., 1988), ACM Press, pp. 301-309.

Digital Library

[2]

BROWN, W. S., AND TRAUB, J. F. On Euclid's algorithm and the theory of subresultants. J. ACM 18 (1971), 505-514.

Digital Library

[3]

CABAY, S., AND KOSSOWSKI, P. Power series remainder sequences and pade fractions over an integral domain. J. Symbolic Comput. 10 (1990), 139-163.

Digital Library

[4]

DEMILLO, R. A., AND LIPTON, R. J. A probabilistic remark on algebraic program testing. Information Process. Letters 7, 4 (1978), 193-195.

[5]

DÍAZ, A., AND KALTOFEN, E. FOXBOX a system for manipulating symbolic objects in black box representation. In Proc. 1998 Internat. Symp. Symbolic Algebraic Comput. (ISSAC'98) (New York, N. Y., 1998), O. Gloor, Ed., ACM Press, pp. 30-37.

Digital Library

[6]

DORNSTETTER, J. L. On the equivalence between Berlekamp's and Euclid's algorithms. IEEE Trans. Inf. Theory IT-33, 3 (1987), 428-431.

Digital Library

[7]

GRIGORIEV, D. Y., AND KARPINSKI, M. A zero-test and an interpolation algorithm for the shifted sparse polynomials. In Proc. AAECC-10 (Heidelberg, Germany, 1993), vol. 673 of Lect. Notes Comput. Sci., Springer Verlag, pp. 162-169.

Digital Library

[8]

GRIGORIEV, D. Y., KARPINSKI, M., AND SINGER, M. F. Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. SIAM J. Comput. 19, 6 (1990), 1059-1063.

Digital Library

[9]

GRIGORIEV, D. Y., KARPINSKI, M., AND SINGER, M. F. Computational complexity of sparse rational function interpolation. SIAM J. Comput. 23 (1994), 1-11.

Digital Library

[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]

GRIGORIEV, D. Y., AND LAKSHMAN Y. N. Algorithms for computing sparse shifts for multivariate polynomials. In Proc. 1995 Internat. Symp. Symbolic Algebraic Comput. ISSAC'95 (New York, N. Y., 1995), A. H. M. Levelt, Ed., ACM Press, pp. 96-103.

Digital Library

[12]

KALTOFEN, E., LEE, W.-S., AND LOBO, A. A. Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm. In Proc. 2000 Internat. Symp. Symbolic Algebraic Comput. (ISSAC'00) (New York, N. Y., 2000), C. Traverso, Ed., ACM Press, pp. 192-201.

Digital Library

[13]

KALTOFEN, E., AND 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 (1990), 301-320.

Digital Library

[14]

KNUTH, D. E. Mathematics for the Analysis of Algorithms, 3rd ed. Birkhäuser, 1983.

Digital Library

[15]

KNUTH, D. E. Seminumerical Algorithms, Third ed., vol. 2 of The Art of Computer Programming. Addison Wesley, Reading, Massachusetts, USA, 1997.

Digital Library

[16]

LAKSHMAN Y. N., AND SAUNDERS, B. D. Sparse shifts for univariate polynomials. Applic. Algebra Engin. Commun. Comput. 7, 5 (1996), 351-364.

Digital Library

[17]

LEE, W.-S. Early termination strategies in sparse interpolation algorithms. PhD thesis, North Carolina State Univ., Raleigh, North Carolina, Dec. 2001. 107 pages.

Digital Library

[18]

MASSEY, J. L. Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory IT-15 (1969), 122-127.

Digital Library

[19]

ROSSER, J. B., AND SCHOENFELD, L. Approximate formulas for some functions of prime numbers. Ill. J. Math. 6 (1962), 64-94.

[20]

SCHWARTZ, J. T. Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27 (1980), 701-717.

Digital Library

[21]

ZIPPEL, R. Probabilistic algorithms for sparse polynomials. In Proc. EUROSAM '79 (Heidelberg, Germany, 1979), vol. 72 of Lect. Notes Comput. Sci., Springer Verlag, pp. 216-226.

Digital Library

Cited By

Kaltofen E(2024)Encounters in Symbolic Computation: Ideas for the AgesProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3672619(1-7)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3672619
Kaltofen EYang Z(2021)Sparse Interpolation With Errors in Chebyshev Basis Beyond Redundant-Block DecodingIEEE Transactions on Information Theory10.1109/TIT.2020.302703667:1(232-243)Online publication date: Jan-2021
https://doi.org/10.1109/TIT.2020.3027036
Hao ZKaltofen EZhi LAbramov SZima EGao X(2016)Numerical Sparsity Determination and Early TerminationProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930924(247-254)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930924
Show More Cited By

Index Terms

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

Recommendations

On Berlekamp–Massey and Berlekamp–Massey–Sakata Algorithms
Computer Algebra in Scientific Computing
Abstract
The Berlekamp–Massey and Berlekamp–Massey–Sakata algorithms compute a minimal polynomial or polynomial set of a linearly recurring sequence or multi-dimensional array. In this paper some underlying properties of and connections between these two ...
Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases
Special issue: International symposium on symbolic and algebraic computation (ISSAC 2002)

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 ...
On the matrix berlekamp-massey algorithm

We analyze the Matrix Berlekamp/Massey algorithm, which generalizes the Berlekamp/Massey algorithm [Massey 1969] for computing linear generators of scalar sequences. The Matrix Berlekamp/Massey algorithm computes a minimal matrix generator of a linearly ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '02: Proceedings of the 2002 international symposium on Symbolic and algebraic computation

July 2002

296 pages

ISBN:1581134843

DOI:10.1145/780506

Conference Chair:
Marc Giusti
CNRS-Ecole Polytechnique, France

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 July 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC02

Sponsor:

SIGSAM

ISSAC02: International Symposium on Symbolic and Algebraic Computation

July 7 - 10, 2002

Lille, France

Acceptance Rates

ISSAC '02 Paper Acceptance Rate 35 of 86 submissions, 41%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
149
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kaltofen E(2024)Encounters in Symbolic Computation: Ideas for the AgesProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3672619(1-7)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3672619
Kaltofen EYang Z(2021)Sparse Interpolation With Errors in Chebyshev Basis Beyond Redundant-Block DecodingIEEE Transactions on Information Theory10.1109/TIT.2020.302703667:1(232-243)Online publication date: Jan-2021
https://doi.org/10.1109/TIT.2020.3027036
Hao ZKaltofen EZhi LAbramov SZima EGao X(2016)Numerical Sparsity Determination and Early TerminationProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930924(247-254)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930924
Stoutemyer D(2014)A computer algebra user interface manifestoACM Communications in Computer Algebra10.1145/2576802.257682747:3/4(130-165)Online publication date: 28-Jan-2014
https://dl.acm.org/doi/10.1145/2576802.2576827
Kaltofen EYuhasz G(2013)On the matrix berlekamp-massey algorithmACM Transactions on Algorithms10.1145/25001229:4(1-24)Online publication date: 3-Oct-2013
https://dl.acm.org/doi/10.1145/2500122
Giesbrecht MKotsireas ILobo A(2007)ISSAC 2007 poster abstractsACM Communications in Computer Algebra10.1145/1296772.129677541:1-2(38-72)Online publication date: 1-Mar-2007
https://dl.acm.org/doi/10.1145/1296772.1296775

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents