r"""
Rational polyhedral fans
This module was designed as a part of the framework for toric varieties
(:mod:`~sage.schemes.toric.variety`,
:mod:`~sage.schemes.toric.fano_variety`). While the emphasis is on
complete full-dimensional fans, arbitrary fans are supported. Work
with distinct lattices. The default lattice is :class:`ToricLattice
<sage.geometry.toric_lattice.ToricLatticeFactory>` `N` of the appropriate
dimension. The only case when you must specify lattice explicitly is creation
of a 0-dimensional fan, where dimension of the ambient space cannot be
guessed.
A **rational polyhedral fan** is a *finite* collection of *strictly* convex
rational polyhedral cones, such that the intersection of any two cones of the
fan is a face of each of them and each face of each cone is also a cone of the
fan.
AUTHORS:
- Andrey Novoseltsev (2010-05-15): initial version.
- Andrey Novoseltsev (2010-06-17): substantial improvement during review by
Volker Braun.
EXAMPLES:
Use :func:`Fan` to construct fans "explicitly"::
sage: fan = Fan(cones=[(0,1), (1,2)],
... rays=[(1,0), (0,1), (-1,0)])
sage: fan
Rational polyhedral fan in 2-d lattice N
In addition to giving such lists of cones and rays you can also create cones
first using :func:`~sage.geometry.cone.Cone` and then combine them into a fan.
See the documentation of :func:`Fan` for details.
Instead of building a fan from scratch, for this tutorial we will use an easy
way to get two fans assosiated to :class:`lattice polytopes
<sage.geometry.lattice_polytope.LatticePolytopeClass>`: :func:`FaceFan` and
:func:`NormalFan`::
sage: fan1 = FaceFan(lattice_polytope.octahedron(3))
sage: fan2 = NormalFan(lattice_polytope.octahedron(3))
Given such "automatic" fans, you may wonder what are their rays and cones::
sage: fan1.rays()
(N(1, 0, 0), N(0, 1, 0), N(0, 0, 1),
N(-1, 0, 0), N(0, -1, 0), N(0, 0, -1))
sage: fan1.ray_matrix()
[ 1 0 0 -1 0 0]
[ 0 1 0 0 -1 0]
[ 0 0 1 0 0 -1]
sage: fan1.generating_cones()
(3-d cone of Rational polyhedral fan in 3-d lattice N,
3-d cone of Rational polyhedral fan in 3-d lattice N,
3-d cone of Rational polyhedral fan in 3-d lattice N,
3-d cone of Rational polyhedral fan in 3-d lattice N,
3-d cone of Rational polyhedral fan in 3-d lattice N,
3-d cone of Rational polyhedral fan in 3-d lattice N,
3-d cone of Rational polyhedral fan in 3-d lattice N,
3-d cone of Rational polyhedral fan in 3-d lattice N)
The last output is not very illuminating. Let's try to improve it::
sage: for cone in fan1: print cone.rays()
(N(1, 0, 0), N(0, 1, 0), N(0, 0, -1))
(N(0, 1, 0), N(-1, 0, 0), N(0, 0, -1))
(N(1, 0, 0), N(0, -1, 0), N(0, 0, -1))
(N(-1, 0, 0), N(0, -1, 0), N(0, 0, -1))
(N(1, 0, 0), N(0, 1, 0), N(0, 0, 1))
(N(0, 1, 0), N(0, 0, 1), N(-1, 0, 0))
(N(1, 0, 0), N(0, 0, 1), N(0, -1, 0))
(N(0, 0, 1), N(-1, 0, 0), N(0, -1, 0))
You can also do ::
sage: for cone in fan1: print cone.ambient_ray_indices()
(0, 1, 5)
(1, 3, 5)
(0, 4, 5)
(3, 4, 5)
(0, 1, 2)
(1, 2, 3)
(0, 2, 4)
(2, 3, 4)
to see indices of rays of the fan corresponding to each cone.
While the above cycles were over "cones in fan", it is obvious that we did not
get ALL the cones: every face of every cone in a fan must also be in the fan,
but all of the above cones were of dimension three. The reason for this
behaviour is that in many cases it is enough to work with generating cones of
the fan, i.e. cones which are not faces of bigger cones. When you do need to
work with lower dimensional cones, you can easily get access to them using
:meth:`~sage.geometry.fan.RationalPolyhedralFan.cones`::
sage: [cone.ambient_ray_indices() for cone in fan1.cones(2)]
[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (0, 4),
(2, 4), (3, 4), (1, 5), (3, 5), (4, 5), (0, 5)]
In fact, you don't have to type ``.cones``::
sage: [cone.ambient_ray_indices() for cone in fan1(2)]
[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (0, 4),
(2, 4), (3, 4), (1, 5), (3, 5), (4, 5), (0, 5)]
You may also need to know the inclusion relations between all of the cones of
the fan. In this case check out
:meth:`~sage.geometry.fan.RationalPolyhedralFan.cone_lattice`::
sage: L = fan1.cone_lattice()
sage: L
Finite poset containing 28 elements
sage: L.bottom()
0-d cone of Rational polyhedral fan in 3-d lattice N
sage: L.top()
Rational polyhedral fan in 3-d lattice N
sage: cone = L.level_sets()[2][0]
sage: cone
2-d cone of Rational polyhedral fan in 3-d lattice N
sage: L.hasse_diagram().neighbors(cone)
[3-d cone of Rational polyhedral fan in 3-d lattice N,
3-d cone of Rational polyhedral fan in 3-d lattice N,
1-d cone of Rational polyhedral fan in 3-d lattice N,
1-d cone of Rational polyhedral fan in 3-d lattice N]
Note, that while ``cone`` above seems to be a "cone", it is not::
sage: cone.rays()
Traceback (most recent call last):
...
AttributeError: 'FinitePoset_with_category.element_class' object has no attribute 'rays'
To get your hands on the "real" cone, you need to do one more step::
sage: cone = cone.element
sage: cone.rays()
(N(1, 0, 0), N(0, 1, 0))
You can check how "good" a fan is::
sage: fan1.is_complete()
True
sage: fan1.is_simplicial()
True
sage: fan1.is_smooth()
True
The face fan of the octahedron is really good! Time to remember that we have
also constructed its normal fan::
sage: fan2.is_complete()
True
sage: fan2.is_simplicial()
False
sage: fan2.is_smooth()
False
This one does have some "problems," but we can fix them::
sage: fan3 = fan2.make_simplicial()
sage: fan3.is_simplicial()
True
sage: fan3.is_smooth()
False
Note that we had to save the result of
:meth:`~sage.geometry.fan.RationalPolyhedralFan.make_simplicial` in a new fan.
Fans in Sage are immutable, so any operation that does change them constructs
a new fan.
We can also make ``fan3`` smooth, but it will take a bit more work::
sage: cube = lattice_polytope.octahedron(3).polar()
sage: sk = cube.skeleton_points(2)
sage: rays = [cube.point(p) for p in sk]
sage: fan4 = fan3.subdivide(new_rays=rays)
sage: fan4.is_smooth()
True
Let's see how "different" are ``fan2`` and ``fan4``::
sage: fan2.ngenerating_cones()
6
sage: fan2.nrays()
8
sage: fan4.ngenerating_cones()
48
sage: fan4.nrays()
26
Smoothness does not come for free!
Please take a look at the rest of the available functions below and their
complete descriptions. If you need any features that are missing, feel free to
suggest them. (Or implement them on your own and submit a patch to Sage for
inclusion!)
"""
import collections
import warnings
import copy
from sage.combinat.combination import Combinations
from sage.combinat.posets.posets import FinitePoset
from sage.geometry.cone import (Cone,
ConvexRationalPolyhedralCone,
IntegralRayCollection,
is_Cone,
normalize_rays)
from sage.geometry.hasse_diagram import Hasse_diagram_from_incidences
from sage.geometry.lattice_polytope import (LatticePolytope,
all_faces,
all_facet_equations)
from sage.geometry.toric_lattice import is_ToricLattice
from sage.geometry.toric_plotter import ToricPlotter
from sage.graphs.all import DiGraph
from sage.matrix.all import matrix
from sage.misc.all import cached_method, flatten, walltime, prod
from sage.misc.misc import deprecation
from sage.modules.all import vector
from sage.rings.all import QQ, RR, ZZ
from sage.structure.all import Sequence
from sage.structure.coerce import parent
def is_Fan(x):
r"""
Check if ``x`` is a Fan.
INPUT:
- ``x`` -- anything.
OUTPUT:
- ``True`` if ``x`` is a fan and ``False`` otherwise.
EXAMPLES::
sage: from sage.geometry.fan import is_Fan
sage: is_Fan(1)
False
sage: fan = FaceFan(lattice_polytope.octahedron(2))
sage: fan
Rational polyhedral fan in 2-d lattice N
sage: is_Fan(fan)
True
"""
return isinstance(x, RationalPolyhedralFan)
def Fan(cones, rays=None, lattice=None, check=True, normalize=True,
is_complete=None, discard_faces=False, **kwds):
r"""
Construct a rational polyhedral fan.
.. NOTE::
Approximate time to construct a fan consisting of `n` cones is `n^2/5`
seconds. That is half an hour for 100 cones. This time can be
significantly reduced in the future, but it is still likely to be
`\sim n^2` (with, say, `/500` instead of `/5`). If you know that your
input does form a valid fan, use ``check=False`` option to skip
consistency checks.
INPUT:
- ``cones`` -- list of either
:class:`Cone<sage.geometry.cone.ConvexRationalPolyhedralCone>` objects
or lists of integers interpreted as indices of generating rays in
``rays``. These must be only **maximal** cones of the fan, unless
``discard_faces=True`` option is specified;
- ``rays`` -- list of rays given as list or vectors convertible to the
rational extension of ``lattice``. If ``cones`` are given by
:class:`Cone<sage.geometry.cone.ConvexRationalPolyhedralCone>` objects
``rays`` may be determined automatically. You still may give them
explicitly to ensure a particular order of rays in the fan. In this case
you must list all rays that appear in ``cones``. You can give "extra"
ones if it is convenient (e.g. if you have a big list of rays for
several fans), but all "extra" rays will be discarded;
- ``lattice`` -- :class:`ToricLattice
<sage.geometry.toric_lattice.ToricLatticeFactory>`, `\ZZ^n`, or any
other object that behaves like these. If not specified, an attempt will
be made to determine an appropriate toric lattice automatically;
- ``check`` -- by default the input data will be checked for correctness
(e.g. that intersection of any two given cones is a face of each). If you
know for sure that the input is correct, you may significantly decrease
construction time using ``check=False`` option;
- ``normalize`` -- you can further speed up construction using
``normalize=False`` option. In this case ``cones`` must be a list of
**sorted** :class:`tuples` and ``rays`` must be immutable primitive
vectors in ``lattice``. In general, you should not use this option, it
is designed for code optimization and does not give as drastic
improvement in speed as the previous one;
- ``is_complete`` -- every fan can determine on its own if it is complete
or not, however it can take quite a bit of time for "big" fans with many
generating cones. On the other hand, in some situations it is known in
advance that a certain fan is complete. In this case you can pass
``is_complete=True`` option to speed up some computations. You may also
pass ``is_complete=False`` option, although it is less likely to be
beneficial. Of course, passing a wrong value can compromise the
integrity of data structures of the fan and lead to wrong results, so
you should be very careful if you decide to use this option;
- ``discard_faces`` -- by default, the fan constructor expects the list of
**maximal** cones. If you provide "extra" ones and leave ``check=True``
(default), an exception will be raised. If you provide "extra" cones and
set ``check=False``, you may get wrong results as assumptions on internal
data structures will be invalid. If you want the fan constructor to
select the maximal cones from the given input, you may provide
``discard_faces=True`` option (it works both for ``check=True`` and
``check=False``).
OUTPUT:
- a :class:`fan <RationalPolyhedralFan>`.
EXAMPLES:
Let's construct a fan corresponding to the projective plane in several
ways::
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(0,1), (-1,-1)])
sage: cone3 = Cone([(-1,-1), (1,0)])
sage: P2 = Fan([cone1, cone2, cone2])
Traceback (most recent call last):
...
ValueError: you have provided 3 cones, but only 2 of them are maximal!
Use discard_faces=True if you indeed need to construct a fan from
these cones.
Oops! There was a typo and ``cone2`` was listed twice as a generating cone
of the fan. If it was intentional (e.g. the list of cones was generated
automatically and it is possible that it contains repetitions or faces of
other cones), use ``discard_faces=True`` option::
sage: P2 = Fan([cone1, cone2, cone2], discard_faces=True)
sage: P2.ngenerating_cones()
2
However, in this case it was definitely a typo, since the fan of
`\mathbb{P}^2` has 3 maximal cones::
sage: P2 = Fan([cone1, cone2, cone3])
sage: P2.ngenerating_cones()
3
Looks better. An alternative way is ::
sage: rays = [(1,0), (0,1), (-1,-1)]
sage: cones = [(0,1), (1,2), (2,0)]
sage: P2a = Fan(cones, rays)
sage: P2a.ngenerating_cones()
3
sage: P2 == P2a
False
That may seem wrong, but it is not::
sage: P2.is_equivalent(P2a)
True
See :meth:`~RationalPolyhedralFan.is_equivalent` for details.
Yet another way to construct this fan is ::
sage: P2b = Fan(cones, rays, check=False)
sage: P2b.ngenerating_cones()
3
sage: P2a == P2b
True
If you try the above examples, you are likely to notice the difference in
speed, so when you are sure that everything is correct, it is a good idea
to use ``check=False`` option. On the other hand, it is usually **NOT** a
good idea to use ``normalize=False`` option::
sage: P2c = Fan(cones, rays, check=False, normalize=False)
Traceback (most recent call last):
...
AttributeError: 'tuple' object has no attribute 'parent'
Yet another way is to use functions :func:`FaceFan` and :func:`NormalFan`
to construct fans from :class:`lattice polytopes
<sage.geometry.lattice_polytope.LatticePolytopeClass>`.
We have not yet used ``lattice`` argument, since if was determined
automatically::
sage: P2.lattice()
2-d lattice N
sage: P2b.lattice()
2-d lattice N
However, it is necessary to specify it explicitly if you want to construct
a fan without rays or cones::
sage: Fan([], [])
Traceback (most recent call last):
...
ValueError: you must specify the lattice
when you construct a fan without rays and cones!
sage: F = Fan([], [], lattice=ToricLattice(2, "L"))
sage: F
Rational polyhedral fan in 2-d lattice L
sage: F.lattice_dim()
2
sage: F.dim()
0
"""
if "discard_warning" in kwds:
deprecation("discard_warning is deprecated, use discard_faces instead.",
"Sage Version 4.7.2")
discard_faces = not discard_warning
kwds.pop(discard_warning)
if kwds:
raise ValueError("unrecognized keywords: %s" % kwds)
if not check and not normalize and not discard_faces:
return RationalPolyhedralFan(cones, rays, lattice, is_complete)
if not isinstance(cones, list):
try:
cones = list(cones)
except TypeError:
raise TypeError(
"cones must be given as an iterable!"
"\nGot: %s" % cones)
if not cones:
if lattice is None:
if rays:
lattice = normalize_rays(rays, lattice)[0].parent()
else:
raise ValueError("you must specify the lattice when you "
"construct a fan without rays and cones!")
return RationalPolyhedralFan(cones=((), ), rays=(), lattice=lattice)
if is_Cone(cones[0]):
if lattice is None:
lattice = cones[0].lattice()
if check:
for cone in cones:
if cone.lattice() != lattice:
raise ValueError("cones belong to different lattices "
"(%s and %s), cannot determine the lattice of the "
"fan!" % (lattice, cone.lattice()))
for i, cone in enumerate(cones):
if cone.lattice() != lattice:
cones[i] = Cone(cone.rays(), lattice, check=False)
if check:
for cone in cones:
if not cone.is_strictly_convex():
raise ValueError(
"cones of a fan must be strictly convex!")
if len(cones) == 1:
cone = cones[0]
return RationalPolyhedralFan((tuple(range(cone.nrays())), ),
cone.rays(), lattice,
is_complete=lattice.dimension() == 0)
ray_set = set([])
for cone in cones:
ray_set.update(cone.rays())
if rays:
rays = normalize_rays(rays, lattice)
new_rays = []
for ray in rays:
if ray in ray_set and ray not in new_rays:
new_rays.append(ray)
if len(new_rays) != len(ray_set):
raise ValueError(
"if rays are given, they must include all rays of the fan!")
rays = new_rays
else:
rays = tuple(ray_set)
if check:
generating_cones = []
for cone in sorted(cones, key=lambda cone: cone.dim(),
reverse=True):
is_generating = True
for g_cone in generating_cones:
i_cone = cone.intersection(g_cone)
if i_cone.is_face_of(cone) and i_cone.is_face_of(g_cone):
if i_cone.dim() == cone.dim():
is_generating = False
break
else:
raise ValueError(
"these cones cannot belong to the same fan!"
"\nCone 1 rays: %s\nCone 2 rays: %s"
% (g_cone.rays(), cone.rays()))
if is_generating:
generating_cones.append(cone)
if len(cones) > len(generating_cones):
if discard_faces:
cones = generating_cones
else:
raise ValueError("you have provided %d cones, but only %d "
"of them are maximal! Use discard_faces=True if you "
"indeed need to construct a fan from these cones." %
(len(cones), len(generating_cones)))
elif discard_faces:
cones = _discard_faces(cones)
return RationalPolyhedralFan(
(tuple(sorted(rays.index(ray) for ray in cone.rays()))
for cone in cones), rays, lattice, is_complete)
rays = normalize_rays(rays, lattice)
for n, cone in enumerate(cones):
try:
cones[n] = sorted(cone)
except TypeError:
raise TypeError("cannot interpret %s as a cone!" % cone)
if not check and not discard_faces:
return RationalPolyhedralFan(cones, rays, lattice, is_complete)
return Fan((Cone([rays[n] for n in cone], lattice) for cone in cones),
rays, lattice, is_complete=is_complete,
discard_faces=discard_faces)
def FaceFan(polytope, lattice=None):
r"""
Construct the face fan of the given lattice ``polytope``.
INPUT:
- ``polytope`` -- :class:`lattice polytope
<sage.geometry.lattice_polytope.LatticePolytopeClass>`;
- ``lattice`` -- :class:`ToricLattice
<sage.geometry.toric_lattice.ToricLatticeFactory>`, `\ZZ^n`, or any
other object that behaves like these. If not specified, an attempt will
be made to determine an appropriate toric lattice automatically.
OUTPUT:
- :class:`rational polyhedral fan <RationalPolyhedralFan>`.
See also :func:`NormalFan`.
EXAMPLES:
Let's construct the fan corresponding to the product of two projective
lines::
sage: diamond = lattice_polytope.octahedron(2)
sage: P1xP1 = FaceFan(diamond)
sage: P1xP1.ray_matrix()
[ 1 0 -1 0]
[ 0 1 0 -1]
sage: for cone in P1xP1: print cone.rays()
(N(1, 0), N(0, -1))
(N(-1, 0), N(0, -1))
(N(1, 0), N(0, 1))
(N(0, 1), N(-1, 0))
"""
if any(d <= 0 for d in polytope.distances([0]*polytope.dim())):
raise ValueError("face fans are defined only for polytopes containing"
"the origin as an interior point!")
cones = (facet.vertices() for facet in polytope.facets())
rays = polytope.vertices().columns(copy=False)
fan = Fan(cones, rays, lattice=lattice, check=False)
fan._is_complete = polytope.dim() == polytope.ambient_dim()
return fan
def NormalFan(polytope, lattice=None):
r"""
Construct the normal fan of the given lattice ``polytope``.
INPUT:
- ``polytope`` -- :class:`lattice polytope
<sage.geometry.lattice_polytope.LatticePolytopeClass>`;
- ``lattice`` -- :class:`ToricLattice
<sage.geometry.toric_lattice.ToricLatticeFactory>`, `\ZZ^n`, or any
other object that behaves like these. If not specified, an attempt will
be made to determine an appropriate toric lattice automatically.
OUTPUT:
- :class:`rational polyhedral fan <RationalPolyhedralFan>`.
See also :func:`FaceFan`.
EXAMPLES:
Let's construct the fan corresponding to the product of two projective
lines::
sage: square = lattice_polytope.octahedron(2).polar()
sage: P1xP1 = NormalFan(square)
sage: P1xP1.ray_matrix()
[ 1 0 -1 0]
[ 0 1 0 -1]
sage: for cone in P1xP1: print cone.rays()
(N(1, 0), N(0, -1))
(N(-1, 0), N(0, -1))
(N(1, 0), N(0, 1))
(N(0, 1), N(-1, 0))
"""
rays = (polytope.facet_normal(i) for i in range(polytope.nfacets()))
cones = (vertex.facets() for vertex in polytope.faces(dim=0))
fan = Fan(cones, rays, lattice=lattice, check=False)
fan._is_complete = polytope.dim() == polytope.ambient_dim()
return fan
class Cone_of_fan(ConvexRationalPolyhedralCone):
r"""
Construct a cone belonging to a fan.
.. WARNING::
This class does not check that the input defines a valid cone of a
fan. You must not construct objects of this class directly.
In addition to all of the properties of "regular" :class:`cones
<sage.geometry.cone.ConvexRationalPolyhedralCone>`, such cones know their
relation to the fan.
INPUT:
- ``ambient`` -- fan whose cone is constructed;
- ``ambient_ray_indices`` -- increasing list or tuple of integers, indices
of rays of ``ambient`` generating this cone.
OUTPUT:
- cone of ``ambient``.
EXAMPLES:
The intended way to get objects of this class is the following::
sage: P1xP1 = FaceFan(lattice_polytope.octahedron(2))
sage: cone = P1xP1.generating_cone(0)
sage: cone
2-d cone of Rational polyhedral fan in 2-d lattice N
sage: cone.ambient_ray_indices()
(0, 3)
sage: cone.star_generator_indices()
(0,)
"""
def __init__(self, ambient, ambient_ray_indices):
r"""
See :class:`Cone_of_Fan` for documentation.
TESTS:
The following code is likely to construct an invalid object, we just
test that creation of cones of fans is working::
sage: P1xP1 = FaceFan(lattice_polytope.octahedron(2))
sage: cone = sage.geometry.fan.Cone_of_fan(P1xP1, (0,))
sage: cone
1-d cone of Rational polyhedral fan in 2-d lattice N
sage: TestSuite(cone).run()
"""
super(Cone_of_fan, self).__init__(
ambient=ambient, ambient_ray_indices=ambient_ray_indices)
self._is_strictly_convex = True
def _repr_(self):
r"""
Return a string representation of ``self``.
OUTPUT:
- string.
TESTS::
sage: P1xP1 = FaceFan(lattice_polytope.octahedron(2))
sage: cone = P1xP1.generating_cone(0)
sage: cone._repr_()
'2-d cone of Rational polyhedral fan in 2-d lattice N'
sage: cone.facets()[0]._repr_()
'1-d cone of Rational polyhedral fan in 2-d lattice N'
"""
return "%d-d cone of %s" % (self.dim(), self.ambient())
def star_generator_indices(self):
r"""
Return indices of generating cones of the "ambient fan" containing
``self``.
OUTPUT:
- increasing :class:`tuple` of integers.
EXAMPLES::
sage: P1xP1 = FaceFan(lattice_polytope.octahedron(2))
sage: cone = P1xP1.generating_cone(0)
sage: cone.star_generator_indices()
(0,)
TESTS:
A mistake in this function used to cause the problem reported in
Trac 9782. We check that now everything is working smoothly::
sage: f = Fan([(0, 2, 4),
... (0, 4, 5),
... (0, 3, 5),
... (0, 1, 3),
... (0, 1, 2),
... (2, 4, 6),
... (4, 5, 6),
... (3, 5, 6),
... (1, 3, 6),
... (1, 2, 6)],
... [(-1, 0, 0),
... (0, -1, 0),
... (0, 0, -1),
... (0, 0, 1),
... (0, 1, 2),
... (0, 1, 3),
... (1, 0, 4)])
sage: f.is_complete()
True
sage: X = ToricVariety(f)
sage: X.fan().is_complete()
True
"""
if "_star_generator_indices" not in self.__dict__:
fan = self.ambient()
sgi = set(range(fan.ngenerating_cones()))
for ray in self.ambient_ray_indices():
sgi.intersection_update(fan._ray_to_cones(ray))
self._star_generator_indices = tuple(sorted(sgi))
return self._star_generator_indices
def star_generators(self):
r"""
Return indices of generating cones of the "ambient fan" containing
``self``.
OUTPUT:
- increasing :class:`tuple` of integers.
EXAMPLES::
sage: P1xP1 = FaceFan(lattice_polytope.octahedron(2))
sage: cone = P1xP1.generating_cone(0)
sage: cone.star_generators()
(2-d cone of Rational polyhedral fan in 2-d lattice N,)
"""
if "_star_generators" not in self.__dict__:
self._star_generators = tuple(self.ambient().generating_cone(i)
for i in self.star_generator_indices())
return self._star_generators
class RationalPolyhedralFan(IntegralRayCollection,
collections.Callable,
collections.Container):
r"""
Create a rational polyhedral fan.
.. WARNING::
This class does not perform any checks of correctness of input nor
does it convert input into the standard representation. Use
:func:`Fan` to construct fans from "raw data" or :func:`FaceFan` and
:func:`NormalFan` to get fans associated to polytopes.
Fans are immutable, but they cache most of the returned values.
INPUT:
- ``cones`` -- list of generating cones of the fan, each cone given as a
list of indices of its generating rays in ``rays``;
- ``rays`` -- list of immutable primitive vectors in ``lattice``
consisting of exactly the rays of the fan (i.e. no "extra" ones);
- ``lattice`` -- :class:`ToricLattice
<sage.geometry.toric_lattice.ToricLatticeFactory>`, `\ZZ^n`, or any
other object that behaves like these. If ``None``, it will be determined
as :func:`parent` of the first ray. Of course, this cannot be done if
there are no rays, so in this case you must give an appropriate
``lattice`` directly.
- ``is_complete`` -- if given, must be ``True`` or ``False`` depending on
whether this fan is complete or not. By default, it will be determined
automatically if necessary.
OUTPUT:
- rational polyhedral fan.
"""
def __init__(self, cones, rays, lattice, is_complete=None):
r"""
See :class:`RationalPolyhedralFan` for documentation.
TESTS::
sage: v = vector([0,1])
sage: v.set_immutable()
sage: f = sage.geometry.fan.RationalPolyhedralFan(
... [(0,)], [v], None)
sage: f.rays()
((0, 1),)
sage: TestSuite(f).run()
sage: f = Fan([(0,)], [(0,1)])
sage: TestSuite(f).run()
"""
super(RationalPolyhedralFan, self).__init__(rays, lattice)
self._generating_cones = tuple(Cone_of_fan(self, c) for c in cones)
for i, cone in enumerate(self._generating_cones):
cone._star_generator_indices = (i,)
if is_complete is not None:
self._is_complete = is_complete
def __call__(self, dim=None, codim=None):
r"""
Return the specified cones of ``self``.
.. NOTE::
"Direct call" syntax is a synonym for :meth:`cones` method except
that in the case of no input parameters this function returns
just ``self``.
INPUT:
- ``dim`` -- dimension of the requested cones;
- ``codim`` -- codimension of the requested cones.
OUTPUT:
- cones of ``self`` of the specified (co)dimension if it was given,
otherwise ``self``.
TESTS::
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(-1,0)])
sage: fan = Fan([cone1, cone2])
sage: fan(1)
(1-d cone of Rational polyhedral fan in 2-d lattice N,
1-d cone of Rational polyhedral fan in 2-d lattice N,
1-d cone of Rational polyhedral fan in 2-d lattice N)
sage: fan(2)
(2-d cone of Rational polyhedral fan in 2-d lattice N,)
sage: fan(dim=2)
(2-d cone of Rational polyhedral fan in 2-d lattice N,)
sage: fan(codim=2)
(0-d cone of Rational polyhedral fan in 2-d lattice N,)
sage: fan(dim=1, codim=1)
Traceback (most recent call last):
...
ValueError: dimension and codimension
cannot be specified together!
sage: fan() is fan
True
"""
if dim is None and codim is None:
return self
else:
return self.cones(dim, codim)
def __cmp__(self, right):
r"""
Compare ``self`` and ``right``.
INPUT:
- ``right`` -- anything.
OUTPUT:
- 0 if ``right`` is also a fan, their rays are the same and stored in
the same order, and their generating cones are the same and stored
in the same order. 1 or -1 otherwise.
TESTS::
sage: f1 = Fan(cones=[(0,1), (1,2)],
... rays=[(1,0), (0,1), (-1, 0)],
... check=False)
sage: f2 = Fan(cones=[(1,2), (0,1)],
... rays=[(1,0), (0,1), (-1, 0)],
... check=False)
sage: f3 = Fan(cones=[(1,2), (0,1)],
... rays=[(1,0), (0,1), (-1, 0)],
... check=False)
sage: cmp(f1, f2)
1
sage: cmp(f2, f1)
-1
sage: cmp(f2, f3)
0
sage: f2 is f3
False
sage: cmp(f1, 1) * cmp(1, f1)
-1
"""
if is_Fan(right):
return cmp([self.rays(), self.generating_cones()],
[right.rays(), right.generating_cones()])
else:
return cmp(type(self), type(right))
def __contains__(self, cone):
r"""
Check if ``cone`` is equivalent to a cone of the fan.
See :meth:`_contains` (which is called by this function) for
documentation.
TESTS::
sage: cone1 = Cone([(0,-1), (1,0)])
sage: cone2 = Cone([(1,0), (0,1)])
sage: f = Fan([cone1, cone2])
sage: f.generating_cone(0) in f
True
sage: cone1 in f
True
sage: (1,1) in f # not a cone
False
sage: "Ceci n'est pas un cone" in f
False
"""
return self._contains(cone)
def __iter__(self):
r"""
Return an iterator over generating cones of ``self``.
OUTPUT:
- iterator.
TESTS::
sage: f = Fan(cones=[(0,1), (1,2)],
... rays=[(1,0), (0,1), (-1, 0)],
... check=False)
sage: for cone in f: print cone.rays()
(N(1, 0), N(0, 1))
(N(0, 1), N(-1, 0))
"""
return iter(self.generating_cones())
def _compute_cone_lattice(self):
r"""
Compute the cone lattice of ``self``.
See :meth:`cone_lattice` for documentation.
TESTS:
We use different algorithms depending on available information. One of
the common cases is a fan which is KNOWN to be complete, i.e. we do
not even need to check if it is complete.
sage: fan = FaceFan(lattice_polytope.octahedron(2))
sage: fan.cone_lattice() # indirect doctest
Finite poset containing 10 elements
These 10 elements are: 1 origin, 4 rays, 4 generating cones, 1 fan.
Another common case is the fan of faces of a single cone::
sage: quadrant = Cone([(1,0), (0,1)])
sage: fan = Fan([quadrant])
sage: fan.cone_lattice() # indirect doctest
Finite poset containing 5 elements
These 5 elements are: 1 origin, 2 rays, 1 generating cone, 1 fan.
Finally, we have "intermediate" fans which are incomplete but are
generated by more than one cone::
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(-1,0)])
sage: fan = Fan([cone1, cone2])
sage: fan.ray_matrix()
[ 0 1 -1]
[ 1 0 0]
sage: for cone in fan: print cone.ambient_ray_indices()
(0, 1)
(2,)
sage: L = fan.cone_lattice() # indirect doctest
sage: L
Finite poset containing 6 elements
Here we got 1 origin, 3 rays (one is a generating cone),
1 2-dimensional cone (a generating one), and 1 fan.
"""
def FanFace(rays, cones):
if not cones:
return self
if len(cones) == 1:
g_cone = self.generating_cone(cones[0])
if g_cone.ambient_ray_indices() == rays:
return g_cone
face = Cone_of_fan(ambient=self, ambient_ray_indices=rays)
face._star_generator_indices=cones
return face
if "_is_complete" in self.__dict__ and self._is_complete:
self._cone_lattice = Hasse_diagram_from_incidences(
self._ray_to_cones(),
(cone.ambient_ray_indices() for cone in self),
FanFace, key = id(self))
else:
L = DiGraph()
face_to_rays = dict()
rays_to_index = dict()
index_to_cones = []
index_to_cones.append(())
next_index = 1
for i, cone in enumerate(self):
L_cone = Cone(cone.rays(), lattice=self.lattice(),
check=False, normalize=False).face_lattice()
for f in L_cone:
f = f.element
f_rays = tuple(cone.ambient_ray_indices()[ray]
for ray in f.ambient_ray_indices())
face_to_rays[f] = f_rays
try:
f_index = rays_to_index[f_rays]
index_to_cones[f_index].append(i)
except KeyError:
f_index = next_index
next_index += 1
rays_to_index[f_rays] = f_index
index_to_cones.append([i])
for f,g in L_cone.cover_relations_iterator():
L.add_edge(rays_to_index[face_to_rays[f.element]],
rays_to_index[face_to_rays[g.element]])
L.add_edge(
rays_to_index[face_to_rays[L_cone.top().element]], 0)
new_order = L.topological_sort()
tail = [rays_to_index[gc.ambient_ray_indices()] for gc in self]
tail.append(0)
new_order = [n for n in new_order if n not in tail] + tail
head = [rays_to_index[()]]
head.extend(rays_to_index[(n,)] for n in range(self.nrays()))
new_order = head + [n for n in new_order if n not in head]
labels = dict()
for new, old in enumerate(new_order):
labels[old] = new
L.relabel(labels)
elements = [None] * next_index
for rays, index in rays_to_index.items():
elements[labels[index]] = FanFace(
rays, tuple(index_to_cones[index]))
elements[labels[0]] = FanFace(tuple(range(self.nrays())), ())
self._cone_lattice = FinitePoset(L, elements, key = id(self))
def _contains(self, cone):
r"""
Check if ``cone`` is equivalent to a cone of the fan.
This function is called by :meth:`__contains__` and :meth:`contains`
to ensure the same call depth for warning messages.
INPUT:
- ``cone`` -- anything.
OUTPUT:
- ``False`` if ``cone`` is not a cone or if ``cone`` is not
equivalent to a cone of the fan. ``True`` otherwise.
TESTS::
sage: cone1 = Cone([(0,-1), (1,0)])
sage: cone2 = Cone([(1,0), (0,1)])
sage: f = Fan([cone1, cone2])
sage: f._contains(cone1)
True
sage: f._contains((1,1)) # this is not a cone!
False
Note that the ambient fan of the cone does not matter::
sage: cone1_f = f.generating_cone(0)
sage: cone1_f is cone1
False
sage: cone1_f.is_equivalent(cone1)
True
sage: cone1 in Fan([cone1, cone2]) # not a cone of any particular fan
True
sage: cone1_f in Fan([cone1, cone2]) # belongs to different fan, but equivalent cone
True
"""
try:
self.embed(cone)
return True
except TypeError:
return False
except ValueError:
if not cone.lattice().is_submodule(self.lattice()):
warnings.warn("you have checked if a fan contains a cone "
"from another lattice, this is always False!",
stacklevel=3)
return False
def support_contains(self, *args):
r"""
Check if a point is contained in the support of the fan.
The support of a fan is the union of all cones of the fan. If
you want to know whether the fan contains a given cone, you
should use :meth:`contains` instead.
INPUT:
- ``*args`` -- an element of ``self.lattice()`` or something
that can be converted to it (for example, a list of
coordinates).
OUTPUT:
- ``True`` if ``point`` is contained in the support of the
fan, ``False`` otherwise.
TESTS::
sage: cone1 = Cone([(0,-1), (1,0)])
sage: cone2 = Cone([(1,0), (0,1)])
sage: f = Fan([cone1, cone2])
We check if some points are in this fan::
sage: f.support_contains(f.lattice()(1,0))
True
sage: f.support_contains(cone1) # a cone is not a point of the lattice
False
sage: f.support_contains((1,0))
True
sage: f.support_contains(1,1)
True
sage: f.support_contains((-1,0))
False
sage: f.support_contains(f.lattice().dual()(1,0)) #random output (warning)
False
sage: f.support_contains(f.lattice().dual()(1,0))
False
sage: f.support_contains(1)
False
sage: f.support_contains(0) # 0 converts to the origin in the lattice
True
sage: f.support_contains(1/2, sqrt(3))
True
sage: f.support_contains(-1/2, sqrt(3))
False
"""
if len(args)==1:
point = args[0]
else:
point = args
try:
point = self._ambient_space_point(point)
except TypeError, ex:
if str(ex).endswith("have incompatible lattices!"):
warnings.warn("you have checked if a fan contains a point "
"from an incompatible lattice, this is False!",
stacklevel=3)
return False
if self.is_complete():
return True
return any(point in cone for cone in self)
def cartesian_product(self, other, lattice=None):
r"""
Return the Cartesian product of ``self`` with ``other``.
INPUT:
- ``other`` -- a :class:`rational polyhedral fan
<sage.geometry.fan.RationalPolyhedralFan>`;
- ``lattice`` -- (optional) the ambient lattice for the
Cartesian product fan. By default, the direct sum of the
ambient lattices of ``self`` and ``other`` is constructed.
OUTPUT:
- a :class:`fan <RationalPolyhedralFan>` whose cones are all pairwise
Cartesian products of the cones of ``self`` and ``other``.
EXAMPLES::
sage: K = ToricLattice(1, 'K')
sage: fan1 = Fan([[0],[1]],[(1,),(-1,)], lattice=K)
sage: L = ToricLattice(2, 'L')
sage: fan2 = Fan(rays=[(1,0),(0,1),(-1,-1)],
... cones=[[0,1],[1,2],[2,0]], lattice=L)
sage: fan1.cartesian_product(fan2)
Rational polyhedral fan in 3-d lattice K+L
sage: _.ngenerating_cones()
6
"""
assert is_Fan(other)
rc = super(RationalPolyhedralFan, self).cartesian_product(
other, lattice)
self_cones = [cone.ambient_ray_indices() for cone in self]
n = self.nrays()
other_cones = [tuple(n + i for i in cone.ambient_ray_indices())
for cone in other]
new_cones = [c1 + c2 for c1 in self_cones for c2 in other_cones]
try:
return RationalPolyhedralFan(new_cones, rc.rays(), rc.lattice(),
self._is_complete and other._is_complete)
except AttributeError:
return RationalPolyhedralFan(new_cones, rc.rays(), rc.lattice())
def _latex_(self):
r"""
Return a LaTeX representation of ``self``.
OUTPUT:
- string.
TESTS::
sage: f = Fan(cones=[(0,1), (1,2)],
... rays=[(1,0), (0,1), (-1, 0)],
... check=False)
sage: f._latex_()
'\\Sigma^{2}'
"""
return r"\Sigma^{%s}" % self.lattice_dim()
def _ray_to_cones(self, i=None):
r"""
Return the set of generating cones containing the ``i``-th ray.
INPUT:
- ``i`` -- integer, index of a ray of ``self``.
OUTPUT:
- :class:`frozenset` of indices of generating cones of ``self``
containing the ``i``-th ray if ``i`` was given, :class:`tuple` of
these sets for all rays otherwise.
EXAMPLES::
sage: fan = FaceFan(lattice_polytope.octahedron(2))
sage: fan._ray_to_cones(0)
frozenset([0, 2])
sage: fan._ray_to_cones()
(frozenset([0, 2]), frozenset([2, 3]),
frozenset([1, 3]), frozenset([0, 1]))
"""
if "_ray_to_cones_tuple" not in self.__dict__:
ray_to_cones = []
for ray in self.rays():
ray_to_cones.append([])
for k, cone in enumerate(self):
for j in cone.ambient_ray_indices():
ray_to_cones[j].append(k)
self._ray_to_cones_tuple = tuple(frozenset(rtc)
for rtc in ray_to_cones)
if i is None:
return self._ray_to_cones_tuple
else:
return self._ray_to_cones_tuple[i]
def _repr_(self):
r"""
Return a string representation of ``self``.
OUTPUT:
- string.
TESTS::
sage: f = Fan(cones=[(0,1), (1,2)],
... rays=[(1,0), (0,1), (-1, 0)],
... check=False)
sage: f._repr_()
'Rational polyhedral fan in 2-d lattice N'
sage: f = Fan(cones=[(0,1), (1,2)],
... rays=[(1,0), (0,1), (-1, 0)],
... lattice=ZZ^2,
... check=False)
sage: f._repr_()
'Rational polyhedral fan in 2-d lattice'
"""
result = "Rational polyhedral fan in"
if is_ToricLattice(self.lattice()):
result += " %s" % self.lattice()
else:
result += " %d-d lattice" % self.lattice_dim()
return result
def _subdivide_palp(self, new_rays, verbose):
r"""
Subdivide ``self`` adding ``new_rays`` one by one.
INPUT:
- ``new_rays`` -- immutable primitive vectors in the lattice of
``self``;
- ``verbose`` -- if ``True``, some timing information will be printed.
OUTPUT:
- rational polyhedral fan.
.. NOTE::
All generating cones of ``self`` must be full-dimensional.
TESTS::
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(-1,0)])
sage: new_rays = sage.geometry.cone.normalize_rays([(1,1)], None)
sage: fan = Fan([cone1, cone2])
sage: fan._subdivide_palp(new_rays, True)
Traceback (most recent call last):
...
ValueError: PALP-subdividing can be used only for
fans whose generating cones are full-dimensional!
sage: fan = Fan([cone1])
sage: # Timing information will depend on your machine
sage: new_fan = fan._subdivide_palp(new_rays, True)
R:1/1 C:2 T:...(ms) T/new:...(ms) T/all:...(ms)
sage: new_fan.ray_matrix()
[1 0 1]
[0 1 1]
sage: for cone in new_fan: print cone.ambient_ray_indices()
(1, 2)
(0, 2)
We make sure that this function constructs cones with ordered ambient
ray indices (see Trac 9812)::
sage: C = Cone([(1,0,0), (0,1,0), (1,0,1), (0,1,1)])
sage: F = Fan([C]).make_simplicial()
sage: [cone.ambient_ray_indices() for cone in F]
[(0, 2, 3), (0, 1, 3)]
"""
dim = self.lattice_dim()
for cone in self:
if cone.dim() != dim:
raise ValueError("PALP-subdividing can be used only for fans "
"whose generating cones are full-dimensional!")
cone_polytopes = [cone.lattice_polytope() for cone in self]
for cone_polytope in cone_polytopes:
cone_polytope._dim = dim
all_faces(cone_polytopes)
all_facet_equations(cone_polytopes)
for n, ray in enumerate(new_rays):
start = walltime()
old_polytopes = []
new_polytopes = []
for cone_polytope in cone_polytopes:
if (cone_polytope.nvertices() == dim + 1
and ray in cone_polytope.vertices().columns(copy=False)):
old_polytopes.append(cone_polytope)
continue
distances = cone_polytope.distances(ray)
cone_facets = cone_polytope.faces(dim=0)[-1].facets()
if all(distances[fn] >= 0 for fn in cone_facets):
vertices = cone_polytope.vertices().columns(copy=False)
for fn in cone_facets:
if distances[fn] > 0:
new_v = [vertices[v] for v in
cone_polytope.facets()[fn].vertices()]
new_v.insert(-1, ray)
new_v = matrix(ZZ, new_v).transpose()
new_polytope = LatticePolytope(new_v,
copy_vertices=False, compute_vertices=False)
new_polytope._dim = dim
new_polytopes.append(new_polytope)
else:
old_polytopes.append(cone_polytope)
all_faces(new_polytopes)
all_facet_equations(new_polytopes)
cone_polytopes = old_polytopes + new_polytopes
if verbose:
t = walltime(start)
T_new = ("%d" % (t / len(new_polytopes) * 1000)
if new_polytopes else "-")
print("R:%d/%d C:%d T:%d(ms) T/new:%s(ms) T/all:%d(ms)"
% (n + 1, len(new_rays), len(cone_polytopes), t * 1000,
T_new, t / len(cone_polytopes) * 1000))
new_fan_rays = list(self.rays())
new_fan_rays.extend(ray for ray in new_rays
if ray not in self.ray_set())
cones = tuple(tuple(sorted(new_fan_rays.index(cone_polytope.vertex(v))
for v in range(cone_polytope.nvertices() - 1)))
for cone_polytope in cone_polytopes)
fan = Fan(cones, new_fan_rays, check=False, normalize=False)
return fan
def cone_containing(self, *points):
r"""
Return the smallest cone of ``self`` containing all given points.
INPUT:
- either one or more indices of rays of ``self``, or one or more
objects representing points of the ambient space of ``self``, or a
list of such objects (you CANNOT give a list of indices).
OUTPUT:
- A :class:`cone of fan <Cone_of_fan>` whose ambient fan is
``self``.
.. NOTE::
We think of the origin as of the smallest cone containing no rays
at all. If there is no ray in ``self`` that contains all ``rays``,
a ``ValueError`` exception will be raised.
EXAMPLES::
sage: cone1 = Cone([(0,-1), (1,0)])
sage: cone2 = Cone([(1,0), (0,1)])
sage: f = Fan([cone1, cone2])
sage: f.rays()
(N(0, 1), N(0, -1), N(1, 0))
sage: f.cone_containing(0) # ray index
1-d cone of Rational polyhedral fan in 2-d lattice N
sage: f.cone_containing(0, 1) # ray indices
Traceback (most recent call last):
...
ValueError: there is no cone in
Rational polyhedral fan in 2-d lattice N
containing all of the given rays! Rays: (N(0, 1), N(0, -1))
sage: f.cone_containing(0, 2) # ray indices
2-d cone of Rational polyhedral fan in 2-d lattice N
sage: f.cone_containing((0,1)) # point
1-d cone of Rational polyhedral fan in 2-d lattice N
sage: f.cone_containing([(0,1)]) # point
1-d cone of Rational polyhedral fan in 2-d lattice N
sage: f.cone_containing((1,1))
2-d cone of Rational polyhedral fan in 2-d lattice N
sage: f.cone_containing((1,1), (1,0))
2-d cone of Rational polyhedral fan in 2-d lattice N
sage: f.cone_containing()
0-d cone of Rational polyhedral fan in 2-d lattice N
sage: f.cone_containing((0,0))
0-d cone of Rational polyhedral fan in 2-d lattice N
sage: f.cone_containing((-1,1))
Traceback (most recent call last):
...
ValueError: there is no cone in
Rational polyhedral fan in 2-d lattice N
containing all of the given points! Points: [N(-1, 1)]
TESTS::
sage: fan = Fan(cones=[(0,1,2,3), (0,1,4)],
... rays=[(1,1,1), (1,-1,1), (1,-1,-1), (1,1,-1), (0,0,1)])
sage: fan.cone_containing(0).rays()
(N(1, 1, 1),)
"""
if not points:
return self.cones(dim=0)[0]
try:
rays = map(int, points)
generating_cones = set(range(self.ngenerating_cones()))
for ray in rays:
generating_cones.intersection_update(self._ray_to_cones(ray))
if not generating_cones:
raise ValueError("there is no cone in %s containing all of "
"the given rays! Rays: %s" % (self, self.rays(rays)))
containing_cone = self.generating_cone(generating_cones.pop())
for cone in generating_cones:
containing_cone = containing_cone.intersection(
self.generating_cone(cone))
if not self.is_complete():
rays = frozenset(rays)
facets = containing_cone.facets()
for facet in facets:
if rays.issubset(facet._ambient_ray_indices):
containing_cone = containing_cone.intersection(facet)
return containing_cone
except TypeError:
try:
points = map(self._ambient_space_point, points)
except TypeError:
if len(points) == 1:
points = map(self._ambient_space_point, points[0])
else:
raise
containing_cone = None
for cone in self:
contains_all = True
for point in points:
if point not in cone:
contains_all = False
break
if contains_all:
containing_cone = cone
break
if containing_cone is None:
raise ValueError("there is no cone in %s containing all of "
"the given points! Points: %s" % (self, points))
facets = containing_cone.facets()
for facet in facets:
contains_all = True
for point in points:
if point not in facet:
contains_all = False
break
if contains_all:
containing_cone = containing_cone.intersection(facet)
return containing_cone
def cone_lattice(self):
r"""
Return the cone lattice of ``self``.
This lattice will have the origin as the bottom (we do not include the
empty set as a cone) and the fan itself as the top.
OUTPUT:
- :class:`finite poset <sage.combinat.posets.posets.FinitePoset` of
:class:`cones of fan<Cone_of_fan>`, behaving like "regular" cones,
but also containing the information about their relation to this
fan, namely, the contained rays and containing generating cones. The
top of the lattice will be this fan itself (*which is not a*
:class:`cone of fan<Cone_of_fan>`).
See also :meth:`cones`.
EXAMPLES:
Cone lattices can be computed for arbitrary fans::
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(-1,0)])
sage: fan = Fan([cone1, cone2])
sage: fan.ray_matrix()
[ 0 1 -1]
[ 1 0 0]
sage: for cone in fan: print cone.ambient_ray_indices()
(0, 1)
(2,)
sage: L = fan.cone_lattice()
sage: L
Finite poset containing 6 elements
These 6 elements are the origin, three rays, one two-dimensional
cone, and the fan itself\ . Since we do add the fan itself as the
largest face, you should be a little bit careful with this last
element::
sage: for face in L: print face.element.ambient_ray_indices()
Traceback (most recent call last):
...
AttributeError: 'RationalPolyhedralFan'
object has no attribute 'ambient_ray_indices'
sage: L.top()
Rational polyhedral fan in 2-d lattice N
For example, you can do ::
sage: for l in L.level_sets()[:-1]:
... print [f.element.ambient_ray_indices() for f in l]
[()]
[(0,), (1,), (2,)]
[(0, 1)]
If the fan is complete, its cone lattice is atomic and coatomic and
can (and will!) be computed in a much more efficient way, but the
interface is exactly the same::
sage: fan = FaceFan(lattice_polytope.octahedron(2))
sage: L = fan.cone_lattice()
sage: for l in L.level_sets()[:-1]:
... print [f.element.ambient_ray_indices() for f in l]
[()]
[(0,), (1,), (2,), (3,)]
[(0, 1), (1, 2), (0, 3), (2, 3)]
Let's also consider the cone lattice of a fan generated by a single
cone::
sage: fan = Fan([cone1])
sage: L = fan.cone_lattice()
sage: L
Finite poset containing 5 elements
Here these 5 elements correspond to the origin, two rays, one
generating cone of dimension two, and the whole fan. While this single
cone "is" the whole fan, it is consistent and convenient to
distinguish them in the cone lattice.
"""
if "_cone_lattice" not in self.__dict__:
self._compute_cone_lattice()
return self._cone_lattice
_face_lattice_function = cone_lattice
def __getstate__(self):
r"""
Return the dictionary that should be pickled.
OUTPUT:
- :class:`dict`.
TESTS::
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(-1,0)])
sage: fan = Fan([cone1, cone2])
sage: fan.cone_lattice()
Finite poset containing 6 elements
sage: fan._test_pickling()
"""
state = copy.copy(self.__dict__)
state.pop("_cone_lattice", None)
return state
def cones(self, dim=None, codim=None):
r"""
Return the specified cones of ``self``.
INPUT:
- ``dim`` -- dimension of the requested cones;
- ``codim`` -- codimension of the requested cones.
.. NOTE::
You can specify at most one input parameter.
OUTPUT:
- :class:`tuple` of cones of ``self`` of the specified (co)dimension,
if either ``dim`` or ``codim`` is given. Otherwise :class:`tuple` of
such tuples for all existing dimensions.
EXAMPLES::
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(-1,0)])
sage: fan = Fan([cone1, cone2])
sage: fan(dim=0)
(0-d cone of Rational polyhedral fan in 2-d lattice N,)
sage: fan(codim=2)
(0-d cone of Rational polyhedral fan in 2-d lattice N,)
sage: for cone in fan.cones(1): cone.ray(0)
N(0, 1)
N(1, 0)
N(-1, 0)
sage: fan.cones(2)
(2-d cone of Rational polyhedral fan in 2-d lattice N,)
You cannot specify both dimension and codimension, even if they
"agree"::
sage: fan(dim=1, codim=1)
Traceback (most recent call last):
...
ValueError: dimension and codimension
cannot be specified together!
But it is OK to ask for cones of too high or low (co)dimension::
sage: fan(-1)
()
sage: fan(3)
()
sage: fan(codim=4)
()
"""
if "_cones" not in self.__dict__:
levels = [(e.element for e in level)
for level in self.cone_lattice().level_sets()]
levels.pop()
if len(levels) >= 3:
top_cones = list(levels[-1])
if len(top_cones) == self.ngenerating_cones():
top_cones.sort(key=lambda cone:
cone.star_generator_indices()[0])
levels[-1] = top_cones
if len(levels) >= 2:
rays = list(levels[1])
rays.sort(key=lambda cone: cone.ambient_ray_indices()[0])
levels[1] = rays
self._cones = tuple(tuple(level) for level in levels)
if dim is None:
if codim is None:
return self._cones
dim = self.dim() - codim
elif codim is not None:
raise ValueError(
"dimension and codimension cannot be specified together!")
return self._cones[dim] if 0 <= dim < len(self._cones) else ()
def contains(self, cone):
r"""
Check if a given ``cone`` is equivalent to a cone of the fan.
INPUT:
- ``cone`` -- anything.
OUTPUT:
- ``False`` if ``cone`` is not a cone or if ``cone`` is not
equivalent to a cone of the fan. ``True`` otherwise.
.. NOTE::
Recall that a fan is a (finite) collection of cones. A
cone is contained in a fan if it is equivalent to one of
the cones of the fan. In particular, it is possible that
all rays of the cone are in the fan, but the cone itself
is not.
If you want to know whether a point is in the support of
the fan, you should use :meth:`support_contains`.
EXAMPLES:
We first construct a simple fan::
sage: cone1 = Cone([(0,-1), (1,0)])
sage: cone2 = Cone([(1,0), (0,1)])
sage: f = Fan([cone1, cone2])
Now we check if some cones are in this fan. First, we make sure that
the order of rays of the input cone does not matter (``check=False``
option ensures that rays of these cones will be listed exactly as they
are given)::
sage: f.contains(Cone([(1,0), (0,1)], check=False))
True
sage: f.contains(Cone([(0,1), (1,0)], check=False))
True
Now we check that a non-generating cone is in our fan::
sage: f.contains(Cone([(1,0)]))
True
sage: Cone([(1,0)]) in f # equivalent to the previous command
True
Finally, we test some cones which are not in this fan::
sage: f.contains(Cone([(1,1)]))
False
sage: f.contains(Cone([(1,0), (-0,1)]))
True
A point is not a cone::
sage: n = f.lattice()(1,1); n
N(1, 1)
sage: f.contains(n)
False
"""
return self._contains(cone)
def embed(self, cone):
r"""
Return the cone equivalent to the given one, but sitting in ``self``.
You may need to use this method before calling methods of ``cone`` that
depend on the ambient structure, such as
:meth:`~sage.geometry.cone.ConvexRationalPolyhedralCone.ambient_ray_indices`
or
:meth:`~sage.geometry.cone.ConvexRationalPolyhedralCone.facet_of`. The
cone returned by this method will have ``self`` as ambient. If ``cone``
does not represent a valid cone of ``self``, ``ValueError`` exception
is raised.
.. NOTE::
This method is very quick if ``self`` is already the ambient
structure of ``cone``, so you can use without extra checks and
performance hit even if ``cone`` is likely to sit in ``self`` but
in principle may not.
INPUT:
- ``cone`` -- a :class:`cone
<sage.geometry.cone.ConvexRationalPolyhedralCone>`.
OUTPUT:
- a :class:`cone of fan <Cone_of_fan>`, equivalent to ``cone`` but
sitting inside ``self``.
EXAMPLES:
Let's take a 3-d fan generated by a cone on 4 rays::
sage: f = Fan([Cone([(1,0,1), (0,1,1), (-1,0,1), (0,-1,1)])])
Then any ray generates a 1-d cone of this fan, but if you construct
such a cone directly, it will not "sit" inside the fan::
sage: ray = Cone([(0,-1,1)])
sage: ray
1-d cone in 3-d lattice N
sage: ray.ambient_ray_indices()
(0,)
sage: ray.adjacent()
()
sage: ray.ambient()
1-d cone in 3-d lattice N
If we want to operate with this ray as a part of the fan, we need to
embed it first::
sage: e_ray = f.embed(ray)
sage: e_ray
1-d cone of Rational polyhedral fan in 3-d lattice N
sage: e_ray.rays()
(N(0, -1, 1),)
sage: e_ray is ray
False
sage: e_ray.is_equivalent(ray)
True
sage: e_ray.ambient_ray_indices()
(3,)
sage: e_ray.adjacent()
(1-d cone of Rational polyhedral fan in 3-d lattice N,
1-d cone of Rational polyhedral fan in 3-d lattice N)
sage: e_ray.ambient()
Rational polyhedral fan in 3-d lattice N
Not every cone can be embedded into a fixed fan::
sage: f.embed(Cone([(0,0,1)]))
Traceback (most recent call last):
...
ValueError: 1-d cone in 3-d lattice N does not belong
to Rational polyhedral fan in 3-d lattice N!
sage: f.embed(Cone([(1,0,1), (-1,0,1)]))
Traceback (most recent call last):
...
ValueError: 2-d cone in 3-d lattice N does not belong
to Rational polyhedral fan in 3-d lattice N!
"""
if not is_Cone(cone):
raise TypeError("%s is not a cone!" % cone)
if cone.ambient() is self:
return cone
rays = self.rays()
try:
ray_indices = [rays.index(ray) for ray in cone.rays()]
result = self.cone_containing(*ray_indices)
if cone.nrays() != result.nrays():
raise ValueError
except ValueError:
raise ValueError("%s does not belong to %s!" % (cone, self))
return result
def Gale_transform(self):
r"""
Return the Gale transform of ``self``.
OUTPUT:
A matrix over `ZZ`.
EXAMPLES::
sage: fan = FaceFan(lattice_polytope.octahedron(2))
sage: fan.Gale_transform()
[ 1 0 1 0 -2]
[ 0 1 0 1 -2]
sage: _.base_ring()
Integer Ring
"""
if "_Gale_transform" not in self.__dict__:
m = self.ray_matrix().augment(matrix(self.lattice_dim(), 1))
m = m.stack(matrix([1]*m.ncols()))
self._Gale_transform = matrix(ZZ, m.transpose().integer_kernel().matrix())
return self._Gale_transform
def generating_cone(self, n):
r"""
Return the ``n``-th generating cone of ``self``.
INPUT:
- ``n`` -- integer, the index of a generating cone.
OUTPUT:
- :class:`cone of fan<Cone_of_fan>`.
EXAMPLES::
sage: fan = FaceFan(lattice_polytope.octahedron(2))
sage: fan.generating_cone(0)
2-d cone of Rational polyhedral fan in 2-d lattice N
"""
return self._generating_cones[n]
def generating_cones(self):
r"""
Return generating cones of ``self``.
OUTPUT:
- :class:`tuple` of :class:`cones of fan<Cone_of_fan>`.
EXAMPLES::
sage: fan = FaceFan(lattice_polytope.octahedron(2))
sage: fan.generating_cones()
(2-d cone of Rational polyhedral fan in 2-d lattice N,
2-d cone of Rational polyhedral fan in 2-d lattice N,
2-d cone of Rational polyhedral fan in 2-d lattice N,
2-d cone of Rational polyhedral fan in 2-d lattice N)
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(-1,0)])
sage: fan = Fan([cone1, cone2])
sage: fan.generating_cones()
(2-d cone of Rational polyhedral fan in 2-d lattice N,
1-d cone of Rational polyhedral fan in 2-d lattice N)
"""
return self._generating_cones
def is_complete(self):
r"""
Check if ``self`` is complete.
A rational polyhedral fan is *complete* if its cones fill the whole
space.
OUTPUT:
- ``True`` if ``self`` is complete and ``False`` otherwise.
EXAMPLES::
sage: fan = FaceFan(lattice_polytope.octahedron(2))
sage: fan.is_complete()
True
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(-1,0)])
sage: fan = Fan([cone1, cone2])
sage: fan.is_complete()
False
"""
if "_is_complete" in self.__dict__:
return self._is_complete
d = self.lattice_dim()
if self.dim() != d:
self._is_complete = False
return False
for cone in self:
if cone.dim() != d:
self._is_complete = False
return False
for cone in self(codim=1):
if len(cone.star_generator_indices()) != 2:
self._is_complete = False
return False
self._is_complete = True
return True
def is_equivalent(self, other):
r"""
Check if ``self`` is "mathematically" the same as ``other``.
INPUT:
- ``other`` - fan.
OUTPUT:
- ``True`` if ``self`` and ``other`` define the same fans as
collections of equivalent cones in the same lattice, ``False``
otherwise.
There are three different equivalences between fans `F_1` and `F_2`
in the same lattice:
#. They have the same rays in the same order and the same generating
cones in the same order.
This is tested by ``F1 == F2``.
#. They have the same rays and the same generating cones without
taking into account any order.
This is tested by ``F1.is_equivalent(F2)``.
#. They are in the same orbit of `GL(n,\ZZ)` (and, therefore,
correspond to isomorphic toric varieties).
This is tested by ``F1.is_isomorphic(F2)``.
EXAMPLES::
sage: fan1 = Fan(cones=[(0,1), (1,2)],
... rays=[(1,0), (0,1), (-1,-1)],
... check=False)
sage: fan2 = Fan(cones=[(2,1), (0,2)],
... rays=[(1,0), (-1,-1), (0,1)],
... check=False)
sage: fan3 = Fan(cones=[(0,1), (1,2)],
... rays=[(1,0), (0,1), (-1,1)],
... check=False)
sage: fan1 == fan2
False
sage: fan1.is_equivalent(fan2)
True
sage: fan1 == fan3
False
sage: fan1.is_equivalent(fan3)
False
"""
if (self.lattice() != other.lattice()
or self.dim() != other.dim()
or self.ngenerating_cones() != other.ngenerating_cones()
or self.ray_set() != other.ray_set()):
return False
return sorted(sorted(cone.rays()) for cone in self) \
== sorted(sorted(cone.rays()) for cone in other)
def is_isomorphic(self, other):
r"""
Check if ``self`` is in the same `GL(n, \ZZ)`-orbit as ``other``.
INPUT:
- ``other`` - fan.
OUTPUT:
- ``True`` if ``self`` and ``other`` are in the same
`GL(n, \ZZ)`-orbit, ``False`` otherwise.
There are three different equivalences between fans `F_1` and `F_2`
in the same lattice:
#. They have the same rays in the same order and the same generating
cones in the same order.
This is tested by ``F1 == F2``.
#. They have the same rays and the same generating cones without
taking into account any order.
This is tested by ``F1.is_equivalent(F2)``.
#. They are in the same orbit of `GL(n,\ZZ)` (and, therefore,
correspond to isomorphic toric varieties).
This is tested by ``F1.is_isomorphic(F2)``.
EXAMPLES:
These fans are "mirrors" of each other::
sage: fan1 = Fan(cones=[(0,1), (1,2)],
... rays=[(1,0), (0,1), (-1,-1)],
... check=False)
sage: fan2 = Fan(cones=[(0,1), (1,2)],
... rays=[(1,0), (0,-1), (-1,1)],
... check=False)
sage: fan1 == fan2
False
sage: fan1.is_equivalent(fan2)
False
sage: fan1.is_isomorphic(fan2)
Traceback (most recent call last):
...
NotImplementedError: fan isomorphism is not implemented yet!
"""
if self.lattice() != other.lattice():
return False
raise NotImplementedError("fan isomorphism is not implemented yet!")
def is_simplicial(self):
r"""
Check if ``self`` is simplicial.
A rational polyhedral fan is **simplicial** if all of its cones are,
i.e. primitive vectors along generating rays of every cone form a part
of a *rational* basis of the ambient space.
OUTPUT:
- ``True`` if ``self`` is simplicial and ``False`` otherwise.
EXAMPLES::
sage: fan = FaceFan(lattice_polytope.octahedron(2))
sage: fan.is_simplicial()
True
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(-1,0)])
sage: fan = Fan([cone1, cone2])
sage: fan.is_simplicial()
True
In fact, any fan in a two-dimensional ambient space is simplicial.
This is no longer the case in dimension three::
sage: fan = NormalFan(lattice_polytope.octahedron(3))
sage: fan.is_simplicial()
False
sage: fan.generating_cone(0).nrays()
4
"""
if "is_simplicial" not in self.__dict__:
self._is_simplicial = all(cone.is_simplicial() for cone in self)
return self._is_simplicial
@cached_method
def is_smooth(self, codim=None):
r"""
Check if ``self`` is smooth.
A rational polyhedral fan is **smooth** if all of its cones
are, i.e. primitive vectors along generating rays of every
cone form a part of an *integral* basis of the ambient
space. In this case the corresponding toric variety is smooth.
A fan in an `n`-dimensional lattice is smooth up to codimension `c`
if all cones of codimension greater than or equal to `c` are smooth,
i.e. if all cones of dimension less than or equal to `n-c` are smooth.
In this case the singular set of the corresponding toric variety is of
dimension less than `c`.
INPUT:
- ``codim`` -- codimension in which smoothness has to be checked, by
default complete smoothness will be checked.
OUTPUT:
- ``True`` if ``self`` is smooth (in codimension ``codim``, if it was
given) and ``False`` otherwise.
EXAMPLES::
sage: fan = FaceFan(lattice_polytope.octahedron(2))
sage: fan.is_smooth()
True
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(-1,0)])
sage: fan = Fan([cone1, cone2])
sage: fan.is_smooth()
True
sage: fan = NormalFan(lattice_polytope.octahedron(2))
sage: fan.is_smooth()
False
sage: fan.is_smooth(codim=1)
True
sage: fan.generating_cone(0).rays()
(N(-1, 1), N(-1, -1))
sage: fan.generating_cone(0).ray_matrix().det()
2
"""
if codim is None or codim < 0:
codim = 0
if codim > self.lattice_dim() - 2:
return True
return all(cone.is_smooth() for cone in self(codim=codim)) and \
self.is_smooth(codim + 1)
def make_simplicial(self, **kwds):
r"""
Construct a simplicial fan subdividing ``self``.
It is a synonym for :meth:`subdivide` with ``make_simplicial=True``
option.
INPUT:
- this functions accepts only keyword arguments. See :meth:`subdivide`
for documentation.
OUTPUT:
- :class:`rational polyhedral fan
<sage.geometry.fan.RationalPolyhedralFan>`.
EXAMPLES::
sage: fan = NormalFan(lattice_polytope.octahedron(3))
sage: fan.is_simplicial()
False
sage: fan.ngenerating_cones()
6
sage: new_fan = fan.make_simplicial()
sage: new_fan.is_simplicial()
True
sage: new_fan.ngenerating_cones()
12
"""
return self.subdivide(make_simplicial=True, **kwds)
def ngenerating_cones(self):
r"""
Return the number of generating cones of ``self``.
OUTPUT:
- integer.
EXAMPLES::
sage: fan = FaceFan(lattice_polytope.octahedron(2))
sage: fan.ngenerating_cones()
4
sage: cone1 = Cone([(1,0), (0,1)])
sage: cone2 = Cone([(-1,0)])
sage: fan = Fan([cone1, cone2])
sage: fan.ngenerating_cones()
2
"""
return len(self.generating_cones())
def plot(self, **options):
r"""
Plot ``self``.
INPUT:
- any options for toric plots (see :func:`toric_plotter.options
<sage.geometry.toric_plotter.options>`), none are mandatory.
OUTPUT:
- a plot.
EXAMPLES::
sage: fan = toric_varieties.dP6().fan()
sage: fan.plot()
"""
tp = ToricPlotter(options, self.lattice().degree(), self.rays())
result = tp.plot_lattice() + tp.plot_rays() + tp.plot_generators()
if self.dim() >= 2:
result += tp.plot_walls(self(2))
return result
def subdivide(self, new_rays=None, make_simplicial=False,
algorithm="default", verbose=False):
r"""
Construct a new fan subdividing ``self``.
INPUT:
- ``new_rays`` - list of new rays to be added during subdivision, each
ray must be a list or a vector. May be empty or ``None`` (default);
- ``make_simplicial`` - if ``True``, the returned fan is guaranteed to
be simplicial, default is ``False``;
- ``algorithm`` - string with the name of the algorithm used for
subdivision. Currently there is only one available algorithm called
"default";
- ``verbose`` - if ``True``, some timing information may be printed
during the process of subdivision.
OUTPUT:
- :class:`rational polyhedral fan
<sage.geometry.fan.RationalPolyhedralFan>`.
Currently the "default" algorithm corresponds to iterative stellar
subdivision for each ray in ``new_rays``.
EXAMPLES::
sage: fan = NormalFan(lattice_polytope.octahedron(3))
sage: fan.is_simplicial()
False
sage: fan.ngenerating_cones()
6
sage: fan.nrays()
8
sage: new_fan = fan.subdivide(new_rays=[(1,0,0)])
sage: new_fan.is_simplicial()
False
sage: new_fan.ngenerating_cones()
9
sage: new_fan.nrays()
9
TESTS:
We check that Trac #11902 is fixed::
sage: fan = toric_varieties.P2().fan()
sage: fan.subdivide(new_rays=[(0,0)])
Traceback (most recent call last):
...
ValueError: the origin cannot be used for fan subdivision!
"""
if make_simplicial and not self.is_simplicial():
rays = list(self.rays())
else:
rays = []
rays.extend(ray for ray in normalize_rays(new_rays, self.lattice())
if ray not in self.ray_set())
if not rays:
return self
if self.lattice().zero() in rays:
raise ValueError("the origin cannot be used for fan subdivision!")
if algorithm == "default":
algorithm = "palp"
method_name = "_subdivide_" + algorithm
if not hasattr(self, method_name):
raise ValueError('"%s" is an unknown subdivision algorithm!'
% algorithm)
return getattr(self, method_name)(rays, verbose)
def primitive_collections(self):
ur"""
Return the primitive collections.
OUTPUT:
Returns the subsets `\{i_1,\dots,i_k\} \subset \{ 1,\dots,n\}`
such that
* The points `\{p_{i_1},\dots,p_{i_k}\}` do not span a cone of
the fan.
* If you remove any one `p_{i_j}` from the set, then they do
span a cone of the fan.
.. NOTE::
By replacing the multiindices `\{i_1,\dots,i_k\}` of each
primitive collection with the monomials `x_{i_1}\cdots
x_{i_k}` one generates the Stanley-Reisner ideal in
`\ZZ[x_1,\dots]`.
REFERENCES:
..
V.V. Batyrev, On the classification of smooth projective
toric varieties, Tohoku Math.J. 43 (1991), 569-585
EXAMPLES::
sage: fan = Fan([[0,1,3],[3,4],[2,0],[1,2,4]], [(-3, -2, 1), (0, 0, 1), (3, -2, 1), (-1, -1, 1), (1, -1, 1)])
sage: fan.primitive_collections()
[frozenset([0, 4]), frozenset([2, 3]), frozenset([0, 1, 2]), frozenset([1, 3, 4])]
"""
try:
return self._primitive_collections
except AttributeError:
pass
def is_not_facet(I):
return all( not(I<=f) for f in facets )
def is_in_SR(I):
return all( not(I>=sr) for sr in SR)
facets = map(frozenset, [ c.ambient_ray_indices() for c in self.generating_cones() ])
all_points = frozenset( range(0,self.nrays()) )
d_max = max(map(len,facets))+1
SR = []
for d in range(1,d_max):
checked = set([])
for facet in facets:
for I_minus_j_list in Combinations(facet, d):
I_minus_j = frozenset(I_minus_j_list)
for j in all_points - I_minus_j:
I = I_minus_j.union( frozenset([j]) )
if I in checked:
continue
else:
checked.add(I)
if is_not_facet(I) and is_in_SR(I):
SR.append(I)
self._primitive_collections = SR
return self._primitive_collections
def Stanley_Reisner_ideal(self, ring):
"""
Return the Stanley-Reisner ideal.
INPUT:
- A polynomial ring in ``self.nrays()`` variables.
OUTPUT:
- The Stanley-Reisner ideal in the given polynomial ring.
EXAMPLES::
sage: fan = Fan([[0,1,3],[3,4],[2,0],[1,2,4]], [(-3, -2, 1), (0, 0, 1), (3, -2, 1), (-1, -1, 1), (1, -1, 1)])
sage: fan.Stanley_Reisner_ideal( PolynomialRing(QQ,5,'A, B, C, D, E') )
Ideal (A*E, C*D, A*B*C, B*D*E) of Multivariate Polynomial Ring in A, B, C, D, E over Rational Field
"""
generators_indices = self.primitive_collections()
SR = ring.ideal([ prod([ ring.gen(i) for i in sr]) for sr in generators_indices ])
return SR
def linear_equivalence_ideal(self, ring):
"""
Return the ideal generated by linear relations
INPUT:
- A polynomial ring in ``self.nrays()`` variables.
OUTPUT:
Returns the ideal, in the given ``ring``, generated by the
linear relations of the rays. In toric geometry, this
corresponds to rational equivalence of divisors.
EXAMPLES::
sage: fan = Fan([[0,1,3],[3,4],[2,0],[1,2,4]], [(-3, -2, 1), (0, 0, 1), (3, -2, 1), (-1, -1, 1), (1, -1, 1)])
sage: fan.linear_equivalence_ideal( PolynomialRing(QQ,5,'A, B, C, D, E') )
Ideal (-3*A + 3*C - D + E, -2*A - 2*C - D - E, A + B + C + D + E) of Multivariate Polynomial Ring in A, B, C, D, E over Rational Field
"""
gens = []
for d in range(0,self.dim()):
gens.append( sum([ self.ray(i)[d] * ring.gen(i)
for i in range(0, self.nrays()) ]) )
return ring.ideal(gens)
def oriented_boundary(self, cone):
r"""
Return the facets bounding ``cone`` with their induced
orientation.
INPUT:
- ``cone`` -- a cone of the fan or the whole fan.
OUTPUT:
The boundary cones of ``cone`` as a formal linear combination
of cones with coefficients `\pm 1`. Each summand is a facet of
``cone`` and the coefficient indicates whether their (chosen)
orientation argrees or disagrees with the "outward normal
first" boundary orientation. Note that the orientation of any
individial cone is arbitrary. This method once and for all
picks orientations for all cones and then computes the
boundaries relative to that chosen orientation.
If ``cone`` is the fan itself, the generating cones with their
orientation relative to the ambient space are returned.
See :meth:`complex` for the associated chain complex. If you
do not require the orientation, use :meth:`cone.facets()
<sage.geometry.cone.ConvexRationalPolyhedralCone.facets>`
instead.
EXAMPLES::
sage: fan = toric_varieties.P(3).fan()
sage: cone = fan(2)[0]
sage: bdry = fan.oriented_boundary(cone); bdry
1-d cone of Rational polyhedral fan in 3-d lattice N
- 1-d cone of Rational polyhedral fan in 3-d lattice N
sage: bdry[0]
(1, 1-d cone of Rational polyhedral fan in 3-d lattice N)
sage: bdry[1]
(-1, 1-d cone of Rational polyhedral fan in 3-d lattice N)
sage: fan.oriented_boundary(bdry[0][1])
-0-d cone of Rational polyhedral fan in 3-d lattice N
sage: fan.oriented_boundary(bdry[1][1])
-0-d cone of Rational polyhedral fan in 3-d lattice N
If you pass the fan itself, this method returns the
orientation of the generating cones which is determined by the
order of the rays in :meth:`cone.ray_basis()
<sage.geometry.cone.IntegralRayCollection.ray_basis>` ::
sage: fan.oriented_boundary(fan)
-3-d cone of Rational polyhedral fan in 3-d lattice N
+ 3-d cone of Rational polyhedral fan in 3-d lattice N
- 3-d cone of Rational polyhedral fan in 3-d lattice N
+ 3-d cone of Rational polyhedral fan in 3-d lattice N
sage: [ matrix(cone.ray_basis()).det() for cone in fan.generating_cones() ]
[-1, 1, -1, 1]
A non-full dimensional fan::
sage: cone = Cone([(4,5)])
sage: fan = Fan([cone])
sage: fan.oriented_boundary(cone)
0-d cone of Rational polyhedral fan in 2-d lattice N
sage: fan.oriented_boundary(fan)
1-d cone of Rational polyhedral fan in 2-d lattice N
TESTS::
sage: fan = toric_varieties.P2().fan()
sage: trivial_cone = fan(0)[0]
sage: fan.oriented_boundary(trivial_cone)
0
"""
if not cone is self:
cone = self.embed(cone)
if '_oriented_boundary' in self.__dict__:
return self._oriented_boundary[cone]
from sage.structure.formal_sum import FormalSum
def sign(x):
assert x != 0
if x>0: return +1
else: return -1
N_QQ = self.lattice().base_extend(QQ)
dim = self.lattice_dim()
outward_vectors = dict()
generating_cones = []
for c in self.generating_cones():
if c.dim()==dim:
outward_v = []
else:
Q = N_QQ.quotient(c.rays())
outward_v = [ Q.lift(q) for q in Q.gens() ]
outward_vectors[c] = outward_v
orientation = sign(matrix(outward_v + list(c.ray_basis())).det())
generating_cones.append(tuple([orientation, c]))
boundaries = {self:FormalSum(generating_cones)}
for d in range(dim, -1, -1):
for c in self(d):
c_boundary = []
c_matrix = matrix(outward_vectors[c] + list(c.ray_basis()))
c_matrix_inv = c_matrix.inverse()
for facet in c.facets():
outward_ray_indices = set(c.ambient_ray_indices()) \
.difference(set(facet.ambient_ray_indices()))
outward_vector = - sum(self.ray(i) for i in outward_ray_indices)
outward_vectors[facet] = [outward_vector] + outward_vectors[c]
facet_matrix = matrix(outward_vectors[facet] + list(facet.ray_basis()))
orientation = sign((c_matrix_inv * facet_matrix).det())
c_boundary.append(tuple([orientation, facet]))
boundaries[c] = FormalSum(c_boundary)
self._oriented_boundary = boundaries
return boundaries[cone]
def complex(self, base_ring=ZZ, extended=False):
r"""
Return the chain complex of the fan.
To a `d`-dimensional fan `\Sigma`, one can canonically
associate a chain complex `K^\bullet`
.. math::
0 \longrightarrow
\ZZ^{\Sigma(d)} \longrightarrow
\ZZ^{\Sigma(d-1)} \longrightarrow
\cdots \longrightarrow
\ZZ^{\Sigma(0)} \longrightarrow
0
where the leftmost non-zero entry is in degree `0` and the
rightmost entry in degree `d`. See [Klyachko], eq. (3.2). This
complex computes the homology of `|\Sigma|\subset N_\RR` with
arbitrary support,
.. math::
H_i(K) = H_{d-i}(|\Sigma|, \ZZ)_{\text{non-cpct}}
For a complete fan, this is just the non-compactly supported
homology of `\RR^d`. In this case, `H_0(K)=\ZZ` and `0` in all
non-zero degrees.
For a complete fan, there is an extended chain complex
.. math::
0 \longrightarrow
\ZZ \longrightarrow
\ZZ^{\Sigma(d)} \longrightarrow
\ZZ^{\Sigma(d-1)} \longrightarrow
\cdots \longrightarrow
\ZZ^{\Sigma(0)} \longrightarrow
0
where we take the first `\ZZ` term to be in degree -1. This
complex is an exact sequence, that is, all homology groups
vanish.
The orientation of each cone is chosen as in
:meth:`oriented_boundary`.
INPUT:
- ``extended`` -- Boolean (default:False). Whether to
construct the extended complex, that is, including the
`\ZZ`-term at degree -1 or not.
- ``base_ring`` -- A ring (default: ``ZZ``). The ring to use
instead of `\ZZ`.
OUTPUT:
The complex associated to the fan as a :class:`ChainComplex
<sage.homology.chain_complex.ChainComplex>`. Raises a
``ValueError`` if the extended complex is requested for a
non-complete fan.
EXAMPLES::
sage: fan = toric_varieties.P(3).fan()
sage: K_normal = fan.complex(); K_normal
Chain complex with at most 4 nonzero terms over Integer Ring
sage: K_normal.homology()
{0: Z, 1: 0, 2: 0, 3: 0}
sage: K_extended = fan.complex(extended=True); K_extended
Chain complex with at most 5 nonzero terms over Integer Ring
sage: K_extended.homology()
{0: 0, 1: 0, 2: 0, 3: 0, -1: 0}
Homology computations are much faster over `\QQ` if you don't
care about the torsion coefficients::
sage: toric_varieties.P2_123().fan().complex(extended=True, base_ring=QQ)
Chain complex with at most 4 nonzero terms over Rational Field
sage: _.homology()
{0: Vector space of dimension 0 over Rational Field,
1: Vector space of dimension 0 over Rational Field,
2: Vector space of dimension 0 over Rational Field,
-1: Vector space of dimension 0 over Rational Field}
The extended complex is only defined for complete fans::
sage: fan = Fan([ Cone([(1,0)]) ])
sage: fan.is_complete()
False
sage: fan.complex(extended=True)
Traceback (most recent call last):
...
ValueError: The extended complex is only defined for complete fans!
The definition of the complex does not refer to the ambient
space of the fan, so it does not distinguish a fan from the
same fan embedded in a subspace::
sage: K1 = Fan([Cone([(-1,)]), Cone([(1,)])]).complex()
sage: K2 = Fan([Cone([(-1,0,0)]), Cone([(1,0,0)])]).complex()
sage: K1 == K2
True
Things get more complicated for non-complete fans::
sage: fan = Fan([Cone([(1,1,1)]),
... Cone([(1,0,0),(0,1,0)]),
... Cone([(-1,0,0),(0,-1,0),(0,0,-1)])])
sage: fan.complex().homology()
{0: 0, 1: 0, 2: Z x Z, 3: 0}
sage: fan = Fan([Cone([(1,0,0),(0,1,0)]),
... Cone([(-1,0,0),(0,-1,0),(0,0,-1)])])
sage: fan.complex().homology()
{0: 0, 1: 0, 2: Z, 3: 0}
sage: fan = Fan([Cone([(-1,0,0),(0,-1,0),(0,0,-1)])])
sage: fan.complex().homology()
{0: 0, 1: 0, 2: 0, 3: 0}
REFERENCES:
.. [Klyachko]
A. A. Klyachko,
Equivariant Bundles on Toral Varieties.
Mathematics of the USSR - Izvestiya 35 (1990), 337-375.
"""
dim = self.dim()
delta = dict()
for degree in range(1, dim+1):
m = matrix(base_ring, len(self(degree-1)), len(self(degree)), base_ring.zero())
for i, cone in enumerate(self(degree)):
boundary = self.oriented_boundary(cone)
for orientation, d_cone in boundary:
m[self(degree-1).index(d_cone), i] = orientation
delta[dim-degree] = m
from sage.homology.chain_complex import ChainComplex
if not extended:
return ChainComplex(delta, base_ring=base_ring)
if not self.is_complete():
raise ValueError('The extended complex is only defined for complete fans!')
extension = matrix(base_ring, len(self(dim)), 1, base_ring.zero())
generating_cones = self.oriented_boundary(self)
for orientation, d_cone in generating_cones:
extension[self(dim).index(d_cone), 0] = orientation
delta[-1] = extension
return ChainComplex(delta, base_ring=base_ring)
def discard_faces(cones):
r"""
Return the cones of the given list which are not faces of each other.
INPUT:
- ``cones`` -- a list of
:class:`cones <sage.geometry.cone.ConvexRationalPolyhedralCone>`.
OUTPUT:
- a list of
:class:`cones <sage.geometry.cone.ConvexRationalPolyhedralCone>`,
sorted by dimension in decreasing order.
EXAMPLES:
Consider all cones of a fan::
sage: Sigma = toric_varieties.P2().fan()
sage: cones = flatten(Sigma.cones())
sage: len(cones)
7
Most of them are not necessary to generate this fan::
sage: from sage.geometry.fan import discard_faces
sage: len(discard_faces(cones))
3
sage: Sigma.ngenerating_cones()
3
"""
cones = list(cones)
cones.sort(key=lambda cone: cone.dim(), reverse=True)
generators = []
for cone in cones:
if not any(cone.is_face_of(other) for other in generators):
generators.append(cone)
return generators
_discard_faces = discard_faces
