新浪博客

强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序

2015-09-15 09:26阅读：

http://blog.sina.cn/dpool/blog/u/1282126350

强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序
原创 2015-09-15 顾险峰 赛先生
撰文/顾险峰 (纽约州立大学石溪分校计算机系终身教授，清华大学丘成桐数学科学中心访问教授)

几何是大自然的语言，一切学科的成熟标志就是用数学来精确表达其概念、思想和规律。古典物理定律的终极表现形式为偏微分方程，近现代物理定律具有几何化解释，例如重力等价于时空弯曲、夸克的分类联系着群论表示、宇宙基本常数取决于卡拉比-丘流形的拓扑等等。
可以毫不夸张地说，几何是人类认识自然不可或缺的基本工具。人类并不仅限于认识自然，其终极目的更在于改造自然。改造自然的基本工具既包括人手的延长物，蒸汽机，又包括人脑的延长物，计算机。时代的发展促使人类不可避免地将深邃优美的几何理论和无坚不摧的计算机技术相结合。由此可见，几何计算化是人类历史发展的必然。
几何计算化面临的挑战


几何计算化对于现代几何理论和计算机科学都提出了强有力的挑战。单纯从理论方面而言，就已经困难重重；考虑到计算机实现，我们不可避免地要渡过许多难以逾越的天堑：
存在性与构造性证明
首先，经典几何理论中的大量存在性证明都是基于抽象的拓扑方法，而非直接的构造法。从证明本身，我们只知道解的存在，但是无法具体找到解。这需要我们进一步发明新的构造性算法，往往构造性证明比存在性证明更加需要对几何现象的深刻理解和洞察。例如，我们考察布劳威尔不动点问题：假设我们有一杯咖啡，处于静止状态。我们轻轻搅拌咖啡，同时避免产生气泡和泡
沫，然后抽离咖啡匙。咖啡继续旋转，随后缓慢终止。由不动点定理，我们知道存在一个分子，其初始的位置和终止的位置相重合。（当然，在搅拌过程中有可能离开初始位置，但是最后又回到初始位置。）这个定理的代数拓扑证明用到了同调群的概念，抽象深刻，令人惊叹，但是关于如何找到不动点没有任何实质性的帮助。相反，这个定理的组合证明（Sperner's lemma），初等繁琐，平易近人，却给出了如何求解的具体步骤。
再比如黎曼面的单值化定理，给定一个封闭的带黎曼度量的可定向曲面，存在一个和初始度量共形等价的度量，其诱导常值高斯曲率。十九世纪末，单值化定理被复变函数方法证明出来。但是这种方法只给出了存在性，却无法直接构造出常曲率度量。直至近百年后，Hamilton的Ricci 曲率流方法才给出构造性方法。图1直观展示了曲面单值化定理，亏格为零的曲面保角地变成球面；亏格为一的曲面可以保角地展开在平面上；高亏格的曲面可以周期性地展开在双曲平面上。
对于大量的几何存在性定理，经典的理论只有抽象的证明，却没有构造性方法，寻求构造性的证明方法本身需要旷日持久的艰苦努力。
强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序 强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序 强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序
强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序 强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序 强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序
图1 单值化定理

光滑结构对离散表示

经典几何理论特别是微分几何和偏微分方程理论都是建筑在光滑微分结构之上。计算机内存有限，所有的数据结构都是离散的。如何用离散来计算连续，有限来表示无限，这本身就是难以调和的矛盾。一种方法是用离散来逼近连续，例如经典的有限元方法：在流形上的无穷维泛函空间中挑选有限维子空间，例如分片多项式样条函数空间，在子空间上求得近似解，然后增大子空间，使得近似解逼近连续解。另外一种方法更为直截了当，离散几何理论本身。例如Hamilton的曲面Ricci曲率流的理论是建立在光滑曲面上的，最近丘成桐学派建立了离散曲面上的Ricci流理论，这套理论是直接建立在离散的多面体曲面上的，并且和Hamilton的理论等价。图1显示了离散Ricci流方法得出的曲面单值化计算结果。
再比如，经典的蒙日-安培方程理论和闵科夫斯基理论，最优传输理论都有深刻的渊源。表面上看，蒙日-安培方程本身需要函数的高阶光滑性，但是它的几何本质却是只需要连续性。丘成桐学派建立了离散蒙日-安培方程理论，利用凸几何的方法求解。图2给出了从曲面到平面圆盘的保持面积元的映射，其计算过程依赖于求解离散蒙日-安培方程。
强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序 强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序
图2 蒙日-安培方程

