A fast algorithm for solving linearly recurrent sequences

DOI10.1145/3313880.3313894MaRDI QIDQ4630320zbMATH OpenOpenAlexFDO

Authors Seung Gyu Hyun, Stephen Melczer, Catherine st-Pierre

Publication date 29 March 2019

Published in ACM Communications in Computer Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.03554

zbMATH Keywords

annihilating polynomiallinear recurrence relation

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Nonnumerical algorithms (68W05) Linear difference equations (39A06)

Abstract: We present an algorithm which computes the $D^{th}$ term of a sequence satisfying a linear recurrence relation of order $d$ over a field $K$ in $$ operations in $K$, where $$ is the degree of the squarefree part of the annihilating polynomial of the recurrence and $mathsfM$ is the cost of polynomial multiplication in $K$. This is a refinement of the previously optimal result of $O(mathsfM(d)log(D))$ operations, due to Fiduccia.

Recommendations

• An Efficient Formula for Linear Recurrences
• Efficient computation of terms of linear recurrence sequences of any order
• New techniques for the computation of linear recurrence coefficients
• scientific article; zbMATH DE number 2124950
• Horner's rule and the computation of linear recurrences

Cited in

(12)

• Horner's rule and the computation of linear recurrences
• Connecting slow solutions to nested recurrences with linear recurrent sequences
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Fast recursive algorithms for a class of linear equations
• A New Algorithm to Compute Remote Terms in Special Types of Characteristic Sequences
• Efficient computation of terms of linear recurrence sequences of any order
• Fast computation of solutions of linear difference equations by Er's rule
• An Algorithm for Computing Minimal Bidirectional Linear Recurrence Relations
• New techniques for the computation of linear recurrence coefficients
• scientific article; zbMATH DE number 2086819 (Why is no real title available?)
• An Efficient Formula for Linear Recurrences
• scientific article; zbMATH DE number 2124950 (Why is no real title available?)

This page was built for publication: A fast algorithm for solving linearly recurrent sequences

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