research-article

On the matrix berlekamp-massey algorithm

Authors:

Erich Kaltofen,

George YuhaszAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 9, Issue 4

Article No.: 33, Pages 1 - 24

https://doi.org/10.1145/2500122

Published: 03 October 2013 Publication History

Abstract

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 generated matrix sequence and has been first introduced by Rissanen [1972a], Dickinson et al. [1974], and Coppersmith [1994]. Our version of the algorithm makes no restrictions on the rank and dimensions of the matrix sequence. We also give new proofs of correctness and complexity for the algorithm, which is based on self-contained loop invariants and includes an explicit termination criterion for a given determinantal degree bound of the minimal matrix generator.

References

[1]

Beckermann, B. and Labahn, G. 1994. A uniform approach for fast computation of matrix-type Padé approximants. SIAM J. Matrix Anal. Applic. 15, 3, 804--823.

Digital Library

[2]

Berlekamp, E. R. 1968. Algebraic Coding Theory. McGraw-Hill, New York.

[3]

Brent, R. P., Gustavson, F. G., and Yun, D. Y. Y. 1980. Fast solution of Toeplitz systems of equations and computation of Padé approximants. J. Algorithms 1, 259--295.

[4]

Cabay, S., Choi, D. K., and Labahn, G. 1990. Inverses of block Hankel and block Toeplitz matrices. SIAM Journal of Computing 19, 98--123.

Digital Library

[5]

Coppersmith, D. 1994. Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. Math. Comput. 62, 205, 333--350.

Digital Library

[6]

Dickinson, B. W., Morf, M., and Kailath, T. 1974. A minimal realization algorithm for matrix sequences. IEEE Trans. Automatic Control shape AC-19, 1, 31--38.

[7]

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

Digital Library

[8]

Dummit, D. S. and Foote, R. M. 1991. Abstract Algebra. Prentice Hall, Inc., Englewood Cliffs, NJ 07632.

[9]

Durbin, J. 1959. The fitting of time-series models. Rev. Int. Stat. Inst. 28, 229--249.

[10]

