Computer Science – Symbolic Computation
Scientific paper
2010-10-11
Computer Science
Symbolic Computation
10 pages
Scientific paper
An algorithm which either finds an nonzero integer vector ${\mathbf m}$ for given $t$ real $n$-dimensional vectors ${\mathbf x}_1,...,{\mathbf x}_t$ such that ${\mathbf x}_i^T{\mathbf 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 ${\mathcal O}(n^4 + n^3 \log \lambda(X))$ exact arithmetic operations in dimension $n$ and the least Euclidean norm $\lambda(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.
Chen Jingwei
Feng Yong
Qin Xiaolin
Zhang Jingzhong
No associations
LandOfFree
Detecting Simultaneous Integer Relations for Several Real Vectors does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Detecting Simultaneous Integer Relations for Several Real Vectors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting Simultaneous Integer Relations for Several Real Vectors will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-657872