专栏
当抽象的几何理论转化为算法程序

1 几何计算化面临的挑战

几何计算化对于现代几何理论和计算机科学都提出了强有力的挑战。单纯从理论方面而言,就已经困难重重;考虑到计算机实现, 我们不可避免地要渡过许多难以逾越的天堑。

1)存在性与构造性证明

经典几何理论中的大量存在性证明都是基于抽象的拓扑方法,而非直接的构造法。从证明本身,我们只知道解的存在,但是无法具体找到解。这需要进一步发明新的构造性算法,往往构造性证明比存在性证明更加需要对几何现象深刻理解和洞察。

比如黎曼面的单值化定理,给定一个封闭的带黎曼度量的可定向曲面,存在一个和初始度量共形等价的度量,其诱导常值高斯曲率。19世纪末,单值化定理被复变函数方法证明出来。但是这种方法只给出了存在性,却无法直接构造出常曲率度量。直至近百年后,Hamilton的Ricci曲率流方法才给出构造性方法。图1直观展示了曲面单值化定理,亏格为0的曲面保角地变成球面;亏格为1的曲面可以保角地展开在平面上;高亏格的曲面可以周期性地展开在双曲平面上。


图1 单值化定理

对于大量的几何存在性定理,经典的理论只有抽象的证明,却没有构造性方法,寻求构造性的证明方法本身需要旷日持久的艰苦努力。

2)光滑结构对离散表示

经典几何理论特别是微分几何和偏微分方程理论都是建立在光滑微分结构之上。计算机内存有限,所有的数据结构都是离散的。如何用离散来计算连续,有限来表示无限,这本身就是难以调和的矛盾。一种方法是用离散来逼近连续,例如经典的有限元方法。另外一种方法即离散几何理论本身则更为直截了当。例如Hamilton的曲面Ricci曲率流的理论是建立在光滑曲面上的,最近丘成桐学派建立了离散曲面上的Ricci流理论,这套理论是直接建立在离散的多面体曲面上的,并且和Hamilton的理论等价。图1显示了离散Ricci流方法得出的曲面单值化计算结果。

再比如,经典的蒙日-安培方程理论和闵科夫斯基理论。表面上看,蒙日-安培方程本身需要函数的高阶光滑性,但是它的几何本质却是只需要连续性。丘成桐学派建立了离散蒙日-安培方程理论,利用凸几何的方法求解。图2给出了从曲面到平面圆盘的保持面积元的映射,其计算过程依赖于求解离散蒙日-安培方程。


图2 单值化定理

3)计算复杂度

许多自然的几何和拓扑问题即便有计算方法,其算法都是具有指数级复杂度的。比如曲面上的复杂封闭曲线在同伦群中的最短表示问题。假如亏格为2的曲面上给定同伦群的基底,任给一条封闭曲线,其同伦类为同伦群中的一个元素,可以表示成基底的乘积,但是表示方法不唯一。在所有可能的表示方法中,求最短的表示。这一问题对于图灵机模型而言是NP问题。

目前,机器定理证明的主要方法是求多项式环中理想的一族生成元,生成元具有特殊的性质,满足一定的要求。主要计算工具是Groberner基底方法。这一方法的空间复杂度非常之高,虽然理论上可以广泛解决机器定理证明的问题,但是实际上作用非常有限。

4)线性对非线性

线性方程现在已经研究得比较透彻,存在大量实用的算法和软件工具。工程中的线性偏微分方程,可以用差分法,傅里叶变换法或者有限元方法转化为线性方程。但是绝大多数自然的拓扑和几何问题都是非线性的,在这种情况下我们寻求变分法。在理想情况下,几何问题被转化为某一凸能量的变分从而使得计算变成凸优化。例如上文中提到的用曲率流方法来构造曲面的黎曼度量,实际上对应着凸能量(所谓熵能量)的优化;最优传输问题的蒙日-安培方程的解也是某种体积能量的极值解。当然,也存在大量的非线性几何问题,我们无法直接用凸能量的变分法处理,比如求高亏格闭曲面之间的泰西米勒映射,或周期映射的不变双曲度量等等。

5)稳定性

许多拓扑和几何问题的解本身是不稳定的,这意味着微小的初始误差或过程中的计算误差将会使结果相差十万八千里。例如混沌问题,动力系统中的三体问题等等。这种不稳定性是问题本身的性质所决定,和计算方法的设计和选取无关。另外一种稳定性是由计算误差所引发。比如经典计算几何中的De⁃launay三角剖分,平面族的包络,离散点的凸包问题。这些问题的几何本质清楚明晰,但是计算中的微小误差就会引发组合结构的崩溃,其内在原因在于计算机只能近似表达实数及其运算结果,而组合结构的搭建却需要绝对精确,不容误差。对于只涉及代数运算的计算几何问题,一种解决方法是在有理数域上进行精确的代数运算,用软件表示长整数。这种方法速度缓慢,但是保证了计算的正确性。另外,许多几何计算需要在特殊的黎曼度量下展开,对于双曲度量而言,靠近双曲空间的边缘处,共形因子趋向无穷,微小的计算误差将会引发巨大的几何误差。

