An Efficient Formula for Linear Recurrences
From MaRDI portal
Publication:5186731
DOI10.1137/0214007zbMath0561.68033OpenAlexW2007463894MaRDI QIDQ5186731
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0214007
fast algorithmsdifference equationsrecurrence relationlinear recurrencesparallel algorithmsalgebraic complexitycompanion matricesfast polynomial multiplicationpolynomial arithmetic
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)
Related Items
Algebraic complexity of computing polynomial zeros, On the number of arithmetical operations for finding Fibonacci numbers, Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source, Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications, Beating binary powering for polynomial matrices, Fast coefficient computation for algebraic power series in positive characteristic, On Faster Integer Calculations Using Non-arithmetic Primitives, A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity, New recombination algorithms for bivariate polynomial factorization based on Hensel lifting, Weak minimization of DFA -- an algorithm and applications, Fast algorithms for the Sylvester equation \(AX-XB^{T}=C\), Efficient computation of terms of linear recurrence sequences of any order, Substitutions for linear shift register sequences and the factorization algorithms of Berlekamp and Niederreiter, Message transmission for GH-public key cryptosystem