2
$\begingroup$

Given a basis for a full-rank lattice $\mathcal{L} \subset \mathbb{R}^n$ I want to find a vector with totally positive entries, in other words an element belonging to $\mathcal{L} \cap Q$ where $Q$ is the "quadrant" $\{(x_1, ..., x_n) \in \mathbb{R}^n | x_i \gt 0, 1 \leq i \leq n\}$.

The only construction I can come up with uses doubling and adding of basis vectors. Is there a simpler way (at least intuitively if not computationally)?

It's also important to me that this vector is not too large and I worry a double and add approach will be suboptimal. Are there any variants of shortest vector problem (SVP) algorithms which can find a short vector in a "quadrant" like this?

Improve this question
$\endgroup$
5
  • $\begingroup$ Terminology: The generalized name for quadrants in $n$ dimensions is “orthants”. $\endgroup$
    – LSpice
    Commented Dec 3, 2020 at 22:55
  • 1
    $\begingroup$ Good to know! @LSpice $\endgroup$
    – user106850
    Commented Dec 3, 2020 at 23:36
  • $\begingroup$ For what its worth I haven't been able to get this double and add approach to work, so I'm starting to think this is a somewhat difficult problem $\endgroup$
    – user106850
    Commented Dec 4, 2020 at 7:52
  • $\begingroup$ I asked this question on Math Stackexchange as well. math.stackexchange.com/questions/3936510/… $\endgroup$
    – user106850
    Commented Dec 6, 2020 at 1:43
  • $\begingroup$ Since I haven't had a response I'll add my temporary solution. You can use Babai round off with suitably short vectors in the positive orthant to find vectors in the lattice that may be in that orthant. Its not optimal but it is fast. $\endgroup$
    – user106850
    Commented Jan 30, 2021 at 8:51

1 Answer 1

Reset to default
2
$\begingroup$

Since I haven't had a response I'll add my temporary solution. You can use Babai round off with suitably short vectors in the positive orthant to find vectors in the lattice that may be in that orthant. Its not optimal but it is fast.

Improve this answer
$\endgroup$

You must log in to answer this question.