{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T05:37:50Z","timestamp":1768714670283,"version":"3.49.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,9,1]],"date-time":"2013-09-01T00:00:00Z","timestamp":1377993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCR-0305314 and CCF-0514585"],"award-info":[{"award-number":["CCR-0305314 and CCF-0514585"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0305314 and CCF-0514585"],"award-info":[{"award-number":["CCR-0305314 and CCF-0514585"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2500122","type":"journal-article","created":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T18:14:28Z","timestamp":1380651268000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["On the matrix berlekamp-massey algorithm"],"prefix":"10.1145","volume":"9","author":[{"given":"Erich","family":"Kaltofen","sequence":"first","affiliation":[{"name":"North Carolina State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Yuhasz","sequence":"additional","affiliation":[{"name":"North Carolina State University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,10,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892230031"},{"key":"e_1_2_1_2_1","volume-title":"Algebraic Coding Theory","author":"Berlekamp E. R."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90013-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/2153413"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1974.1100457"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1987.1057299"},{"key":"e_1_2_1_8_1","unstructured":"Dummit D. S. and Foote R. M. 1991. Abstract Algebra. Prentice Hall Inc. Englewood Cliffs NJ 07632.  Dummit D. S. and Foote R. M. 1991. Abstract Algebra. Prentice Hall Inc. Englewood Cliffs NJ 07632."},{"key":"e_1_2_1_9_1","first-page":"229","article-title":"The fitting of time-series models","volume":"28","author":"Durbin J.","year":"1959","journal-title":"Rev. Int. Stat. Inst."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(03)00087-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/780506.780519"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/860854.860889"},{"key":"e_1_2_1_13_1","volume-title":"Linear systems","author":"Kailath T."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/143242.143350"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.2307\/2153451"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(03)00088-9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Kaltofen E.\n     and \n      Saunders B. D\n  . \n  1991\n  . 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. \n  539\n  . \n  Springer-Verlag Berlin Germany 29--38.   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.","DOI":"10.1007\/3-540-54522-0_93"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0185-3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1946251261"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1969.1054260"},{"key":"e_1_2_1_22_1","series-title":"Lecture Notes in Mathematics.","volume-title":"Some properties of control systems with irreducible matrix transfer functions","author":"Popov V. M."},{"key":"e_1_2_1_23_1","volume-title":"Realizations of Matrix Sequences. Technical rep. RJ-1032","author":"Rissanen J."},{"key":"e_1_2_1_24_1","volume-title":"Realizations of Matrix Sequences. Technical rep. RJ-1032","author":"Rissanen J."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(75)90090-X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2002.0533"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02142327"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02141952"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/258726.258742"},{"key":"e_1_2_1_31_1","volume-title":"A study of Coppersmith's block Wiedemann algorithm using matrix polynomials. Rapport de Recherche 975 IM","author":"Villard G."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057137"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2500122","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2500122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:31Z","timestamp":1750232071000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2500122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1145\/2500122"],"URL":"https:\/\/doi.org\/10.1145\/2500122","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]},"assertion":[{"value":"2011-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}