Giesbrecht, M., Kaltofen, E., and Lee, W.-S. 2003. Algorithms for computing sparsest shifts of polynomials in power, chebychev, and pochhammer bases. J. Symbolic Comput. 36, 3--4, (Special issue (ISSAC 2002). Guest editors: M. Giusti & L. M. Pardo. URL://EKbib/03/GKL03.pdf.) 401--424.

Digital Library

[11]

Giesbrecht, M., Kaltofen, E., and Lee, W.-S. 2002. Algorithms for computing the sparsest shifts for polynomials via the Berlekamp/Massey algorithm. In Proceedings of the 2002 International Symposium on Symbolic Algebraic Comput. (ISSAC'02), T. Mora (Ed.). ACM, New York, 101--108.

Digital Library

[12]

Giorgi, P., Jeannerod, C.-P., and Villard, G. 2003. On the complexity of polynomial matrix computations. In Proceedings of the 2003 International Symposium on Symbolic Algebraic Comput. (ISSAC'03), J. R. Sendra Ed., ACM, New York, 135--142.

Digital Library

[13]

Kailath, T. 1980. Linear systems. Prentice-Hall.

[14]

Kaltofen, E. 1992. On computing determinants of matrices without divisions. In Proceedings of the 1992 International Symposium on Symbolic Algebraic Computing (ISSAC'92), P. S. Wang (Ed.). ACM Press, New York, 342--349.

Digital Library

[15]

Kaltofen, E. 1995. Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems. Math. Comput. 64, 210, 777--806.

Digital Library

[16]

Kaltofen, E. and Lee, W.-S. 2003. Early termination in sparse interpolation algorithms. J. Symbolic Comput. 36, 3--4, Special issue (ISSAC 2002). 365--400.

Digital Library

[17]

Kaltofen, E. and Saunders, B. D. 1991. On Wiedemann's method of solving sparse linear systems. In Proceedings of the (AAECC-9). H. F. Mattson, T. Mora, and T. R. N. Rao Eds., Lecture Notes in Computer Science, vol. 539. Springer-Verlag, Berlin, Germany, 29--38.

Digital Library

[18]

Kaltofen, E. and Villard, G. 2004. On the complexity of computing determinants. Comput. Complex. 13, 3--4, 91--130.

Digital Library

[19]

Levinson, N. 1947. The Wiener RMS (Root-Mean-Square) error criterion in the filter design and prediction. J. Math. Phys. 25, 261--278.

[20]

Lobo, A. A. 1995. Matrix-Free Linear System Solving and Applications to Symbolic Computation. Ph.D. dissertation. Rensselaer Polytechnic Instit., Troy, NY.

Digital Library

[21]

Massey, J. L. 1969. Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory it- 15, 122--127.

Digital Library

[22]

Popov, V. M. 1970. Some properties of control systems with irreducible matrix transfer functions. In Lecture Notes in Mathematics. Vol. 144, Springer-Verlag, Berlin, 169--180.

[23]

Rissanen, J. 1972a. Realizations of Matrix Sequences. Technical rep. RJ-1032. IBM T. J. Watson Research Center, Yorktown Heights, New York.

[24]

Rissanen, J. 1972b. Realizations of Matrix Sequences. Technical rep. RJ-1032. IBM T. J. Watson Research Center, Yorktown Heights, New York.

[25]

Sugiyama, Y., Kasahara, M., Hirasawa, S., and Namekawa, T. 1975. A method for solving key equation for decoding Goppa codes. Inf. Cont. 27, 87--99.

[26]

Thomé, E. 2002. Subquadratic Computation of Vector Generating Polynomials and Improvements of the Block Wiedemann Method. J. Symbolic Comput. 33, 5, 757--775.

Digital Library

[27]

Turner, W. J. 2002. Black box linear algebra with the LINBOX library. Ph.D. dissertation. North Carolina State University, Raleigh, North Carolina.

Digital Library

[28]

Van Barel, M. and Bultheel, A. 1991. The computation of non-perfect Padé-Hermite approximants. Numer. Algo. 1, 285--304.

[29]

Van Barel, M. and Bultheel, A. 1992. A general module theoretic framework for vector M-Padé and matrix rational interpolation. Numer. Algo. 3, 451--462.

[30]

Villard, G. 1997a. Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems. In ISSAC 97: Proceedings of the 1997 International Symposium on Symbolic Algebraic Computation, W. Küchlin Ed., ACM, New York, 32--39.

Digital Library

[31]

Villard, G. 1997b. A study of Coppersmith's block Wiedemann algorithm using matrix polynomials. Rapport de Recherche 975 IM. Institut d'Informatique et de Mathématiques Appliquées de Grenoble.

[32]

Wiedemann, D. 1986. Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory it-32, 54--62.

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
Neiger VSalvy BSchost ÉVillard G(2024)Faster Modular CompositionJournal of the ACM10.1145/363834971:2(1-79)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638349
Song ZLi YZhao YDing QCheng HHuang C(2024)A Word-oriented Code on Galois Field with Accurate Period2024 3rd International Joint Conference on Information and Communication Engineering (JCICE)10.1109/JCICE61382.2024.00018(41-45)Online publication date: 10-May-2024
https://doi.org/10.1109/JCICE61382.2024.00018
Show More Cited By

Index Terms

On the matrix berlekamp-massey algorithm

Recommendations

Berlekamp/massey algorithms for linearly generated matrix sequences
On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field

We derive an explicit count for the number of singular nxn Hankel (Toeplitz) matrices whose entries range over a finite field with q elements by observing the execution of the Berlekamp/Massey algorithm on its elements. Our method yields explicit counts ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 9, Issue 4

September 2013

131 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/2533288

Issue’s Table of Contents

Copyright © 2013 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 October 2013

Accepted: 01 March 2013

Revised: 01 February 2013

Received: 01 December 2011

Published in TALG Volume 9, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
305
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Nov 2024

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
Neiger VSalvy BSchost ÉVillard G(2024)Faster Modular CompositionJournal of the ACM10.1145/363834971:2(1-79)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638349
Song ZLi YZhao YDing QCheng HHuang C(2024)A Word-oriented Code on Galois Field with Accurate Period2024 3rd International Joint Conference on Information and Communication Engineering (JCICE)10.1109/JCICE61382.2024.00018(41-45)Online publication date: 10-May-2024
https://doi.org/10.1109/JCICE61382.2024.00018
Pernet CSignargout HVillard G(2024)High-order lifting for polynomial Sylvester matricesJournal of Complexity10.1016/j.jco.2023.10180380:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.jco.2023.101803
Wen XZhu RHe ZHuang SYin ZLiu GLiu ZMa Q(2023)A Linear Recurrence-Based Pseudorandom Number Generator Optimized for Detector EmulatorsIEEE Transactions on Nuclear Science10.1109/TNS.2023.328525170:8(2139-2147)Online publication date: Aug-2023
https://doi.org/10.1109/TNS.2023.3285251
Kaltofen EMaza MZhi L(2022)Sparse Polynomial Hermite InterpolationProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535501(469-478)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535501
Harrison GJohnson JSaunders B(2022)Probabilistic analysis of block Wiedemann for leading invariant factorsJournal of Symbolic Computation10.1016/j.jsc.2021.06.005108:C(98-116)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1016/j.jsc.2021.06.005
Karpman PPernet CSignargout HVillard GChyzak FLabahn G(2021)Computing the Characteristic Polynomial of Generic Toeplitz-like and Hankel-like MatricesProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465542(249-256)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465542
Berthomieu JFaugère J(2020)In-depth comparison of the Berlekamp–Massey–Sakata and the Scalar-FGLM algorithms: The adaptive variantsJournal of Symbolic Computation10.1016/j.jsc.2019.09.001101(270-303)Online publication date: Nov-2020
https://doi.org/10.1016/j.jsc.2019.09.001
Baragaña IRoca A(2019)Linear feedback shift registers and the minimal realization problemLinear Algebra and its Applications10.1016/j.laa.2018.06.009576(200-227)Online publication date: Sep-2019
https://doi.org/10.1016/j.laa.2018.06.009
Show More Cited By

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents