Diamond cutting implementation#
AUTHORS:
Jan Poeschko (2012-07-02): initial version
- sage.modules.diamond_cutting.calculate_voronoi_cell(basis, radius=None, verbose=False)[source]#
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
>>> from sage.all import * >>> from sage.modules.diamond_cutting import calculate_voronoi_cell >>> V = calculate_voronoi_cell(matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]])) >>> V.volume() 1
- sage.modules.diamond_cutting.diamond_cut(V, GM, C, verbose=False)[source]#
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))
>>> from sage.all import * >>> from sage.modules.diamond_cutting import diamond_cut >>> V = Polyhedron([[Integer(0)], [Integer(2)]]) >>> GM = matrix([Integer(2)]) >>> V = diamond_cut(V, GM, Integer(4)) >>> V.vertices() (A vertex at (2), A vertex at (0))
- sage.modules.diamond_cutting.jacobi(M)[source]#
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
>>> from sage.all import * >>> from sage.modules.diamond_cutting import jacobi >>> jacobi(identity_matrix(Integer(3)) * Integer(4)) [4 0 0] [0 4 0] [0 0 4] >>> def testall(M): ... Q = jacobi(M) ... for j in range(Integer(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(Integer(3)): ... if Q[i,i] != M[i,i] - sum(Q[r,i] ** Integer(2) * Q[r,r] for r in range(i)): ... return False ... for j in range(i): ... if Q[i,j] != Integer(0): ... return False ... return True >>> M = Matrix(QQ, [[Integer(8),Integer(1),Integer(5)], [Integer(1),Integer(6),Integer(0)], [Integer(5),Integer(0),Integer(3)]]) >>> Q = jacobi(M); Q [ 8 1/8 5/8] [ 0 47/8 -5/47] [ 0 0 -9/47] >>> testall(M) True >>> M = Matrix(QQ, [[Integer(3),Integer(6),-Integer(1),Integer(7)],[Integer(6),Integer(9),Integer(8),Integer(5)],[-Integer(1),Integer(8),Integer(2),Integer(4)],[Integer(7),Integer(5),Integer(4),Integer(0)]]) >>> testall(M) True
- sage.modules.diamond_cutting.plane_inequality(v)[source]#
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
>>> from sage.all import * >>> from sage.modules.diamond_cutting import plane_inequality >>> ieq = plane_inequality([Integer(1), -Integer(1)]); ieq [2, -1, 1] >>> ieq[Integer(0)] + vector(ieq[Integer(1):]) * vector([Integer(1), -Integer(1)]) 0