解多项式方程组的同伦分治法

Polynomial systems often appear in science and engineering. It is a big challenge for solving polynomial systems in computational mathematics. The homotopy method is the primary numerical method and can theoretically find all the isolated solutions of any polynomial systems, but many problems can’t be solved in a reasonable time by those existing homotopies, because of their intrinsic complexity. On the basis of our previous work, we propose a homotopy divide and conquer method for solving polynomial systems. Differing from the previous homotopies that transform target systems to start systems who can be solved straightforwardly, the proposed homotopy keeps the deficient and symmetry structure of target systems as much as possible, and then the start systems can be decomposed by eliminations into several groups of subsystems with lower dimensions, less bezout numbers or BKK bounds or the same structure of terms. Hence, start systems can be solved effectively and efficiently. We plan to research on construction, theoretical analysis and implementation of homotopy divide and conquer methods for solving general polynomial systems and some challenging practical problems.

多项式方程组是科学和工程中常见的数学模型，其理论和解法是代数几何和计算数学中的重要而困难的课题。同伦方法是解多项式方程组的主要数值方法。理论上可以用同伦方法求任何多项式方程组的全部孤立解，但由于问题的固有复杂性，很多实际问题无法在容许时间内用现有的同伦方法解决。本项目将在前期工作基础上，研究解多项式方程组的同伦分治法。该方法并不像已有的同伦方法那样，将目标多项式组同伦形变为直接可解的初始多项式组，而是尽可能多地保持问题的稀疏和对称结构，而初始多项式组可以分解为若干个子方程组，它们或者能通过消元来化简为低维、具有低Bezout数或BKK界的问题，或者具有相同的单项式结构，因而可以用较小的代价求解。我们将研究适合一般问题的同伦分治法和针对重要应用问题的特殊同伦分治法的构造、理论分析和程序实现。

科学和工程中经常需要解多项式方程组，它可能直接来自于工程问题（如声呐信号处理）或是某些模型转化而来（如某些微分方程离散化）。解多项式方程组的理论和快速算法具有十分重要的意义。一、对于一般的亏欠多项式方程组，我们提出同伦分治法，该方法并不像已有的同伦方法那样，将目标多项式组同伦形变为直接可解的初始多项式组，而是尽可能多地保持原问题的稀疏和对称结构，其可以分解为若干个子方程组，它们或能通过消元来化简为低维、具有低Bezout数或BKK界的问题，或具有相同的单项式结构，从而可以用较小的代价求解。二、在正电子湮灭寿命谱分析、放射性探测以及解常系数齐次微分或差分方程等问题中有重要应用的稀疏插值问题。我们对等距情形下的稀疏插值问题，通过变元替换转化为解多项式方程组问题，并利用其对称结构给出一个高效的同伦，其在置换意义下只需要跟踪一条解路径即可得到全部孤立解。对于非等距情形，采样点由于观测设备的不精确可能会出现部分采样点失效或者缺失的情况，这样就会出现跳点的情况。此时，经典的Prony方法无法使用，而我们将其转化为多项式方程组求解依然有效且仍然保持置换意义下对称性。但是对孤立解的个数上界的估计比较困难。我们给出了一种估计，只给出了部分证明。假定孤立解上界估计正确，多项式方程组的解就可以分为多个等价类，每个等价类求一个代表解即可，将大大节省了计算量。我们证明了解路径的可达性和光滑性。三、对于多项式非线性椭圆方程和椭圆方程组多解问题，我们提出一种特征函数展开法，将原微分方程问题转化为解多项式方程组问题。该多项式方程组具有一种特殊的D4对称结构，构造保持该特殊结构的同伦，节省了大量的计算量。从多项式非线性椭圆方程多解问题扩展到多项式非线性椭圆方程组多解问题，我们将此类问题，先在较粗糙状态下，利用特征函数展开将其离散为多项式组，保持其特有对称性构造同伦并求解这个多项式系统，去除伪解，逐步加细并反复使用上述过程。