Fast computation of solutions of linear difference equations by Er's rule
From MaRDI portal
A linear difference equation of \(k\)-th order is considered. An efficient algorithm for the computation of the \(n\)-th element of the solution is presented. This algorithm only uses \(O(k^ 2\log({n\over k}))\) time and \(O(k)\) space for performing the task and is better than previously known results.
Recommendations
Cites work
- A Fast Algorithm for Computing Order-K Fibonacci Numbers
- A Formal Derivation of an 0(log n) Algorithm for Computing Fibonacci Numbers
- A presentation of the Fibonacci algorithm
- An \(O(\log n)\) algorithm for computing the \(n\)th element of the solution of a difference equation
- An interative program to calculate Fibonacci numbers in O(log n) arithmetic operations
- An O(log n) algorithm for computing general order-k Fibonacci numbers
- Computing Fibonacci numbers (and similarly defined functions) in log time
- Computing sums of order-k Fibonacci numbers in log time
- Derivation of an O(k^ 2 n) algorithm for computing order-k Fibonacci numbers from the O(k^ 3 n) matrix multiplication method
- scientific article; zbMATH DE number 3857208 (Why is no real title available?)
- scientific article; zbMATH DE number 3857295 (Why is no real title available?)
- scientific article; zbMATH DE number 3260110 (Why is no real title available?)
This page was built for publication: Fast computation of solutions of linear difference equations by Er's rule
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1187207)