# Error in finding the closest vector in a sublattice of Z^n

I'm trying to use the Sage package for discrete subgroups of Z^n.

But the "closest_vector()" function seems to be behaving incorrectly.

Here are some examples: The input

from sage.modules.free_module_integer import IntegerLattice

L = IntegerLattice([[2,0,0],[0,1,0]])
L
u=[0,0,0]
L.closest_vector(u)

yields the output

Free module of degree 3 and rank 2 over Integer Ring
User basis matrix:
[0 1 0]
[2 0 0]
(0, 0, 0)

as expected.

But the input

from sage.modules.free_module_integer import IntegerLattice

L = IntegerLattice([[2,0,0],[1,1,0]])
L
u=[0,0,0]
L.closest_vector(u)

yields the output

Free module of degree 3 and rank 2 over Integer Ring
User basis matrix:
[ 1  1  0]
[ 1 -1  0]
Error in lines 5-5
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 1, in <module>
File "/ext/sage/sage-8.4_1804/local/lib/python2.7/site-packages/sage/modules/free_module_integer.py", line 787, in closest_vector
voronoi_cell = self.voronoi_cell()
File "sage/misc/cachefunc.pyx", line 1953, in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10824)
w = self._instance_call(*args, **kwds)
File "sage/misc/cachefunc.pyx", line 1829, in sage.misc.cachefunc.CachedMethodCaller._instance_call (build/cythonized/sage/misc/cachefunc.c:10280)
return self.f(self._instance, *args, **kwds)
File "/ext/sage/sage-8.4_1804/local/lib/python2.7/site-packages/sage/modules/free_module_integer.py", line 724, in voronoi_cell
File "/ext/sage/sage-8.4_1804/local/lib/python2.7/site-packages/sage/modules/diamond_cutting.py", line 263, in calculate_voronoi_cell
artificial_length = max(abs(v) for v in basis).ceil() * 2
File "sage/structure/element.pyx", line 493, in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4550)
return self.getattr_from_category(name)
File "sage/structure/element.pyx", line 506, in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4659)
return getattr_from_other_class(self, cls, name)
File "sage/cpython/getattr.pyx", line 394, in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2536)
raise AttributeError(dummy_error_message)
AttributeError: 'sage.symbolic.expression.Expression' object has no attribute 'ceil'

What am I doing wrong?

edit retag close merge delete

Sort by » oldest newest most voted

You're not doing anything wrong; it is Sage that is wrong.

Here L.closest_vector(u) causes L.voronoi_cell() to be called, which calls (if L._basis_is_LLL_reduced is False, first L.LLL()) the function calculate_voronoi_cell(basis=L.reduced_basis, radius=None) which is located in sage.modules.diamond_cutting. Here we find the problem:

max(abs(v) for v in basis).ceil()


This code assumes that the result of max(abs(v) for v in basis) has a method called ceil(). This would be true for ordinary numbers as in your first example, but not for symbolic expressions such as sqrt(2) which appears in your second example.

The solution is to fix this part of Sage's code, e.g. replace the expression by:

max(abs(v).n() for v in basis).ceil()


To get this fix into Sage (for everyone to enjoy) a trac ticket should be opened for this problem and solution.

more

Great! In the meantime is there a way for me to make the code run properly? I confess that I don't know how to "fix parts of Sage's code."

( 2018-12-02 12:53:00 -0500 )edit

In your local installation you can find the code I mentioned in src/sage/modules/diamond_cutting.py; search for calculate_voronoi_celland in there you can make the change I proposed. Here is the offending line: https://github.com/sagemath/sage/blob... Run sage -br to rebuild, for the change to take effect.

( 2018-12-02 13:52:42 -0500 )edit

Thanks! This change fixed the simple example in the original post, but some more complicated examples still give me errors. For instance, sage: L = IntegerLattice([[1,-1,0,0,0,0],[0,1,-1,0,0,0],[0,0,1,1,-1,-1],[0,0,1,-1,1,-1],[1,1,1,1,1,1]]) sage: L.closest_vector([0,0,0,0,0,0]) gives the error ValueError: math domain error

( 2018-12-02 16:20:01 -0500 )edit

This time the problem is in the function diamond_cut in the same file, namely in the line Z = sqrt(T[i] / q[i][i]): the argument of sqrt becomes negative and very tiny (for your example input) at some point in the algorithm. This function is being called from calculate_voronoi_cell as V = diamond_cut(Q, basis, radius, verbose=verbose). To get some more debug information, you can change verbose=verbose in this line to verbose=True. I'm not sure what the algorithm is doing, so I don't know how to fix it.

( 2018-12-02 16:46:29 -0500 )edit

Okay, I guess I should just treat the "discrete subgroups of Z^n" as a not-fully-implemented part of Sage. Honestly, for my purposes one of the main things I want to do is simply orthogonally project a vector onto a subspace spanned by the columns of a matrix, which is functionality Sage also seems not to have built-in anywhere I can find it.

( 2018-12-02 16:50:56 -0500 )edit