Detecting Simultaneous Integer Relations for Several Real Vectors

Authors Jingwei Chen, Yong Feng, Xiaolin Qin, Jingzhong Zhang

Publication date 10 October 2010

Abstract: An algorithm which either finds an nonzero integer vector

m a t h b f m

for given

t

real

n

-dimensional vectors

{m a t h b f x}_{1}, ..., {m a t h b f x}_{t}

such that

{m a t h b f x}_{i}^{T} m a t h b f m = 0

or proves that no such integer vector with norm less than a given bound exists is presented in this paper. The cost of the algorithm is at most

m a t h c a l O (n^{4} + n^{3} l o g l a m b d a (X))

exact arithmetic operations in dimension

n

and the least Euclidean norm

l a m b d a (X)

of such integer vectors. It matches the best complexity upper bound known for this problem. Experimental data show that the algorithm is better than an already existing algorithm in the literature. In application, the algorithm is used to get a complete method for finding the minimal polynomial of an unknown complex algebraic number from its approximation, which runs even faster than the corresponding emph{Maple} built-in function.

This page was built for publication: Detecting Simultaneous Integer Relations for Several Real Vectors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6221157)