Simultaneous Integer Relation Detection and Its an Application

Details Simultaneous Integer Relation Detection and Its an Application Simultaneous Integer Relation Detection and Its an Application

2009-06-26

arxiv.org/abs/0906.4917v2

Computer Science

Symbolic Computation

Scientific paper

Let $\mathbf{x_1}, ..., \mathbf{x_t} \in \mathbb{R}^{n}$. A simultaneous integer relation (SIR) for $\mathbf{x_1}, ..., \mathbf{x_t}$ is a vector $\mathbf{m} \in \mathbb{Z}^{n}\setminus\{\textbf{0}\}$ such that $\mathbf{x_i}^T\mathbf{m} = 0$ for $i = 1, ..., t$. In this paper, we propose an algorithm SIRD to detect an SIR for real vectors, which constructs an SIR within $\mathcal {O}(n^4 + n^3 \log \lambda(X))$ arithmetic operations, where $\lambda(X)$ is the least Euclidean norm of SIRs for $\mathbf{x_1}, >..., \mathbf{x_t}$. One can easily generalize SIRD to complex number field. Experimental results show that SIRD is practical and better than another detecting algorithm in the literature. In its application, we present a new algorithm for finding the minimal polynomial of an arbitrary complex algebraic number from its an approximation, which is not based on LLL. We also provide a sufficient condition on the precision of the approximate value, which depends only on the height and the degree of the algebraic number.

Affiliated with

Also associated with

No associations

Rating

Simultaneous Integer Relation Detection and Its an Application 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 Simultaneous Integer Relation Detection and Its an Application, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simultaneous Integer Relation Detection and Its an Application will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-670953