2010/10/11 by Jingwei Chen, Chen, Jingwei, Yong Feng +5
Computer Science · Mathematics · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Symbolic Computation (cs.SC) #cs.CC #cs.SC #math.NT
paper · pdf · doi:10.48550/arxiv.1010.1982
10 pages
arxiv created 2010/10/11 · arxiv updated 2010/10/12
An algorithm which either finds an nonzero integer vector \mathbf m for given t real n-dimensional vectors \mathbf x1,...,\mathbf xt such that \mathbf xiT\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(n4 + n3 log λ(X)) exact arithmetic operations in dimension n and the least Euclidean norm λ(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 Maple built-in function.