ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 03 Dec 2018 10:40:58 +0100Error in finding the closest vector in a sublattice of Z^nhttps://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/ 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
<pre>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)</pre>
yields the output
<pre>Free module of degree 3 and rank 2 over Integer Ring
User basis matrix:
[0 1 0]
[2 0 0]
(0, 0, 0)</pre>
as expected.
But the input
<pre>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)</pre>
yields the output
<pre>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'</pre>
What am I doing wrong?
Sat, 01 Dec 2018 23:23:08 +0100https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/Answer by rburing for <p>I'm trying to use the Sage package for discrete subgroups of Z^n.</p>
<p>But the "closest_vector()" function seems to be behaving incorrectly.</p>
<p>Here are some examples: The input</p>
<pre>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)</pre>
<p>yields the output</p>
<pre>Free module of degree 3 and rank 2 over Integer Ring
User basis matrix:
[0 1 0]
[2 0 0]
(0, 0, 0)</pre>
<p>as expected.</p>
<p>But the input</p>
<pre>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)</pre>
<p>yields the output</p>
<pre>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'</pre>
<p>What am I doing wrong?</p>
https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?answer=44533#post-id-44533You'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.Sun, 02 Dec 2018 19:39:33 +0100https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?answer=44533#post-id-44533Comment by rburing for <p>You're not doing anything wrong; it is Sage that is wrong.</p>
<p>Here <code>L.closest_vector(u)</code> causes <code>L.voronoi_cell()</code> to be called, which calls (if <code>L._basis_is_LLL_reduced</code> is <code>False</code>, first <code>L.LLL()</code>) the function <code>calculate_voronoi_cell(basis=L.reduced_basis, radius=None)</code> which is located in <code>sage.modules.diamond_cutting</code>. Here we find the problem:</p>
<pre><code>max(abs(v) for v in basis).ceil()
</code></pre>
<p>This code assumes that the result of <code>max(abs(v) for v in basis)</code> has a method called <code>ceil()</code>. This would be true for ordinary numbers as in your first example, but not for symbolic expressions such as <code>sqrt(2)</code> which appears in your second example.</p>
<p>The solution is to fix this part of Sage's code, e.g. replace the expression by:</p>
<pre><code>max(abs(v).n() for v in basis).ceil()
</code></pre>
<p>To get this fix into Sage (for everyone to enjoy) a trac ticket should be opened for this problem and solution.</p>
https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44539#post-id-44539This 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.Sun, 02 Dec 2018 23:46:29 +0100https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44539#post-id-44539Comment by Sam Hopkins for <p>You're not doing anything wrong; it is Sage that is wrong.</p>
<p>Here <code>L.closest_vector(u)</code> causes <code>L.voronoi_cell()</code> to be called, which calls (if <code>L._basis_is_LLL_reduced</code> is <code>False</code>, first <code>L.LLL()</code>) the function <code>calculate_voronoi_cell(basis=L.reduced_basis, radius=None)</code> which is located in <code>sage.modules.diamond_cutting</code>. Here we find the problem:</p>
<pre><code>max(abs(v) for v in basis).ceil()
</code></pre>
<p>This code assumes that the result of <code>max(abs(v) for v in basis)</code> has a method called <code>ceil()</code>. This would be true for ordinary numbers as in your first example, but not for symbolic expressions such as <code>sqrt(2)</code> which appears in your second example.</p>
<p>The solution is to fix this part of Sage's code, e.g. replace the expression by:</p>
<pre><code>max(abs(v).n() for v in basis).ceil()
</code></pre>
<p>To get this fix into Sage (for everyone to enjoy) a trac ticket should be opened for this problem and solution.</p>
https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44540#post-id-44540Okay, 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.Sun, 02 Dec 2018 23:50:56 +0100https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44540#post-id-44540Comment by rburing for <p>You're not doing anything wrong; it is Sage that is wrong.</p>
<p>Here <code>L.closest_vector(u)</code> causes <code>L.voronoi_cell()</code> to be called, which calls (if <code>L._basis_is_LLL_reduced</code> is <code>False</code>, first <code>L.LLL()</code>) the function <code>calculate_voronoi_cell(basis=L.reduced_basis, radius=None)</code> which is located in <code>sage.modules.diamond_cutting</code>. Here we find the problem:</p>
<pre><code>max(abs(v) for v in basis).ceil()
</code></pre>
<p>This code assumes that the result of <code>max(abs(v) for v in basis)</code> has a method called <code>ceil()</code>. This would be true for ordinary numbers as in your first example, but not for symbolic expressions such as <code>sqrt(2)</code> which appears in your second example.</p>
<p>The solution is to fix this part of Sage's code, e.g. replace the expression by:</p>
<pre><code>max(abs(v).n() for v in basis).ceil()
</code></pre>
<p>To get this fix into Sage (for everyone to enjoy) a trac ticket should be opened for this problem and solution.</p>
https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44541#post-id-44541The algorithm was [originally implemented by Jan Pöschko in 2012](http://gsoc-sage-lattices.blogspot.com/2012/07/voronoi-cells.html) based on the paper [Computing the Voronoi Cell of a Lattice: The Diamond-Cutting Algorithm](https://ecse.monash.edu/staff/eviterbo/papers/itjan96.pdf) by Emanuele Viterbo and Ezio Biglieri (1996). I don't have the time for it now, but the way to fix the code can probably be found by reading and understanding these resources.Mon, 03 Dec 2018 00:39:12 +0100https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44541#post-id-44541Comment by Sébastien for <p>You're not doing anything wrong; it is Sage that is wrong.</p>
<p>Here <code>L.closest_vector(u)</code> causes <code>L.voronoi_cell()</code> to be called, which calls (if <code>L._basis_is_LLL_reduced</code> is <code>False</code>, first <code>L.LLL()</code>) the function <code>calculate_voronoi_cell(basis=L.reduced_basis, radius=None)</code> which is located in <code>sage.modules.diamond_cutting</code>. Here we find the problem:</p>
<pre><code>max(abs(v) for v in basis).ceil()
</code></pre>
<p>This code assumes that the result of <code>max(abs(v) for v in basis)</code> has a method called <code>ceil()</code>. This would be true for ordinary numbers as in your first example, but not for symbolic expressions such as <code>sqrt(2)</code> which appears in your second example.</p>
<p>The solution is to fix this part of Sage's code, e.g. replace the expression by:</p>
<pre><code>max(abs(v).n() for v in basis).ceil()
</code></pre>
<p>To get this fix into Sage (for everyone to enjoy) a trac ticket should be opened for this problem and solution.</p>
https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44546#post-id-44546*"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."*
Orthogonal projection can be made with multiplication of matrices, and I think that you can multiply matrices in Sage. In the wikipedia page [Projection (linear algebra)](https://en.wikipedia.org/wiki/Projection_(linear_algebra)), you will find a formula of the form:
sage: P_A = A*(A.transpose()*A).inverse()*A.transpose()
which gives you a matrix which does the orthogonal projection with respect to the column of the matrix A.Mon, 03 Dec 2018 10:40:58 +0100https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44546#post-id-44546Comment by Sam Hopkins for <p>You're not doing anything wrong; it is Sage that is wrong.</p>
<p>Here <code>L.closest_vector(u)</code> causes <code>L.voronoi_cell()</code> to be called, which calls (if <code>L._basis_is_LLL_reduced</code> is <code>False</code>, first <code>L.LLL()</code>) the function <code>calculate_voronoi_cell(basis=L.reduced_basis, radius=None)</code> which is located in <code>sage.modules.diamond_cutting</code>. Here we find the problem:</p>
<pre><code>max(abs(v) for v in basis).ceil()
</code></pre>
<p>This code assumes that the result of <code>max(abs(v) for v in basis)</code> has a method called <code>ceil()</code>. This would be true for ordinary numbers as in your first example, but not for symbolic expressions such as <code>sqrt(2)</code> which appears in your second example.</p>
<p>The solution is to fix this part of Sage's code, e.g. replace the expression by:</p>
<pre><code>max(abs(v).n() for v in basis).ceil()
</code></pre>
<p>To get this fix into Sage (for everyone to enjoy) a trac ticket should be opened for this problem and solution.</p>
https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44534#post-id-44534Great! 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."Sun, 02 Dec 2018 19:53:00 +0100https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44534#post-id-44534Comment by rburing for <p>You're not doing anything wrong; it is Sage that is wrong.</p>
<p>Here <code>L.closest_vector(u)</code> causes <code>L.voronoi_cell()</code> to be called, which calls (if <code>L._basis_is_LLL_reduced</code> is <code>False</code>, first <code>L.LLL()</code>) the function <code>calculate_voronoi_cell(basis=L.reduced_basis, radius=None)</code> which is located in <code>sage.modules.diamond_cutting</code>. Here we find the problem:</p>
<pre><code>max(abs(v) for v in basis).ceil()
</code></pre>
<p>This code assumes that the result of <code>max(abs(v) for v in basis)</code> has a method called <code>ceil()</code>. This would be true for ordinary numbers as in your first example, but not for symbolic expressions such as <code>sqrt(2)</code> which appears in your second example.</p>
<p>The solution is to fix this part of Sage's code, e.g. replace the expression by:</p>
<pre><code>max(abs(v).n() for v in basis).ceil()
</code></pre>
<p>To get this fix into Sage (for everyone to enjoy) a trac ticket should be opened for this problem and solution.</p>
https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44536#post-id-44536In your local installation you can find the code I mentioned in `src/sage/modules/diamond_cutting.py`; search for `calculate_voronoi_cell` and in there you can make the change I proposed. Here is the offending line: https://github.com/sagemath/sage/blob/6187d261eca3c980e575b53d1a31f580ba8cfdfd/src/sage/modules/diamond_cutting.py#L263 Run `sage -br` to rebuild, for the change to take effect.Sun, 02 Dec 2018 20:52:42 +0100https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44536#post-id-44536Comment by Sam Hopkins for <p>You're not doing anything wrong; it is Sage that is wrong.</p>
<p>Here <code>L.closest_vector(u)</code> causes <code>L.voronoi_cell()</code> to be called, which calls (if <code>L._basis_is_LLL_reduced</code> is <code>False</code>, first <code>L.LLL()</code>) the function <code>calculate_voronoi_cell(basis=L.reduced_basis, radius=None)</code> which is located in <code>sage.modules.diamond_cutting</code>. Here we find the problem:</p>
<pre><code>max(abs(v) for v in basis).ceil()
</code></pre>
<p>This code assumes that the result of <code>max(abs(v) for v in basis)</code> has a method called <code>ceil()</code>. This would be true for ordinary numbers as in your first example, but not for symbolic expressions such as <code>sqrt(2)</code> which appears in your second example.</p>
<p>The solution is to fix this part of Sage's code, e.g. replace the expression by:</p>
<pre><code>max(abs(v).n() for v in basis).ceil()
</code></pre>
<p>To get this fix into Sage (for everyone to enjoy) a trac ticket should be opened for this problem and solution.</p>
https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44537#post-id-44537Thanks! 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`Sun, 02 Dec 2018 23:20:01 +0100https://ask.sagemath.org/question/44532/error-in-finding-the-closest-vector-in-a-sublattice-of-zn/?comment=44537#post-id-44537