Sage中多面体计算的较长介绍¶
本教程旨在展示Sage关于多面体几何和组合学的一些可能性。
关于这一主题的经典文献包括:
对于命名法,Sage试图遵循:
离散与计算几何手册 ,第15章, [Goo2004]
本文件的编写部分得到了OpenDreamKit项目的支持,并在奥洛特(西班牙)的SageDays 84期间编写。
第0讲:基本定义和结构¶
真实的 (ktimes d) -矩阵 A 一个实向量 b 在里面 mathbb{{R}}^d 定义a(凸) 多面体 P 作为线性不等式组的一组解:
Each row of A defines a closed half-space of mathbb{R}^d. Hence a polyhedron is the intersection of finitely many closed half-spaces in mathbb{R}^d. The matrix A may contain equal rows, which may lead to a set of equalities satisfied by the polyhedron. If there are no redundant rows in the above definition, this definition is referred to as the mathbf{H} -representation of a polyhedron.
极大仿射子空间 L 包含在多面体中的是 直线性 空间 P . 固定一个点 o 线性空间的 L 充当 起源 ,一个人可以写下每一点 p 在多面体中作为一个组合
在哪里? ellin L (使用) o 作为起源), sum_{{i=1}}^nlambda_i=1 , lambda_igeq0 , mu_igeq0 和 r_ineq0 为了所有 0leq ileq m 以及 r_i 的正独立性(起源不在其正范围内)。对于一个给定的点 p 使用不同的集合可能有许多等效的方法来编写上面的内容 {{v_i}}_{{i=1}}^{{n}} 和 {{r_i}}_{{i=1}}^{{m}} . 因此,我们要求集合是包含极小集,这样我们就可以得到任何点的上述性质相等 pin P .
The vectors v_i are called the vertices of P and the vectors r_i are called the rays of P. This way to represent a polyhedron is referred to as the mathbf{V} -representation of a polyhedron. The first sum represents the convex hull of the vertices v_i 's and the second sum represents a pointed polyhedral cone generated by finitely many rays.
当线性空间和光线被缩减到一个点(即没有光线和直线)时,对象通常被称为 多面体 .
注解
在输入时,如构造函数文档中所述 Polyhedron?
:
You may either define it with vertex/ray/line or inequalities/equations data, but not both. Redundant data will automatically be removed (unless "minimize=False"), and the complementary representation will be computed.
以下是的构造函数函数的文档 多面体 .
V -代表¶
首先,让我们将多面体对象定义为一组点和一些光线的凸包。
sage: P1 = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]])
sage: P1
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray
字符串表示法已经提供了很多信息:
多面体的维数(包含它的最小仿射空间)
定义它的空间的维数
底座环 (mathbb{{Z}}^2 )多面体所在的位置(这指定父类,请参见 多面体亲本 )
顶点的数量
射线的数量
当然,您想知道这个对象是什么样子的:
sage: P1.plot()
Graphics object consisting of 5 graphics primitives
我们还可以添加一个线性空间。
sage: P2 = Polyhedron(vertices = [[1/2, 0, 0], [0, 1/2, 0]],
....: rays = [[1, 1, 0]],
....: lines = [[0, 0, 1]])
sage: P2
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 2 vertices, 1 ray, 1 line
sage: P2.plot()
Graphics3d Object
请注意,基环因值而改变 frac{{1}}{{2}} . 实际上,Sage找到了一个合适的环来定义对象。
sage: P1.parent()
Polyhedra in QQ^2
sage: P2.parent()
Polyhedra in QQ^3
选择的环取决于输入格式。
sage: P3 = Polyhedron(vertices = [[0.5, 0], [0, 0.5]])
sage: P3
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices
sage: P3.parent()
Polyhedra in RDF^2
警告
底座环 RDF
应小心使用。由于它不是一个精确的环,某些计算可能会中断或无声地产生错误的结果,例如在处理非简单多面体时。
下面的示例演示了 RDF
.
sage: D = polytopes.dodecahedron()
sage: D
A 3-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^3 defined as the convex hull of 20 vertices
sage: D_RDF = Polyhedron(vertices = [n(v.vector(),digits=6) for v in D.vertices()], base_ring=RDF)
Traceback (most recent call last):
...
ValueError: *Error: Numerical inconsistency is found. Use the GMP exact arithmetic.
如果多面体的输入由python组成 float
,它自动将数据转换为 RDF
:
sage: Polyhedron(vertices=[[float(1.1)]])
A 0-dimensional polyhedron in RDF^1 defined as the convex hull of 1 vertex
在代数数上定义多面体也是可能的。
sage: sqrt_2 = AA(2)^(1/2)
sage: cbrt_2 = AA(2)^(1/3)
sage: timeit('Polyhedron(vertices = [[sqrt_2, 0], [0, cbrt_2]])') # random
5 loops, best of 3: 43.2 ms per loop
sage: P4 = Polyhedron(vertices = [[sqrt_2, 0], [0, cbrt_2]]); P4
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices
还有另一种方法可以在代数数上创建多面体:
sage: K.<a> = NumberField(x^2 - 2, embedding=AA(2)**(1/2))
sage: L.<b> = NumberField(x^3 - 2, embedding=AA(2)**(1/3))
sage: timeit('Polyhedron(vertices = [[a, 0], [0, b]])') # random
5 loops, best of 3: 39.9 ms per loop
sage: P5 = Polyhedron(vertices = [[a, 0], [0, b]]); P5
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices
如果基环已知,则使用适当的 sage.rings.number_field.number_field.number_field.composite_fields()
:
sage: J = K.composite_fields(L)[0]
sage: timeit('Polyhedron(vertices = [[J(a), 0], [0, J(b)]])') # random
25 loops, best of 3: 9.8 ms per loop
sage: P5_comp = Polyhedron(vertices = [[J(a), 0], [0, J(b)]]); P5_comp
A 1-dimensional polyhedron in (Number Field in ab with defining polynomial x^6 - 6*x^4 - 4*x^3 + 12*x^2 - 24*x - 4 with ab = -0.1542925124782219?)^2 defined as the convex hull of 2 vertices
多面体计算 Symbolic Ring
没有实现。无法在其上定义多面体:
sage: sqrt_2s = sqrt(2)
sage: cbrt_2s = 2^(1/3)
sage: Polyhedron(vertices = [[sqrt_2s, 0], [0, cbrt_2s]])
Traceback (most recent call last):
...
ValueError: no default backend for computations with Symbolic Ring
同样,也不可能在上面创建多面体对象 RR
(不管精确到多少位)。
sage: F45 = RealField(45)
sage: F100 = RealField(100)
sage: f = 1.1
sage: Polyhedron(vertices=[[F45(f)]])
Traceback (most recent call last):
...
ValueError: the only allowed inexact ring is 'RDF' with backend 'cdd'
sage: Polyhedron(vertices=[[F100(f)]])
Traceback (most recent call last):
...
ValueError: the only allowed inexact ring is 'RDF' with backend 'cdd'
有一个例外,当精度位数为53时,基环转换为 RDF
:
sage: F53 = RealField(53)
sage: Polyhedron(vertices=[[F53(f)]])
A 0-dimensional polyhedron in RDF^1 defined as the convex hull of 1 vertex
sage: type(Polyhedron(vertices=[[F53(f)]]))
<class 'sage.geometry.polyhedron.parent.Polyhedra_RDF_cdd_with_category.element_class'>
这种行为可能被视为错误,但它允许Sage接受以下行为:
sage: Polyhedron([(1.0, 2.3), (3.5, 2.0)])
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices
没有指定基环 RDF
由用户决定。
H -代表¶
如果多面体对象是通过 V -代表,Sage可以提供 H -对象的表示。
sage: for h in P1.Hrepresentation():
....: print(h)
An inequality (1, 1) x - 1 >= 0
An inequality (1, -1) x + 1 >= 0
An inequality (-1, 1) x + 1 >= 0
每行给出一行矩阵 A 以及向量的一个条目 b . 变量 x 是环境空间中的向量,其中 P1
已定义。这个 H -表示可以包含以下等式:
sage: P3.Hrepresentation()
(An inequality (-2.0, 0.0) x + 1.0 >= 0,
An inequality (1.0, 0.0) x + 0.0 >= 0,
An equation (1.0, 1.0) x - 0.5 == 0)
通过its构造多面体对象 H -表示,需要精确的格式。每个不平等 (a_{{i1}}, dots, a_{{id}})cdot x + b_i geq 0 必须写成 [b_i,a_i1, ..., a_id]
.
sage: P3_H = Polyhedron(ieqs = [[1.0, -2, 0], [0, 1, 0]], eqns = [[-0.5, 1, 1]])
sage: P3 == P3_H
True
sage: P3_H.Vrepresentation()
(A vertex at (0.0, 0.5), A vertex at (0.5, 0.0))
值得使用该参数 eqns
缩短对象的结构。在下面的示例中,前四行是第二组四行的负数。
sage: H = [[0, 0, 0, 0, 0, 0, 0, 0, 1],
....: [0, 0, 0, 0, 0, 0, 1, 0, 0],
....: [-2, 1, 1, 1, 1, 1, 0, 0, 0],
....: [0, 0, 0, 0, 0, 0, 0, 1, 0],
....: [0, 0, 0, 0, 0, 0, 0, 0, -1],
....: [0, 0, 0, 0, 0, 0, -1, 0, 0],
....: [2, -1, -1, -1, -1, -1, 0, 0, 0],
....: [0, 0, 0, 0, 0, 0, 0, -1, 0],
....: [2, -1, -1, -1, -1, 0, 0, 0, 0],
....: [0, 0, 0, 0, 1, 0, 0, 0, 0],
....: [0, 0, 0, 1, 0, 0, 0, 0, 0],
....: [0, 0, 1, 0, 0, 0, 0, 0, 0],
....: [-1, 1, 1, 1, 1, 0, 0, 0, 0],
....: [1, 0, 0, -1, 0, 0, 0, 0, 0],
....: [0, 1, 0, 0, 0, 0, 0, 0, 0],
....: [1, 0, 0, 0, -1, 0, 0, 0, 0],
....: [1, 0, -1, 0, 0, 0, 0, 0, 0],
....: [1, -1, 0, 0, 0, 0, 0, 0, 0]]
sage: timeit('Polyhedron(ieqs = H)') # random
125 loops, best of 3: 5.99 ms per loop
sage: timeit('Polyhedron(ieqs = H[8:], eqns = H[:4])') # random
125 loops, best of 3: 4.78 ms per loop
sage: Polyhedron(ieqs = H) == Polyhedron(ieqs = H[8:], eqns = H[:4])
True
当然,这是一个很有趣的例子,但是如果可能的话,在定义多面体之前通常需要对数据进行预处理。
第一讲:表现对象¶
许多对象与 H -和 V -陈述。Sage为他们实现了类。
H -代表¶
您可以存储 H -表示变量,并将不等式和等式用作对象。
sage: P3_QQ = Polyhedron(vertices = [[0.5, 0], [0, 0.5]], base_ring=QQ)
sage: HRep = P3_QQ.Hrepresentation()
sage: H1 = HRep[0]; H1
An equation (2, 2) x - 1 == 0
sage: H2 = HRep[1]; H2
An inequality (0, -2) x + 1 >= 0
sage: H1.<tab> # not tested
sage: H1.A()
(2, 2)
sage: H1.b()
-1
sage: H1.is_equation()
True
sage: H1.is_inequality()
False
sage: H1.contains(vector([0,0]))
False
sage: H2.contains(vector([0,0]))
True
sage: H1.is_incident(H2)
True
可以获得 H -陈述如下。
sage: P3_QQ.equations()
(An equation (2, 2) x - 1 == 0,)
sage: P3_QQ.inequalities()
(An inequality (0, -2) x + 1 >= 0, An inequality (0, 1) x + 0 >= 0)
注解
建议使用 equations
或 equation_generator
(对于不等式也是如此)如果你想迭代它们而不是 equations_list
.
V -代表¶
类似地,您可以访问多面体的顶点、光线和线。
sage: VRep = P2.Vrepresentation(); VRep
(A line in the direction (0, 0, 1),
A vertex at (0, 1/2, 0),
A vertex at (1/2, 0, 0),
A ray in the direction (1, 1, 0))
sage: L = VRep[0]; L
A line in the direction (0, 0, 1)
sage: V = VRep[1]; V
A vertex at (0, 1/2, 0)
sage: R = VRep[3]; R
A ray in the direction (1, 1, 0)
sage: L.is_line()
True
sage: L.is_incident(V)
True
sage: R.is_incident(L)
False
sage: L.vector()
(0, 0, 1)
sage: V.vector()
(0, 1/2, 0)
可以获得 V -陈述如下。
sage: P2.vertices()
(A vertex at (0, 1/2, 0), A vertex at (1/2, 0, 0))
sage: P2.rays()
(A ray in the direction (1, 1, 0),)
sage: P2.lines()
(A line in the direction (0, 0, 1),)
sage: P2.vertices_matrix()
[ 0 1/2]
[1/2 0]
[ 0 0]
注解
建议使用 vertices
或 vertex_generator
(光线和线条也是如此)如果你想迭代它们而不是 vertices_list
.
第二讲:多面体计算的后端¶
为了处理多面体对象,Sage目前有四个后端可用。这些后端提供了各种功能,并有自己的特定优势和局限性。
这是一个
python
在无理坐标上提供多面体实现的后端。多面体计算的规范化后端 可选程序包需要
pynormaliz
)
默认后端是 ppl
. 任何需要的时候 速度 尝试不同的后端是很好的。后端 field
是 not 专门设计用于处理极值计算,但可以在精确坐标下进行计算。
这个 cdd
后端¶
为了使用特定的后端,我们指定 backend
参数。
sage: P1_cdd = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]], backend='cdd')
sage: P1_cdd
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray
一个先验,似乎没有什么改变,但是。。。
sage: P1_cdd.parent()
Polyhedra in QQ^2
多面体 P1_cdd
现在被后端视为有理多面体 cdd
. 我们也可以使用 type
:
sage: type(P1_cdd)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_cdd_with_category.element_class'>
sage: type(P1)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>
我们看到了
使用的后端(例如:
backend_cdd
)后面跟着一个点“.”
母公司(例如:
Polyhedra_QQ
)接着是后端,
在本教程中,您可以放心地忽略其余部分。
这个 cdd
后端也接受 RDF
:
sage: P3_cdd = Polyhedron(vertices = [[0.5, 0], [0, 0.5]], backend='cdd')
sage: P3_cdd
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices
但不是代数或符号值:
sage: P4_cdd = Polyhedron(vertices = [[sqrt_2, 0], [0, cbrt_2]], backend='cdd')
Traceback (most recent call last):
...
ValueError: No such backend (=cdd) implemented for given basering (=Algebraic Real Field).
sage: P5_cdd = Polyhedron(vertices = [[sqrt_2s, 0], [0, cbrt_2s]], backend='cdd')
Traceback (most recent call last):
...
ValueError: No such backend (=cdd) implemented for given basering (=Symbolic Ring).
有可能得到 cdd
上定义的任何多面体对象的格式 mathbb{{Z}} , mathbb{{Q}} 或 RDF
:
sage: print(P1.cdd_Vrepresentation())
V-representation
begin
3 3 rational
0 1 1
1 0 1
1 1 0
end
sage: print(P3.cdd_Hrepresentation())
H-representation
linearity 1 1
begin
3 3 real
-0.5 1.0 1.0
1.0 -2.0 0.0
0.0 1.0 0.0
end
也可以使用方法将这些数据写入文件 .write_cdd_Hrepresentation(filename)
或 .write_cdd_Vrepresentation(filename)
在哪里 filename
包含要写入的文件的路径的字符串。
这个 ppl
后端¶
多面体对象的默认后端是 ppl
.
sage: type(P1)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>
sage: type(P2)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>
sage: type(P3) # has entries like 0.5
<class 'sage.geometry.polyhedron.parent.Polyhedra_RDF_cdd_with_category.element_class'>
如您所见,它不接受 RDF
多面体构造器使用 cdd
后端。
这个 polymake
后端¶
这个 polymake
安装sage的实验包polymake时提供后端。
sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)], # optional - polymake
....: rays=[(1,1)], lines=[],
....: backend='polymake', base_ring=QQ)
二次域示例:
sage: V = polytopes.dodecahedron().vertices_list()
sage: Polyhedron(vertices=V, backend='polymake') # optional - polymake
A 3-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5)^3 defined as the convex hull of 20 vertices
这个 field
后端¶
事实证明,有理数不足以表示多面体的所有组合类型。例如,Perles构造了一个 8 -三维多面体 12 没有有理坐标实现的顶点,参见 [Zie2007]. 此外,如果一个人想要一个实现具有特定的几何性质,例如对称性,有时还需要无理坐标。
后端 field
提供处理此类示例所需的工具。
sage: type(D)
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>
任何时候坐标都应该在理性的扩展中,后端 field
被称为。
sage: P4.parent()
Polyhedra in AA^2
sage: P5.parent()
Polyhedra in AA^2
sage: type(P4)
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>
sage: type(P5)
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>
这个 normaliz
后端¶
第四个后端是 normaliz
是一个可选的Sage包。
sage: P1_normaliz = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]], backend='normaliz') # optional - pynormaliz
sage: type(P1_normaliz) # optional - pynormaliz
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_normaliz_with_category.element_class'>
sage: P2_normaliz = Polyhedron(vertices = [[1/2, 0, 0], [0, 1/2, 0]], # optional - pynormaliz
....: rays = [[1, 1, 0]],
....: lines = [[0, 0, 1]], backend='normaliz')
sage: type(P2_normaliz) # optional - pynormaliz
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_normaliz_with_category.element_class'>
此后端不适用于 RDF
不准确的行为。
sage: P3_normaliz = Polyhedron(vertices = [[0.5, 0], [0, 0.5]], backend='normaliz') # optional - pynormaliz
Traceback (most recent call last):
...
ValueError: No such backend (=normaliz) implemented for given basering (=Real Double Field).
这个 normaliz
后端提供代数数的快速计算。它们可以作为嵌入数域、代数数域甚至符号环的元素输入。在内部,使用嵌入的数字字段完成计算。
sage: P4_normaliz = Polyhedron(vertices = [[sqrt_2, 0], [0, cbrt_2]], backend='normaliz') # optional - pynormaliz
sage: P4_normaliz # optional - pynormaliz
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices
sage: P5_normaliz = Polyhedron(vertices = [[sqrt_2s, 0], [0, cbrt_2s]], backend='normaliz') # optional - pynormaliz
sage: P5_normaliz # optional - pynormaliz
A 1-dimensional polyhedron in (Symbolic Ring)^2 defined as the convex hull of 2 vertices
后端 normaliz
提供其他方法,如 integral_hull
,也适用于无界多面体。
sage: P6 = Polyhedron(vertices = [[0, 0], [3/2, 0], [3/2, 3/2], [0, 3]], backend='normaliz') # optional - pynormaliz
sage: IH = P6.integral_hull(); IH # optional - pynormaliz
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: P6.plot(color='blue')+IH.plot(color='red') # optional - pynormaliz
Graphics object consisting of 12 graphics primitives
sage: P1_normaliz.integral_hull() # optional - pynormaliz
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray
第三讲:对于每一个多面体,正确的父类¶
为了 知道多面体对象的所有方法 我们必须调查 base class
:
如果这些类看起来是空的,不要惊讶!这些类主要包含实现一些比较方法的私有方法:验证基环中数字的相等性和不相等性以及其他内部功能。
为了全面了解提供给您的方法, 多面体的基类 是你想去的第一个地方。
第四讲:多面体类库¶
类库里有很多多面体,你看 常用的、著名的或有趣的多面体的类库 . 看看它们,看看你的多面体是否已经定义好了!
sage: A = polytopes.buckyball(); A # can take long
A 3-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^3 defined as the convex hull of 60 vertices
sage: B = polytopes.cross_polytope(4); B
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 8 vertices
sage: C = polytopes.cyclic_polytope(3,10); C
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 10 vertices
sage: E = polytopes.snub_cube(exact=False); E
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 24 vertices
sage: polytopes.<tab> # not tested, to view all the possible polytopes
参考文献¶
- Bro1983
布朗斯特德,A.,凸多面体导论,数学研究生教材第90卷。斯普林格·韦拉格,纽约,1983年。国际标准书号978-1-4612-7023-2
- Goo2004
J、 E.Goodman和J.O'Rourke,编辑,CRC出版社有限责任公司,佛罗里达州博卡拉顿,2004年。ISBN 978-1584883012(65章,xvii+1539页)。
- Gru1967
Günbaum,B.,凸多面体,数学研究生教材第221卷。斯普林格·韦拉格,纽约,2003年。国际标准书号978-1-4613-0019-9
- Zie2007(1,2)
齐格勒,G.M.,关于多面体的讲座,数学研究生教材第152卷。斯普林格·韦拉格,纽约,2007年。国际标准书号978-0-387-94365-7