Integer Relation Among Reals (Integer Relation)

From Algorithm Wiki
Jump to navigation Jump to search


Given a vector $x \in \mathbb{R}^n$, find an integer relation, i.e. a non-zero vector $m \in \mathbb{Z}^n$ such that $<x, m> = 0$

Related Problems

Subproblem: Integer Relation Among Integers


$n$: dimensionality of vectors

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
HJLS algorithm 1986 $O(n^{3}(n+k))$ $O(n^{2})$ -- but requires infinite precision with large n or else it becomes unstable Exact Deterministic Time