New techniques for the computation of linear recurrence coefficients
type: Item
instance of: scholarly article
title: New techniques for the computation of linear recurrence coefficients
zbMATH Open document ID: 0978.65130
published in: Finite Fields and their Applications
publication date: 2002-01-21T00:00:00Z
review text: The paper shows algorithms to compute the \(n\)th coefficients of a linear recurrence or, equivalently, the coefficients of a polynomial expressed via the power sums of its zeros. The problem is equivalent to the key equation for decoding BCH error-correcting codes. It has applications in sparse multivariate polynomial interpolation and computation with sparse matrices over finite fields. Previous algorithms for the problem provided an upper bound of \(O(\mu (n) \log n)\), where \(\mu (n)= O(n \log n \log \log n)\) is the bound for multiplying a pair of polynomials modulo \(x^n\). For \(c\) the characteristic of the field of the allowed constants, the algorithms presented in the paper have upper bound \(O(\mu (n))\), if \(c=0\) or \(c> n\). For \(0 < c \leq n\), the Las Vegas type randomization algorithm results in an upper bound of \(O(\mu (n) + \mu (n/c) \log (n/c))\) field operations.
reviewed by: Vilmar Trevisan
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 94B27
zbMATH DE Number: 1421409
zbMATH Keywords: Berlekamp-Massey linear recurrence problem
zbMATH Keywords: sparse matrices over finite fields
zbMATH Keywords: sparse multivariate polynomial interpolation
zbMATH Keywords: power sums
author: Victor Y. Pan
MaRDI profile type: Publication
full work available at URL: ffta.1999.0267
OpenAlex ID: W2043768406
cites work: Algebraic coding theory
cites work: Fast solution of toeplitz systems of equations and computation of Padé approximants
cites work: Q4314299
cites work: Q4110543
cites work: On fast multiplication of polynomials over arbitrary algebras
cites work: A probabilistic remark on algebraic program testing
cites work: Representations and Parallel Computations for Rational Functions
cites work: The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis
cites work: Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
cites work: A method for decoding of generalized Goppa codes (Corresp.)
cites work: Shift-register synthesis and BCH decoding
cites work: Continued Fractions and Linear Recurrences
cites work: Fast computation of GCDs
cites work: Parallel computation of polynomial GCD and some related parallel computations over abstract fields
cites work: Q4526980
cites work: The algebraic decoding of Goppa codes
cites work: Minimal torsion spaces and the partial input/output problem
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: On the complexity of decoding Goppa codes (Corresp.)
cites work: Fast parallel computation of characteristic polynomials by Leverrier's power sum method adapted to fields of finite characteristic
cites work: A method for solving key equation for decoding goppa codes
cites work: Solving sparse linear equations over finite fields
cites work: Q3963124
cites work: Q3851616
DOI: 10.1006/FFTA.1999.0267
description: scientific article; zbMATH DE number 1421409