2 几何理论的计算方法

从计算方法角度而言,几何理论的计算方法非常丰富,大致可以分为如下几类。

1)组合计算方法

许多几何和拓扑对象可以被表示成图,图论的大多数算法可以归结为组合方法。例如布劳威尔不动点的构造性方法可以归结为图的染色问题。计算拓扑的许多问题,如流形的同伦群和同调群,都可以归结为组合计算问题。

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

2)符号计算方法

符号计算将数学符号作为计算对象,通过对符号进行运算得到结论。例如一些偏微分方程存在形式通解,通过符号计算我们可以得到解的表达式。符号计算的基本方法包括吴文俊方法和Grobner基底方法。由希尔伯特定理,我们知道所有的多项式理想都是有限生成,因此Grobner基底方法的收敛性得以保证。但是,迄今为止,人们并不清楚这些算法的时间和空间复杂度的上界,一些实例表明其上界远超指数级。符号计算完全精确,但是效率较低。符号计算广泛应用于机器人路径规划,数控机床中的样条曲面求交问题。大量的代数几何问题,代数数论问题,群论问题都是基于符号计算。特别地,到目前为止,符号计算是机器定理证明的最主要方法,它代表了“人工智能”方向最为智能的部分——数学推理。机器定理证明和人脑定理证明的多方面比较,例如洞察角度,深刻程度,几何直观,联想广度等等,这些都是饶有兴味的哲学科学问题。

3)数值计算方法

在几何计算方向占据统治地位的是数值计算方法,部分归因于大多数几何问题不存在解析解,只能用数值解加以近似。最为经典的自然是几何偏微分方程的有限元解法。流形经过三角剖分,函数被分片多项式函数所逼近,椭圆型微分算子被离散化成正定线性算子,偏微分方程被转化成线性方程组。在适当的三角剖分下,黎曼度量的信息反映在线性算子的各项系数(权重)上面。应用索伯列夫空间理论,可以证明离散数值解依照特定范数收敛于连续解。这种方法可以直接推广到计算曲面间调和映照,和计算曲面上调和微分构成的上同调群,从而进一步计算曲面间的共形映射,拟共形映射。给定曲率求曲面上相应的黎曼度量,并且和初始度量共形等价,这需要用到曲面Ricci曲率流的方法。Ricci曲率流可以看成是曲率的非线性热流方法,本质上这一方法可以转化为非线性凸优化问题。数值计算方法源远流长,种类繁多,思想迥异,博大精深。

4)概率方法

概率方法思想奇特,妙不可言,程序短小精悍,适于并行。脍炙人口的例子首推黎曼流形的热核计算问题。热核是流形至为重要的等距不变量,其概率解释为从一点出发的布朗运动在给定时刻达到另外一点的概率。通过在流形上模拟数目庞大的随机行走,热核可以被精确地估算出来。几何中的任何概念,如果具有概率解释必然能够被概率方法计算出来:比如曲面边界的调和测度,曲面的共形不变量-极值长度等等。概率方法对于无穷大曲面的几何问题具有独到的优势,例如通过随机行走的整体行为,我们能够判定无穷大空间的曲率符号等等。

在实践中,不同方法的选取对于问题的求解具有决定性的影响。比如我们考察扭结同痕问题,我们可以采取代数拓扑的方法:在三维欧式空间中挖去扭结,计算剩余的补空间的同伦群。如果两个补空间的同伦群彼此同构,则两个扭结同痕。判断两个群是否同构需要采用符号计算的方法,这是一个NP难的问题。我们也可以采用所谓几何拓扑的方法,首先将补空间三角剖分,然后计算标准的双曲度量。如果两个补空间在各自的标准度量下等距同构,则两个扭结同痕。几何拓扑的方法用到组合和数值算法,计算起来更加实际可行。

同时各种方法相辅相成,很多时候一个问题需要综合多种方法。比如我们求解闵科夫斯基问题,给定一个凸多面体各个面的法向量,和各个面的面积,将凸多面体构造出来。这一问题可以用变分问题的数值方法加上组合方法解出。

3 总结和展望

在人类历史长河之中,抽象艰深的几何理论只能被极少数的职业数学家所掌握,许多深刻的概念和定理只能被数学家所透彻领悟和审美。计算机技术的发展使得抽象的几何理论可以被转化为算法程序,人们即便无法理解艰深的理论,也能直接使用和感受。计算机将几何理论请出象牙塔,在社会实践中真正发挥它的巨大威力。

目前,纯粹数学和计算机科学是两个分立的教育领域,两个领域的哲学思想、训练技巧、价值观念和生态环境有着天渊之别,这进一步割裂了他们之间的内在联系。但是,几何计算化顺应历史的洪流,正在隐蔽而坚定地发展着,生机无限,势不可挡。我们坚信,几何计算化必将改变教育和科学,改变工业和医疗,改变人类文明的进程。

文/顾险峰
作者简介 1美国纽约州立大学石溪分校计算机系终身教授; 清华大学丘成桐数学科学中心访问教授。
(责任编辑  王丽娜)