A multidimensional continued fraction based on a high-order recurrence relation

YJM Tourigny, NP Smart

Research output: Contribution to journalArticle (Academic Journal)peer-review


The paper describes and studies an iterative algorithm for finding small values of a set of linear forms over vectors of integers. The algorithm uses a linear recurrence relation to generate a vector sequence, the basic idea being to choose the integral coefficients in the recurrence relation in such a way that the linear forms take small values, subject to the requirement that the integers should not become too large. The problem of choosing good coefficients for the recurrence relation is thus related to the problem of finding a good approximation of a given vector by a vector in a certain one-parameter family of lattices; the novel feature of our approach is that practical formulae for the coefficients are obtained by considering the limit as the parameter tends to zero. The paper discusses two rounding procedures to solve the underlying inhomogeneous Diophantine approximation problem: the first, which we call ``naive rounding'' leads to a multidimensional continued fraction algorithm with suboptimal asymptotic convergence properties; in particular, when it is applied to the familiar problem of simultaneous rational approximation, the algorithm reduces to the classical Jacobi-Perron algorithm. The second rounding procedure is Babai's nearest-plane procedure. We compare the two rounding procedures numerically; our experiments suggest that the multidimensional continued fraction corresponding to nearest-plane rounding converges at an optimal asymptotic rate.
Translated title of the contributionA multidimensional continued fraction based on a high-order recurrence relation
Original languageEnglish
Pages (from-to)1995 - 2022
Number of pages28
JournalMathematics of Computation
Volume76 (260)
Publication statusPublished - May 2007

Bibliographical note

Publisher: American Mathematical Society


Dive into the research topics of 'A multidimensional continued fraction based on a high-order recurrence relation'. Together they form a unique fingerprint.

Cite this