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

Nigel Smart, Y. Tourigny,

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

*Math. Comp.*, 76, pp. 1995–2022. August 2007. No electronic version available.

## Abstract

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.

Bibtex entry.

## Contact details

## Publication Admin