New techniques for the computation of linear recurrence coefficients

DOI10.1006/FFTA.1999.0267MaRDI QIDQ1971066zbMATH OpenOpenAlexFDO

Authors Victor Y. Pan

Publication date 21 January 2002

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/ffta.1999.0267

zbMATH Keywords

power sumsBerlekamp-Massey linear recurrence problemsparse matrices over finite fieldssparse multivariate polynomial interpolation

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Number-theoretic algorithms; complexity (11Y16) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Recommendations

• scientific article; zbMATH DE number 1559532
• An Efficient Formula for Linear Recurrences
• Efficient computation of terms of linear recurrence sequences of any order
• Polynomial-division-based algorithms for computing linear recurrence relations
• A fast algorithm for solving linearly recurrent sequences

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3785035 (Why is no real title available?)
• scientific article; zbMATH DE number 3533996 (Why is no real title available?)
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 1559532 (Why is no real title available?)
• A method for decoding of generalized Goppa codes (Corresp.)
• A method for solving key equation for decoding goppa codes
• A probabilistic remark on algebraic program testing
• Algebraic coding theory
• Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
• Continued Fractions and Linear Recurrences
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast computation of GCDs
• Fast parallel computation of characteristic polynomials by Leverrier's power sum method adapted to fields of finite characteristic
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Minimal torsion spaces and the partial input/output problem
• On fast multiplication of polynomials over arbitrary algebras
• On the complexity of decoding Goppa codes (Corresp.)
• Parallel computation of polynomial GCD and some related parallel computations over abstract fields
• Representations and Parallel Computations for Rational Functions
• Shift-register synthesis and BCH decoding
• Solving sparse linear equations over finite fields
• The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis
• The algebraic decoding of Goppa codes

Cited in

(13)

• Evaluation of Polynomials Using the Structure of the Coefficients
• Algebraic diagonals and walks: algorithms, bounds, complexity
• Symbolic and numeric methods for exploiting structure in constructing resultant matrices
• The Berlekamp-Massey algorithm revisited
• Deterministic root finding over finite fields using Graeffe transforms
• New efficient programs to calculate general recoupling coefficients. II: Evaluation of a summation formula
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• A fast algorithm for solving linearly recurrent sequences
• Block diagonalization and LU-equivalence of Hankel matrices
• A linear complexity analysis of quadratic residues and primitive roots spacings
• Fast computation of special resultants
• An Efficient Formula for Linear Recurrences
• On Elkies subgroups of \(\ell\)-torsion points in elliptic curves defined over a finite field

This page was built for publication: New techniques for the computation of linear recurrence coefficients

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1971066)