Diamond cutting implementation#
AUTHORS:
Jan Poeschko (2012-07-02): initial version
- sage.modules.diamond_cutting.calculate_voronoi_cell(basis, radius=None, verbose=False)#
Calculate the Voronoi cell of the lattice defined by basis
INPUT:
basis
– embedded basis matrix of the latticeradius
– radius of basis vectors to considerverbose
– whether to print debug information
OUTPUT:
A
Polyhedron
instance.EXAMPLES:
sage: from sage.modules.diamond_cutting import calculate_voronoi_cell sage: V = calculate_voronoi_cell(matrix([[1, 0], [0, 1]])) sage: V.volume() 1
- sage.modules.diamond_cutting.diamond_cut(V, GM, C, verbose=False)#
Perform diamond cutting on polyhedron
V
with basis matrixGM
and radiusC
.INPUT:
V
– polyhedron to cut fromGM
– half of the basis matrix of the latticeC
– radius to use in cutting algorithmverbose
– (default:False
) whether to print debug information
OUTPUT:
A
Polyhedron
instance.EXAMPLES:
sage: from sage.modules.diamond_cutting import diamond_cut sage: V = Polyhedron([[0], [2]]) sage: GM = matrix([2]) sage: V = diamond_cut(V, GM, 4) sage: V.vertices() (A vertex at (2), A vertex at (0))
- sage.modules.diamond_cutting.jacobi(M)#
Compute the upper-triangular part of the Cholesky/Jacobi decomposition of the symmetric matrix
M
.Let \(M\) be a symmetric \(n \times n\)-matrix over a field \(F\). Let \(m_{i,j}\) denote the \((i,j)\)-th entry of \(M\) for any \(1 \leq i \leq n\) and \(1 \leq j \leq n\). Then, the upper-triangular part computed by this method is the upper-triangular \(n \times n\)-matrix \(Q\) whose \((i,j)\)-th entry \(q_{i,j}\) satisfies
\[\begin{split}q_{i,j} = \begin{cases} \frac{1}{q_{i,i}} \left( m_{i,j} - \sum_{r<i} q_{r,r} q_{r,i} q_{r,j} \right) & i < j, \\ a_{i,j} - \sum_{r<i} q_{r,r} q_{r,i}^2 & i = j, \\ 0 & i > j, \end{cases}\end{split}\]for all \(1 \leq i \leq n\) and \(1 \leq j \leq n\). (These equalities determine the entries of \(Q\) uniquely by recursion.) This matrix \(Q\) is defined for all \(M\) in a certain Zariski-dense open subset of the set of all \(n \times n\)-matrices.
Note
This should be a method of matrices.
EXAMPLES:
sage: from sage.modules.diamond_cutting import jacobi sage: jacobi(identity_matrix(3) * 4) [4 0 0] [0 4 0] [0 0 4] sage: def testall(M): ....: Q = jacobi(M) ....: for j in range(3): ....: for i in range(j): ....: if Q[i,j] * Q[i,i] != M[i,j] - sum(Q[r,i] * Q[r,j] * Q[r,r] for r in range(i)): ....: return False ....: for i in range(3): ....: if Q[i,i] != M[i,i] - sum(Q[r,i] ** 2 * Q[r,r] for r in range(i)): ....: return False ....: for j in range(i): ....: if Q[i,j] != 0: ....: return False ....: return True sage: M = Matrix(QQ, [[8,1,5], [1,6,0], [5,0,3]]) sage: Q = jacobi(M); Q [ 8 1/8 5/8] [ 0 47/8 -5/47] [ 0 0 -9/47] sage: testall(M) True sage: M = Matrix(QQ, [[3,6,-1,7],[6,9,8,5],[-1,8,2,4],[7,5,4,0]]) sage: testall(M) True
- sage.modules.diamond_cutting.plane_inequality(v)#
Return the inequality for points on the same side as the origin with respect to the plane through
v
normal tov
.EXAMPLES:
sage: from sage.modules.diamond_cutting import plane_inequality sage: ieq = plane_inequality([1, -1]); ieq [2, -1, 1] sage: ieq[0] + vector(ieq[1:]) * vector([1, -1]) 0