计算复杂度
许多自然的几何和拓扑问题即便有计算方法，其算法都是具有指数级复杂度的。比如曲面上的复杂封闭曲线在同伦群中的最短表示问题。如图3所示，亏格为2的曲面上给定同伦群的基底，任给一条封闭曲线，其同伦类为同伦群中的一个元素，可以表示成基底的乘积，但是表示方法不唯一。在所有可能的表示方法中，求最短的表示。这一问题对于图灵机模型而言是NP问题。再如，给定空间中两条扭结，判定它们是否同痕：亦即我们能否将其中的一条渐变成另外一条，形变过程中要求不剪断而又重新连接。这一问题如果用代数拓扑方法求解也是NP问题。
目前，机器定理证明的主要方法是求多项式环中理想的一族生成元，生成元具有特殊的性质，满足一定的要求。主要的·计算工具是Groberner基底方法。这一方法的空间复杂度非常之高，虽然理论上可以广泛解决机器定理证明的问题，但是实际上作用非常有限。
强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序
图3 同伦群的计算问题

线性对非线性
线性方程现在已经研究得比较透彻，存在大量实用的算法和软件工具。工程中的线性偏微分方程，可以用差分法，傅里叶变换法或者有限元方法转化为线性方程。但是绝大多数自然的拓扑和几何问题都是非线性的，在这种情况下我们寻求变分法。在理想情况下，几何问题被转化为某一凸能量的变分从而使得计算变成凸优化。例如上文中提到的用曲率流方法来构造曲面的黎曼度量，实际上对应着凸能量（所谓熵能量）的优化；最优传输问题的蒙日-安培方程的解也是某种体积能量的极值解。当然，也存在大量的非线性几何问题，我们无法直接用凸能量的变分法处理，比如求高亏格闭曲面之间的泰西米勒映射（Teichmuller map），或周期映射的不变双曲度量等等。
稳定性
许多拓扑和几何问题的解本身是不稳定的，这意味着微小的初始误差或过程中的计算误差将会使结果相差十万八千里。例如混沌问题，动力系统中的三体问题等等。这种不稳定性是问题本身的性质所决定，和计算方法的设计和选取无关。另外一种稳定性是由计算误差所引发。比如经典计算几何中的Delaunay三角剖分，平面族的包络，离散点的凸包问题。这些问题的几何本质清楚明晰，但是计算中的微小误差就会引发组合结构的崩溃，其内在原因在于计算机只能近似表达实数及其运算结果，而组合结构的搭建却需要绝对精确，不容误差的。对于只涉及代数运算的计算几何问题，一种解决方法是在有理数域上进行精确的代数运算，用软件表示长整数。这种方法速度缓慢，但是保证了计算的正确性。另外，许多几何计算需要在特殊的黎曼度量下展开，对于双曲度量而言，靠近双曲空间的边缘处，共形因子趋向无穷，微小的计算误差将会引发巨大的几何误差。
几何理论的计算方法
从计算方法角度而言，几何理论的计算方法非常丰富，大致可以分为如下几类：
组合计算方法
许多几何和拓扑对象可以被表示成图，图论的大多数算法可以归结为组合方法。例如布劳威尔不动点的构造性方法可以归结为图的染色问题（Spencer Lemma），如图4所示。计算拓扑的许多问题，如流形的同伦群和同调群，都可以归结为组合计算问题，例如判定复杂拓扑曲面上一条封闭曲线是否能够缩成一个点等等。
强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序
4 （Spener's walk）组合方法计算不动点

我们计算的主要对象是几何流形和拓扑空间，绝大多数情况下我们需要将它们离散化。最为常见的离散化方法就是三角剖分。这里涉及到两个基本问题：三角剖分是否存在；如若存在，如何选取最优剖分。光滑流形存在三角剖分，但是一般高维拓扑流形不见得可以被三角剖分。那么是否所有拓扑流形都可以用光滑流形来替代呢？米尔诺的微分拓扑理论揭示了拓扑结构和微分结构之间的巨大差别，从而在理论上否定了用光滑流形逼近拓扑流形的可能。如果存在三角剖分，如何根据问题本身来选取最优方案？例如如何三角化一张光滑的带度量的曲面，使得离散曲率收敛于光滑曲率？离散法丛理论给出了具有普遍意义的指导，离散共形映射和Delaunay Refinement算法给出了具体的计算流程。图5显示了这一方法的计算示例。高维流形的离散化依然具有很多尚未解决的开放问题。
强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序
图5 保持曲率测度的三角剖分

