Let $A$ be a non-singular matrix in $\mathbb{R}^{n \times n}$. Let $S^{n-1}$ denote the surface of the unit $n$-sphere in $\mathbb{R}^{n}$. Suppose we know that there exists an $x \in S^{n-1}$ such that $Ax \in \mathbb{Z}^{n}$. Is there a numerical method, such as the gradient method, for approximating such an $x$?
Equivalently the problem can be formulated as finding an $x\in S^{n-1}$ such that the function $f(x)=\text{dist}(Ax, {\Bbb Z}^n)$, is equal to $0$.
If we let $y = Ax$, then you're asking whether there exists $y \in \mathbb{Z}^n$ such that $|A^{-1} y|=1$. The set $A^{-1} \mathbb{Z}^n$ is a lattice in $\mathbb{R}^n$, and so the question comes down to whether there is a vector of length 1 in a given lattice. Unfortunately, that problem seems to be hard. For example, finding the shortest nonzero vector length in a given lattice is NP-hard, and although I don't know offhand of a hardness theorem for the specific problem of finding a length 1 vector, I expect it's at least as hard.
If $n$ is not very large and 1 is among the shortest vector lengths in $A^{-1} \mathbb{Z}^n$, then you can solve the problem in a reasonable amount of time by using lattice basis reduction to enumerate the short vectors.
However, even for $n=2$ it can get complicated when $1$ isn't a particularly short vector. For example, the nonzero vector lengths in the square lattice $\mathbb{Z}^2$ are the square roots of positive integers for which every prime congruent to 3 mod 4 has an even exponent in the prime factorization. That means if $k$ is a positive integer and $A$ is $\sqrt{k}$ times the identity matrix, then 1 is a vector length in $A^{-1} \mathbb{Z}^2$ iff the prime factorization of $k$ has this property. I expect there's no better way to figure this out than factoring $k$. If there were an efficient algorithm to produce a high-precision solution numerically when a solution exists, then we could run it, round to integers, and check whether it worked, which would bypass the need to factor $k$.
