A fast algorithm for solving linearly recurrent sequences

DOI10.1145/3313880.3313894zbMATH Open1439.39001arXiv1806.03554OpenAlexW2963324215MaRDI QIDQ4630320FDOQ4630320

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)

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.

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

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

zbMATH Keywords

annihilating polynomiallinear recurrence relation

Mathematics Subject Classification ID

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

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
• An Algorithm for Computing Minimal Bidirectional Linear Recurrence Relations
• Fast computation of solutions of linear difference equations by Er's rule
• New techniques for the computation of linear recurrence coefficients
• Title not available (Why is that?)
• An Efficient Formula for Linear Recurrences
• Title not available (Why is that?)

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)