Ask Your Question
2

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

asked 2018-12-01 16:23:08 -0600

Sam Hopkins gravatar image

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
    return calculate_voronoi_cell(B, radius=radius)
  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 flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2018-12-02 12:39:33 -0600

updated 2018-12-02 12:41:13 -0600

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.

edit flag offensive delete link more

Comments

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."

Sam Hopkins gravatar imageSam Hopkins ( 2018-12-02 12:53:00 -0600 )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.

rburing gravatar imagerburing ( 2018-12-02 13:52:42 -0600 )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

Sam Hopkins gravatar imageSam Hopkins ( 2018-12-02 16:20:01 -0600 )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.

rburing gravatar imagerburing ( 2018-12-02 16:46:29 -0600 )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.

Sam Hopkins gravatar imageSam Hopkins ( 2018-12-02 16:50:56 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-12-01 16:23:08 -0600

Seen: 67 times

Last updated: Dec 02