-
-
Notifications
You must be signed in to change notification settings - Fork 453
/
lattice_polytope.py
5731 lines (4690 loc) · 188 KB
/
lattice_polytope.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
r"""
Lattice and reflexive polytopes
This module provides tools for work with lattice and reflexive
polytopes. A *convex polytope* is the convex hull of finitely many
points in `\RR^n`. The dimension `n` of a
polytope is the smallest `n` such that the polytope can be
embedded in `\RR^n`.
A *lattice polytope* is a polytope whose vertices all have integer
coordinates.
If `L` is a lattice polytope, the dual polytope of
`L` is
.. MATH::
\{y \in \ZZ^n : x\cdot y \geq -1 \text{ all } x \in L\}
A *reflexive polytope* is a lattice polytope, such that its polar
is also a lattice polytope, i.e. it is bounded and has vertices with
integer coordinates.
This Sage module uses Package for Analyzing Lattice Polytopes
(PALP), which is a program written in C by Maximilian Kreuzer and
Harald Skarke, which is freely available under the GNU license
terms at http://hep.itp.tuwien.ac.at/~kreuzer/CY/. Moreover, PALP is
included standard with Sage.
PALP is described in the paper :arxiv:`math.SC/0204356`. Its distribution
also contains the application nef.x, which was created by Erwin
Riegler and computes nef-partitions and Hodge data for toric
complete intersections.
ACKNOWLEDGMENT: polytope.py module written by William Stein was
used as an example of organizing an interface between an external
program and Sage. William Stein also helped Andrey Novoseltsev with
debugging and tuning of this module.
Robert Bradshaw helped Andrey Novoseltsev to realize plot3d
function.
.. note::
IMPORTANT: PALP requires some parameters to be determined during
compilation time, i.e., the maximum dimension of polytopes, the
maximum number of points, etc. These limitations may lead to errors
during calls to different functions of these module. Currently, a
ValueError exception will be raised if the output of poly.x or
nef.x is empty or contains the exclamation mark. The error message
will contain the exact command that caused an error, the
description and vertices of the polytope, and the obtained output.
Data obtained from PALP and some other data is cached and most
returned values are immutable. In particular, you cannot change the
vertices of the polytope or their order after creation of the
polytope.
If you are going to work with large sets of data, take a look at
``all_*`` functions in this module. They precompute different data
for sequences of polynomials with a few runs of external programs.
This can significantly affect the time of future computations. You
can also use dump/load, but not all data will be stored (currently
only faces and the number of their internal and boundary points are
stored, in addition to polytope vertices and its polar).
AUTHORS:
- Andrey Novoseltsev (2007-01-11): initial version
- Andrey Novoseltsev (2007-01-15): ``all_*`` functions
- Andrey Novoseltsev (2008-04-01): second version, including:
- dual nef-partitions and necessary convex_hull and minkowski_sum
- built-in sequences of 2- and 3-dimensional reflexive polytopes
- plot3d, skeleton_show
- Andrey Novoseltsev (2009-08-26): dropped maximal dimension requirement
- Andrey Novoseltsev (2010-12-15): new version of nef-partitions
- Andrey Novoseltsev (2013-09-30): switch to PointCollection.
- Maximilian Kreuzer and Harald Skarke: authors of PALP (which was
also used to obtain the list of 3-dimensional reflexive polytopes)
- Erwin Riegler: the author of nef.x
"""
#*****************************************************************************
# Copyright (C) 2007-2013 Andrey Novoseltsev <novoselt@gmail.com>
# Copyright (C) 2007-2013 William Stein <wstein@gmail.com>
#
# Distributed under the terms of the GNU General Public License (GPL)
# as published by the Free Software Foundation; either version 2 of
# the License, or (at your option) any later version.
# http://www.gnu.org/licenses/
#*****************************************************************************
from __future__ import print_function, absolute_import
from sage.combinat.posets.posets import FinitePoset
from sage.geometry.hasse_diagram import Hasse_diagram_from_incidences
from sage.geometry.point_collection import PointCollection, is_PointCollection
from sage.geometry.toric_lattice import ToricLattice, is_ToricLattice
from sage.graphs.graph import DiGraph, Graph
from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
from sage.matrix.constructor import matrix
from sage.matrix.matrix import is_Matrix
from sage.misc.all import cached_method, tmp_filename
from sage.env import POLYTOPE_DATA_DIR
from sage.modules.all import vector, span
from sage.misc.superseded import deprecated_function_alias
from sage.plot.plot3d.index_face_set import IndexFaceSet
from sage.plot.plot3d.all import line3d, point3d
from sage.plot.plot3d.shapes2 import text3d
from sage.rings.all import Integer, ZZ, QQ
from sage.arith.all import gcd, lcm
from sage.sets.set import Set_generic
from sage.structure.all import Sequence
from sage.structure.sage_object import SageObject
from sage.numerical.mip import MixedIntegerLinearProgram
from copy import copy
import collections
from six.moves import copyreg
import os
import subprocess
from six import StringIO
from functools import reduce
class SetOfAllLatticePolytopesClass(Set_generic):
def _repr_(self):
r"""
Return a string representation.
TESTS::
sage: lattice_polytope.SetOfAllLatticePolytopesClass()._repr_()
'Set of all Lattice Polytopes'
"""
return "Set of all Lattice Polytopes"
def __call__(self, x):
r"""
TESTS::
sage: o = lattice_polytope.cross_polytope(3)
sage: lattice_polytope.SetOfAllLatticePolytopesClass().__call__(o)
3-d reflexive polytope in 3-d lattice M
"""
if isinstance(x, LatticePolytopeClass):
return x
raise TypeError
SetOfAllLatticePolytopes = SetOfAllLatticePolytopesClass()
def LatticePolytope(data, compute_vertices=True, n=0, lattice=None):
r"""
Construct a lattice polytope.
INPUT:
- ``data`` -- points spanning the lattice polytope, specified as one of:
* a :class:`point collection
<sage.geometry.point_collection.PointCollection>` (this is the
preferred input and it is the quickest and the most memory efficient
one);
* an iterable of iterables (for example, a list of vectors)
defining the point coordinates;
* a file with matrix data, opened for reading, or
* a filename of such a file, see :func:`read_palp_matrix` for the
file format;
- ``compute_vertices`` -- boolean (default: ``True``). If ``True``, the
convex hull of the given points will be computed for
determining vertices. Otherwise, the given points must be
vertices;
- ``n`` -- an integer (default: 0) if ``data`` is a name of a file,
that contains data blocks for several polytopes, the ``n``-th block
will be used;
- ``lattice`` -- the ambient lattice of the polytope. If not given, a
suitable lattice will be determined automatically, most likely the
:class:`toric lattice <sage.geometry.toric_lattice.ToricLatticeFactory>`
`M` of the appropriate dimension.
OUTPUT:
- a :class:`lattice polytope <LatticePolytopeClass>`.
EXAMPLES::
sage: points = [(1,0,0), (0,1,0), (0,0,1), (-1,0,0), (0,-1,0), (0,0,-1)]
sage: p = LatticePolytope(points)
sage: p
3-d reflexive polytope in 3-d lattice M
sage: p.vertices()
M( 1, 0, 0),
M( 0, 1, 0),
M( 0, 0, 1),
M(-1, 0, 0),
M( 0, -1, 0),
M( 0, 0, -1)
in 3-d lattice M
We draw a pretty picture of the polytope in 3-dimensional space::
sage: p.plot3d().show()
Now we add an extra point, which is in the interior of the
polytope...
::
sage: points.append((0,0,0))
sage: p = LatticePolytope(points)
sage: p.nvertices()
6
You can suppress vertex computation for speed but this can lead to
mistakes::
sage: p = LatticePolytope(points, compute_vertices=False)
...
sage: p.nvertices()
7
Given points must be in the lattice::
sage: LatticePolytope([[1/2], [3/2]])
Traceback (most recent call last):
...
ValueError: points
[[1/2], [3/2]]
are not in 1-d lattice M!
But it is OK to create polytopes of non-maximal dimension::
sage: p = LatticePolytope([(1,0,0), (0,1,0), (0,0,0),
....: (-1,0,0), (0,-1,0), (0,0,0), (0,0,0)])
sage: p
2-d lattice polytope in 3-d lattice M
sage: p.vertices()
M( 1, 0, 0),
M( 0, 1, 0),
M(-1, 0, 0),
M( 0, -1, 0)
in 3-d lattice M
An empty lattice polytope can be considered as well::
sage: p = LatticePolytope([], lattice=ToricLattice(3).dual()); p
-1-d lattice polytope in 3-d lattice M
sage: p.lattice_dim()
3
sage: p.npoints()
0
sage: p.nfacets()
0
sage: p.points()
Empty collection
in 3-d lattice M
sage: p.faces()
((-1-d lattice polytope in 3-d lattice M,),)
"""
if isinstance(data, LatticePolytopeClass):
data = data._vertices
compute_vertices = False
if (is_PointCollection(data) and
(lattice is None or lattice is data.module())):
return LatticePolytopeClass(data, compute_vertices)
if isinstance(data, str):
f = open(data)
skip_palp_matrix(f, n)
data = read_palp_matrix(data)
f.close()
if isinstance(data, (file, StringIO)):
data = read_palp_matrix(data)
if not is_PointCollection(data) and not isinstance(data, (list, tuple)):
try:
data = list(data)
except TypeError:
raise TypeError("cannot construct a polytope from\n%s" % data)
if lattice is None:
if not data:
raise ValueError("lattice must be given explicitly for "
"empty polytopes!")
try:
if is_ToricLattice(data[0].parent()):
lattice = data[0].parent()
except AttributeError:
pass
if lattice is None:
try:
lattice = ToricLattice(len(data[0])).dual()
except TypeError:
raise TypeError("cannot construct a polytope from\n%s" % data)
try:
data = tuple(map(lattice, data))
except TypeError:
raise ValueError("points\n%s\nare not in %s!" % (data, lattice))
for p in data:
p.set_immutable()
data = PointCollection(data, lattice)
return LatticePolytopeClass(data, compute_vertices)
copyreg.constructor(LatticePolytope) # "safe for unpickling"
def ReflexivePolytope(dim, n):
r"""
Return n-th reflexive polytope from the database of 2- or
3-dimensional reflexive polytopes.
.. note::
#. Numeration starts with zero: `0 \leq n \leq 15` for `{\rm dim} = 2`
and `0 \leq n \leq 4318` for `{\rm dim} = 3`.
#. During the first call, all reflexive polytopes of requested
dimension are loaded and cached for future use, so the first
call for 3-dimensional polytopes can take several seconds,
but all consecutive calls are fast.
#. Equivalent to ``ReflexivePolytopes(dim)[n]`` but checks bounds
first.
EXAMPLES: The 3rd 2-dimensional polytope is "the diamond:"
::
sage: ReflexivePolytope(2, 3)
2-d reflexive polytope #3 in 2-d lattice M
sage: lattice_polytope.ReflexivePolytope(2,3).vertices()
M( 1, 0),
M( 0, 1),
M( 0, -1),
M(-1, 0)
in 2-d lattice M
There are 16 reflexive polygons and numeration starts with 0::
sage: ReflexivePolytope(2,16)
Traceback (most recent call last):
...
ValueError: there are only 16 reflexive polygons!
It is not possible to load a 4-dimensional polytope in this way::
sage: ReflexivePolytope(4,16)
Traceback (most recent call last):
...
NotImplementedError: only 2- and 3-dimensional reflexive polytopes are available!
"""
if dim == 2:
if n > 15:
raise ValueError("there are only 16 reflexive polygons!")
return ReflexivePolytopes(2)[n]
elif dim == 3:
if n > 4318:
raise ValueError("there are only 4319 reflexive 3-polytopes!")
return ReflexivePolytopes(3)[n]
else:
raise NotImplementedError("only 2- and 3-dimensional reflexive polytopes are available!")
# Sequences of reflexive polytopes
_rp = [None]*4
def ReflexivePolytopes(dim):
r"""
Return the sequence of all 2- or 3-dimensional reflexive polytopes.
.. note::
During the first call the database is loaded and cached for
future use, so repetitive calls will return the same object in
memory.
:param dim: dimension of required reflexive polytopes
:type dim: 2 or 3
:rtype: list of lattice polytopes
EXAMPLES: There are 16 reflexive polygons::
sage: len(ReflexivePolytopes(2))
16
It is not possible to load 4-dimensional polytopes in this way::
sage: ReflexivePolytopes(4)
Traceback (most recent call last):
...
NotImplementedError: only 2- and 3-dimensional reflexive polytopes are available!
"""
global _rp
if dim not in [2, 3]:
raise NotImplementedError("only 2- and 3-dimensional reflexive polytopes are available!")
if _rp[dim] is None:
rp = read_all_polytopes(
os.path.join(POLYTOPE_DATA_DIR, "reflexive_polytopes_%dd" % dim))
for n, p in enumerate(rp):
# Data files have normal form of reflexive polytopes
p.normal_form.set_cache(p._vertices)
p.index.set_cache(n)
# Prevents dimension computation later
p._dim = dim
# Compute "fast" data in one call to PALP
all_polars(rp)
# Construction of all points via PALP takes more time after the switch
# to point collections, which is inconvenient for doctests and using
# reflexive polytopes in general, turn it off for now - there was no
# promise in documentation that points are precomputed.
# all_points(rp + [p._polar for p in rp])
# TODO: improve faces representation so that we can uncomment
# all_faces(rp)
# It adds ~10s for dim=3, which is a bit annoying to wait for.
_rp[dim] = rp
return _rp[dim]
def is_LatticePolytope(x):
r"""
Check if ``x`` is a lattice polytope.
INPUT:
- ``x`` -- anything.
OUTPUT:
- ``True`` if ``x`` is a :class:`lattice polytope <LatticePolytopeClass>`,
``False`` otherwise.
EXAMPLES::
sage: from sage.geometry.lattice_polytope import is_LatticePolytope
sage: is_LatticePolytope(1)
False
sage: p = LatticePolytope([(1,0), (0,1), (-1,-1)])
sage: p
2-d reflexive polytope #0 in 2-d lattice M
sage: is_LatticePolytope(p)
True
"""
return isinstance(x, LatticePolytopeClass)
class LatticePolytopeClass(SageObject, collections.Hashable):
r"""
Create a lattice polytope.
.. WARNING::
This class does not perform any checks of correctness of input nor
does it convert input into the standard representation. Use
:func:`LatticePolytope` to construct lattice polytopes.
Lattice polytopes are immutable, but they cache most of the returned values.
INPUT:
The input can be either:
- ``points`` -- :class:`~sage.geometry.point_collection.PointCollection`;
- ``compute_vertices`` -- boolean.
or (these parameters must be given as keywords):
- ``ambient`` -- ambient structure, this polytope *must be a face of*
``ambient``;
- ``ambient_vertex_indices`` -- increasing list or tuple of integers,
indices of vertices of ``ambient`` generating this polytope;
- ``ambient_facet_indices`` -- increasing list or tuple of integers,
indices of facets of ``ambient`` generating this polytope.
OUTPUT:
- lattice polytope.
.. NOTE::
Every polytope has an ambient structure. If it was not specified, it is
this polytope itself.
"""
def __init__(self, points=None, compute_vertices=None,
ambient=None, ambient_vertex_indices=None,
ambient_facet_indices=None):
r"""
Construct a lattice polytope.
See :func:`LatticePolytope` for documentation.
TESTS::
sage: LatticePolytope([(1,2,3), (4,5,6)]) # indirect test
1-d lattice polytope in 3-d lattice M
"""
if ambient is None:
self._ambient = self
self._vertices = points
if compute_vertices:
self._compute_dim(compute_vertices=True)
self._ambient_vertex_indices = tuple(range(self.nvertices()))
self._ambient_facet_indices = ()
else:
self._ambient = ambient
self._ambient_vertex_indices = tuple(ambient_vertex_indices)
self._ambient_facet_indices = tuple(ambient_facet_indices)
self._vertices = ambient.vertices(self._ambient_vertex_indices)
def __eq__(self, other):
r"""
Compare ``self`` with ``other``.
INPUT:
- ``other`` -- anything.
OUTPUT:
- ``True`` if ``other`` is a :class:`lattice polytope
<LatticePolytopeClass>` equal to ``self``, ``False`` otherwise.
.. NOTE::
Two lattice polytopes are equal if they have the same vertices
listed in the same order.
TESTS::
sage: p1 = LatticePolytope([(1,0), (0,1), (-1,-1)])
sage: p2 = LatticePolytope([(1,0), (0,1), (-1,-1)])
sage: p3 = LatticePolytope([(0,1), (1,0), (-1,-1)])
sage: p1 == p1
True
sage: p1 == p2
True
sage: p1 is p2
False
sage: p1 == p3
False
sage: p1 == 0
False
"""
return (isinstance(other, LatticePolytopeClass)
and self._vertices == other._vertices)
@cached_method
def __hash__(self):
r"""
Return the hash of ``self``.
OUTPUT:
- an integer.
TESTS::
sage: o = lattice_polytope.cross_polytope(3)
sage: hash(o) == hash(o)
True
"""
# FIXME: take into account other things that may be preset?..
return hash(self._vertices)
def __ne__(self, other):
r"""
Compare ``self`` with ``other``.
INPUT:
- ``other`` -- anything.
OUTPUT:
- ``False`` if ``other`` is a :class:`lattice polytope
<LatticePolytopeClass>` equal to ``self``, ``True`` otherwise.
.. NOTE::
Two lattice polytopes are if they have the same vertices listed in
the same order.
TESTS::
sage: p1 = LatticePolytope([(1,0), (0,1), (-1,-1)])
sage: p2 = LatticePolytope([(1,0), (0,1), (-1,-1)])
sage: p3 = LatticePolytope([(0,1), (1,0), (-1,-1)])
sage: p1 != p1
False
sage: p1 != p2
False
sage: p1 is p2
False
sage: p1 != p3
True
sage: p1 != 0
True
"""
return not (self == other)
def __reduce__(self):
r"""
Reduction function. Does not store data that can be relatively fast
recomputed.
TESTS::
sage: o = lattice_polytope.cross_polytope(3)
sage: o.vertices() == loads(o.dumps()).vertices()
True
"""
state = self.__dict__.copy()
state.pop('_vertices')
state.pop('_distances', None)
state.pop('_skeleton', None)
try:
state['_npoints'] = len(state['_points'])
state.pop('_points')
except KeyError:
pass
return (LatticePolytope, (self._vertices, None, False), state)
def __setstate__(self, state):
r"""
Restores the state of pickled polytope.
TESTS::
sage: o = lattice_polytope.cross_polytope(3)
sage: o.vertices() == loads(o.dumps()).vertices()
True
"""
self.__dict__.update(state)
def _compute_dim(self, compute_vertices):
r"""
Compute the dimension of this polytope and its vertices, if necessary.
If ``compute_vertices`` is ``True``, then ``self._vertices`` should
contain points whose convex hull will be computed and placed back into
``self._vertices``.
If the dimension of this polytope is not equal to its ambient dimension,
auxiliary polytope will be created and stored for using PALP commands.
TESTS::
sage: p = LatticePolytope(([1], [2], [3]), compute_vertices=False)
sage: p.vertices() # wrong, since these were not vertices
M(1),
M(2),
M(3)
in 1-d lattice M
sage: hasattr(p, "_dim")
False
sage: p._compute_dim(compute_vertices=True)
sage: p.vertices()
M(1),
M(3)
in 1-d lattice M
sage: p._dim
1
"""
if hasattr(self, "_dim"):
return
N = self.lattice()
points = self._vertices
if not points: # the empty lattice polytope
self._dim = -1
return
if compute_vertices and len(points) != len(points.set()):
points = []
for point in self._vertices:
if not point in points:
points.append(point)
# Still may not be vertices, but don't have repetitions.
self._vertices = PointCollection(points, N)
p0 = points[0]
points = [point - p0 for point in points]
H = N.submodule(points)
self._dim = H.rank()
if self._dim == 0:
self._vertices = PointCollection((p0, ), N)
elif self._dim == self.lattice_dim():
if compute_vertices:
points = [N(_) for _ in read_palp_matrix(self.poly_x("v")).columns()]
for point in points:
point.set_immutable()
self._vertices = PointCollection(points, N)
else:
# Setup auxiliary polytope and maps
H = H.saturation()
H_points = [H.coordinates(point) for point in points]
H_polytope = LatticePolytope(H_points, compute_vertices=True)
self._sublattice = H
self._sublattice_polytope = H_polytope
self._embedding_matrix = H.basis_matrix().transpose()
self._shift_vector = p0
if compute_vertices:
self._vertices = self._embed(H_polytope._vertices)
# In order to use facet normals obtained from subpolytopes, we
# need the following (see Trac #9188).
M = self._embedding_matrix
# Basis for the ambient space with spanned subspace in front
basis = M.columns() + M.integer_kernel().basis()
# Let's represent it as columns of a matrix
basis = matrix(basis).transpose()
# Absolute value helps to keep normals "inner"
self._dual_embedding_scale = abs(basis.det())
dualbasis = matrix(ZZ, self._dual_embedding_scale * basis.inverse())
self._dual_embedding_matrix = dualbasis.submatrix(0,0,M.ncols())
def _compute_facets(self):
r"""
Compute and cache equations of facets of ``self``.
TESTS::
sage: p = LatticePolytope([(1,0,0), (0,1,0), (-1,0,0), (0,-1,0)])
sage: p._compute_facets()
sage: p._facet_normals
N(-1, 1, 0),
N( 1, 1, 0),
N(-1, -1, 0),
N( 1, -1, 0)
in 3-d lattice N
"""
assert not hasattr(self, "_facet_normals")
if self.dim() == self.lattice_dim():
self._read_equations(self.poly_x("e"))
else:
sp = self._sublattice_polytope
N = self.dual_lattice()
normals = [N(_) for _ in sp.facet_normals() * self._dual_embedding_matrix]
for n in normals:
n.set_immutable()
self._facet_normals = PointCollection(normals, N)
self._facet_constants = (
sp.facet_constants() * self._dual_embedding_scale -
self._shift_vector * self._facet_normals)
self._facet_constants.set_immutable()
def _compute_hodge_numbers(self):
r"""
Compute Hodge numbers for the current nef_partitions.
This function (currently) always raises an exception directing to
use another way for computing Hodge numbers.
TESTS::
sage: o = lattice_polytope.cross_polytope(3)
sage: o._compute_hodge_numbers()
Traceback (most recent call last):
...
NotImplementedError: use nef_partitions(hodge_numbers=True)!
"""
raise NotImplementedError("use nef_partitions(hodge_numbers=True)!")
def _embed(self, data):
r"""
Embed given point(s) into the ambient space of this polytope.
INPUT:
- ``data`` - point or matrix of points (as columns) in the affine
subspace spanned by this polytope
OUTPUT: The same point(s) in the coordinates of the ambient space of
this polytope.
TESTS::
sage: o = lattice_polytope.cross_polytope(3)
sage: o._embed(o.vertices()) == o.vertices()
True
sage: m = matrix(ZZ, 3)
sage: m[0, 0] = 1
sage: m[1, 1] = 1
sage: p = o.affine_transform(m)
sage: p._embed((0,0))
M(1, 0, 0)
"""
if self.lattice_dim() == self.dim():
return data
M = self.lattice()
if is_PointCollection(data):
r = [M(self._embedding_matrix * point + self._shift_vector)
for point in data]
for point in r:
point.set_immutable()
return PointCollection(r, M)
elif is_Matrix(data):
r = self._embedding_matrix * data
for i, col in enumerate(r.columns(copy=False)):
r.set_column(i, col + self._shift_vector)
return r
else:
return M(self._embedding_matrix * vector(QQ, data) +
self._shift_vector)
def _latex_(self):
r"""
Return the latex representation of self.
OUTPUT:
- string
EXAMPLES:
Arbitrary lattice polytopes are printed as `\Delta^d`, where `d` is
the (actual) dimension of the polytope::
sage: LatticePolytope([(1,1), (0,0)])._latex_()
'\\Delta^{1}'
For 2- and 3-d reflexive polytopes the index in the internal database
appears as a subscript::
sage: print(ReflexivePolytope(2, 3)._latex_())
\Delta^{2}_{3}
"""
result = r"\Delta^{%d}" % self.dim()
if self.dim() in (2, 3) and self.is_reflexive():
result += "_{%d}" % self.index()
return result
def _palp(self, command, reduce_dimension=False):
r"""
Run ``command`` on vertices of this polytope.
Returns the output of ``command`` as a string.
.. note::
PALP cannot be called for polytopes that do not span the ambient space.
If you specify ``reduce_dimension=True`` argument, PALP will be
called for vertices of this polytope in some basis of the affine space
it spans.
TESTS::
sage: o = lattice_polytope.cross_polytope(3)
sage: o._palp("poly.x -f")
'M:7 6 N:27 8 Pic:17 Cor:0\n'
sage: print(o._palp("nef.x -f -N -p")) # random time information
M:27 8 N:7 6 codim=2 #part=5
H:[0] P:0 V:2 4 5 0sec 0cpu
H:[0] P:2 V:3 4 5 0sec 0cpu
H:[0] P:3 V:4 5 0sec 0cpu
np=3 d:1 p:1 0sec 0cpu
sage: p = LatticePolytope([[1]])
sage: p._palp("poly.x -f")
Traceback (most recent call last):
...
ValueError: Cannot run "poly.x -f" for the zero-dimensional polytope!
Polytope: 0-d lattice polytope in 1-d lattice M
sage: p = LatticePolytope([(1,0,0), (0,1,0), (-1,0,0), (0,-1,0)])
sage: p._palp("poly.x -f")
Traceback (most recent call last):
...
ValueError: Cannot run PALP for a 2-dimensional polytope in a 3-dimensional space!
sage: p._palp("poly.x -f", reduce_dimension=True)
'M:5 4 F:4\n'
"""
if self.dim() <= 0:
raise ValueError(("Cannot run \"%s\" for the zero-dimensional "
+ "polytope!\nPolytope: %s") % (command, self))
if self.dim() < self.lattice_dim() and not reduce_dimension:
raise ValueError(("Cannot run PALP for a %d-dimensional polytope " +
"in a %d-dimensional space!") % (self.dim(), self.lattice_dim()))
fn = _palp(command, [self], reduce_dimension)
with open(fn) as f:
result = f.read()
os.remove(fn)
if (not result or
"!" in result or
"failed." in result or
"increase" in result or
"Unable" in result):
lines = ["Error executing '%s' for the given polytope!" % command,
"Output:", result]
raise ValueError("\n".join(lines))
return result
def _pullback(self, data):
r"""
Pull back given point(s) to the affine subspace spanned by this polytope.
INPUT:
- ``data`` -- rational point or matrix of points (as columns) in the
ambient space
OUTPUT: The same point(s) in the coordinates of the affine subspace
space spanned by this polytope.
TESTS::
sage: o = lattice_polytope.cross_polytope(3)
sage: o._pullback(o.vertices().column_matrix()) == o.vertices().column_matrix()
True
sage: m = matrix(ZZ, 3)
sage: m[0, 0] = 1
sage: m[1, 1] = 1
sage: p = o.affine_transform(m)
sage: p._pullback((0, 0, 0))
[-1, 0]
"""
if self.lattice_dim() == self.dim():
return data
if data is self._vertices:
return self._sublattice_polytope._vertices
if is_PointCollection(data):
r = [self._pullback(point) for point in data]
for point in r:
point.set_immutable()
return PointCollection(r, self._sublattice)
if is_Matrix(data):
r = matrix([self._pullback(col)
for col in data.columns(copy=False)]).transpose()
return r
data = vector(QQ, data)
return self._sublattice.coordinates(data - self._shift_vector)
def _read_equations(self, data):
r"""
Read equations of facets/vertices of polar polytope from string or
file.
TESTS:
For a reflexive polytope construct the polar polytope::
sage: p = LatticePolytope([(1,0), (0,1), (-1,-1)])
sage: p.vertices()
M( 1, 0),
M( 0, 1),
M(-1, -1)
in 2-d lattice M
sage: s = p.poly_x("e")
sage: print(s)
3 2 Vertices of P-dual <-> Equations of P
2 -1
-1 2
-1 -1
sage: "_polar" in p.__dict__
False
sage: p._read_equations(s)
sage: p._polar._vertices
N( 2, -1),
N(-1, 2),
N(-1, -1)
in 2-d lattice N
For a non-reflexive polytope cache facet equations::
sage: p = LatticePolytope([(1,0), (0,2), (-1,-3 )])
sage: p.vertices()
M( 1, 0),
M( 0, 2),
M(-1, -3)
in 2-d lattice M
sage: "_facet_normals" in p.__dict__
False
sage: "_facet_constants" in p.__dict__
False
sage: s = p.poly_x("e")
sage: print(s)
3 2 Equations of P
5 -1 2
-2 -1 2
-3 2 3
sage: p._read_equations(s)
sage: p._facet_normals