A fast algorithm for repeated computation of linear recurrence relations

descriptionPublicationkeyboard_double_arrow_right Article 01 Dec 1977 English Publisher:Springer Science and Business Media LLCJournal:BIT, volume 17, pages 430-436 (issn: 0006-3835, eissn: 1572-9125,

Copyright policy )

Authors: Miklosko, Jozef;

doi: 10.1007/bf01933452

A fast algorithm for repeated computation of linear recurrence relations

- Summary
- Subjects
- Metrics

Abstract

Let the calculation of thenth term of a general recurrence relation requireO(q(n)) arithmetical operations. The derivation is given of a new algorithm that performsm repetitions of this calculation with different initial conditions requiring onlyO(q(n)) +O(m) operations. The application of this algorithm to accelerate the calculation of continued fractions and the solution of three- and five-diagonal systems of linear equations, is also described.

Related Organizations

Slovak Academy of Sciences
Slovakia

Keywords

Extrapolation to the limit, deferred corrections, Iterative numerical methods for linear systems, Numerical methods for functional equations, Convergence and divergence of continued fractions

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	1
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average