New techniques for the computation of linear recurrence coefficients
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.
- 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
- 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 computation of GCDs
- Fast parallel computation of characteristic polynomials by Leverrier's power sum method adapted to fields of finite characteristic
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Fast solution of toeplitz systems of equations and computation of Padé approximants
- 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?)
- 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 algebraic decoding of Goppa codes
- The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis
- On Elkies subgroups of \(\ell\)-torsion points in elliptic curves defined over a finite field
- New efficient programs to calculate general recoupling coefficients. II: Evaluation of a summation formula
- Symbolic and numeric methods for exploiting structure in constructing resultant matrices
- Fast computation of special resultants
- The Berlekamp-Massey algorithm revisited
- Block diagonalization and LU-equivalence of Hankel matrices
- Algebraic diagonals and walks: algorithms, bounds, complexity
- Deterministic root finding over finite fields using Graeffe transforms
- A fast algorithm for solving linearly recurrent sequences
- Evaluation of Polynomials Using the Structure of the Coefficients
- A linear complexity analysis of quadratic residues and primitive roots spacings
- An Efficient Formula for Linear Recurrences
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
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)
