稀疏多项式组和混合三角多项式组高效同伦算法研究及应用

Finding all solutions of the polynomial systems and the mixed trigonometric polynomial systems is a common problem in many fields of science and engineering, the main difficulty of this problem is the design of the global convergence method. In this project, we mainly focus on the numerical methods, hybrid methods and symbolic methods. For the polynomial systems transformed from the mixed trigonometric polynomial systems, we study its special structure and design the efficient numerical-symbolic method. Furthermore, we generalize these methods to the study of general polynomial systems, and design efficient numerical method based on the sparse structure. For the sparse mixed trigonometric polynomial systems, we give a more accurate upper bound on the number of isolated solutions, and then design the direct homotopy method based on this upper bound. For the geometric constraint problem, we will give the uniform constructive method for the equation corresponding to each constraint. Additionally, we combine symbolic methods for polynomial systems and numerical methods for eigenvalue problems to find the real solutions and other desired solutions. Through this project, we want to give the more accurate estimation on the upper bound of the solution number, implement the combination of product homotopy and coefficient-parameter homotopy, continue the study of finding desired solutions, extend the homotopy methods to the study of the mixed trigonometric polynomial systems, prove the convergence of the algorithms, develop the practical software and apply it to solve the practical problems.

科学与工程的许多领域经常遇到多项式组和混合三角多项式组求解问题，大范围收敛算法和多解问题是该问题求解的重点和难点。本项目拟研究求解该问题的数值方法、混合方法、符号计算方法。从由混合三角多项式组转化来的多项式组入手，研究其特殊结构，设计综合利用符号计算和同伦算法的高效混合算法。进一步，将此方法推广到一般多项式组的求解中，充分利用问题的代数结构设计高效率的求解算法。对稀疏混合三角多项式组，给出孤立解个数上界的更优估计，并依此构造有效的直接同伦方法；对几何约束问题，对所有约束给出统一的方程构造方法。在指定解方面，将符号计算方法与特征值问题的数值解法结合，求实解或具有指定意义的解。通过此项目，我们将给出孤立解个数上界的更优估计、实现乘积同伦与系数参数同伦的结合、开展利用特征值算法求指定解的研究、拓展同伦方法在混合三角多项式组中的应用、证明算法的收敛性、编制相应软件并用以解决几何约束问题等实际应用。

本项目主要考虑了多项式组、混合三角多项式组全部解的数值求解算法及其在多参数特征值问题、张量分解和低秩逼近中的应用。在多项式组方面，我们明确了问题的稀疏结构对孤立解个数的影响，结合线性规划的方法制定了方程是否分解为乘积形式的策略，引入符号计算的相关算法设计了部分乘积的混合同伦方法，理论上分析了算法的计算复杂性并证明了算法的收敛性。在混合三角多项式组方面，分析了相关应用问题的特殊结构，给出了问题的一般形式，在此基础上结合多项式组的混合方法设计了高效的两步法：混合同伦+系数参数同伦方法。在应用推广方面，我们将多项式组的相关理论推广到多参数特征值问题的数值求解中，给出了问题解个数的精确上界，明确了问题的奇异性，给出了求解模型修正问题对应的奇异多参数特征值问题的同伦方法和行列压缩方法，借助数值代数和代数几何的相关知识实现了算法收敛性的理论证明和复杂性分析。在张量低秩逼近方面，给出了问题对应的矩阵多项式方程组的具体形式，在此基础上给出了一次更新两个向量的交替方向法。实际应用方面，编写了求解相关问题的应用软件包并应用于实际问题。