符号计算方法
符号计算将数学符号作为计算对象，通过对符号进行运算得到结论。例如一些偏微分方程存在形式通解，通过符号计算我们可以得到解的表达式。对于代数方程，多元线性方程组的通解可以用方程系数的代数运算求出，推广到多元多项式方程组，其解可以类似推导。当然，我们知道高阶代数方程不存在求根公式，但是通过对方程化简变形，我们可以极大的简化求解过程。或者等价地，我们可以计算多元多项式环中理想的满足特定条件的基底。符号计算的基本方法包括吴文俊方法和Grobner基底方法。由希尔伯特定理，我们知道所有的多项式理想都是有限生成，因此Grobner基底方法的收敛性得以保证。但是，迄今为止，人们并不清楚这些算法的时间和空间复杂度的上界，一些实例表明其上界远超指数级。符号计算完全精确，但是效率较低。符号计算广泛应用于机器人路径规划，数控机床中的样条曲面求交问题。大量的代数几何问题，代数数论问题，群论问题都是基于符号计算。特别地，到目前为止，符号计算是机器定理证明的最主要方法，它代表了“人工智能”方向最为智能的部分-数学推理。机器定理证明和人脑定理证明的多方面比较，例如洞察角度，深刻程度，几何直观，联想广度等等，这些都是饶有兴味的哲学科学问题。
数值计算方法
在几何计算方向占据统治地位的是数值计算方法，部分归因于大多数几何问题不存在解析解，只能用数值解加以近似。最为经典的自然是几何偏微分方程的有限元解法。流形经过三角剖分，函数被分片多项式函数所逼近，椭圆型微分算子被离散化成正定线性算子，偏微分方程被转化成线性方程组。在适当的三角剖分下，黎曼度量的信息反映在线性算子的各项系数（权重）上面。应用索伯列夫空间理论，可以证明离散数值解依照特定范数收敛于连续解。这种方法可以直接推广到计算曲面间调和映照，和计算曲面上调和微分构成的上同调群，从而进一步计算曲面间的共形映射，拟共形映射。给定曲率求曲面上相应的黎曼度量，并且和初始度量共形等价，这需要用到曲面Ricci曲率流的方法。Ricci曲率流可以看成是曲率的非线性热流方法，本质上这一方法可以转化为非线性凸优化问题。数值计算方法源远流长，种类繁多，思想迥异，博大精深。
概率方法
概率方法思想奇特，妙不可言，程序短小精悍，适于并行。脍炙人口的例子首推黎曼流形的热核计算问题。热核（heat kernel）是流形至为重要的等距不变量，其概率解释为从一点出发的布朗运动在给定时刻达到另外一点的概率。通过在流形上模拟数目庞大的随机行走，热核可以被精确的估算出来。几何中的任何概念，如果具有概率解释必然能够被概率方法计算出来：比如曲面边界的调和测度（harmonic measure），曲面的共形不变量-极值长度( extremal length )等等。概率方法对于无穷大曲面的几何问题具有独到的优势，例如通过随机行走的整体行为，我们能够判定无穷大空间的曲率符号等等。
在实践中，不同方法的选取对于问题的求解具有决定性的影响。比如我们考察扭结同痕问题，我们可以采取代数拓扑的方法：在三维欧式空间中挖去扭结，计算剩余的补空间的同伦群。如果两个补空间的同伦群彼此同构，则两个扭结同痕。判断两个群是否同构需要采用符号计算的方法，这是一个NP难的问题。我们也可以采用所谓几何拓扑的方法，首先将补空间三角剖分，然后计算标准的双曲度量。如果两个补空间在各自的标准度量下等距同构，则两个扭结同痕。几何拓扑的方法用到组合和数值算法，计算起来更加实际可行。
强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序
图7 闵科夫斯基问题
同时各种方法相辅相成，很多时候一个问题需要综合多种方法。比如我们求解闵科夫斯基问题，如图7所示，给定一个凸多面体各个面的法向量，和各个面的面积，将凸多面体构造出来。这一问题可以用变分问题的数值方法加上组合方法解出，我们将各个支撑平面的截距设为未知变量，在各个支撑平面的截距之和为常数的限制下极大化多面体的体积。依随截距的变化，多面体的组合结构随着变化。这种组合结构依随几何和拓扑的变化而变化是几何计算的一个显著特点。例如在Ricci曲率流的计算过程中，曲面的三角剖分依随黎曼度量的变化而变化，从而使组合结构和背景度量相互协调一致。
强力推荐：透彻领悟数学之美——当抽象的几何理论转化为算法程序
图7 闵科夫斯基问题

总结和展望
在人类历史长河之中，抽象艰深的几何理论只能被极少数的职业数学家所掌握，许多深刻的概念和定理只能被数学家所透彻领悟和审美。现代教育虽然有所改善，但是许多基本的概念，例如黎曼度量、上同调群、域的超越扩张，依然只能被专家所理解和使用。计算机技术的发展使得抽象的几何理论可以被转化为算法程序，人们即便无法理解艰深的理论，也能直接使用和感受。计算机将几何理论请出象牙塔，在社会实践中真正发挥它的巨大威力！
目前，纯粹数学和计算机科学是两个分立的教育领域，年轻学子几乎不可能得到两方面充分的训练。两个领域的哲学思想，训练技巧，价值观念，生态环境天渊之别，这进一步割裂了他们之间的内在联系。但是，几何计算化顺应历史的洪流，它正在隐蔽而坚定地发展着，生机无限，势不可挡。我们坚信，历史潮流，浩浩荡荡，顺之者昌，逆之者亡。几何计算化必将改变教育和科学，改变工业和医疗，改变人类文明的进程……


原文链接：
http://mp.weixin.qq.com/s__biz=MzA3OTgzMzUzOA==&mid=210326179&idx=1&sn=6730b56785b9e2138eed0e265948ea9c&scene=5&srcid=09159YFqUWMUF83UVcOKSkRp#rd

我的更多文章

下载客户端阅读体验更佳

APP专享