基于同伦方法的代数方程并行计算的理论、实现及其应用

数学、物理、生化、经济等领域中的许多非线性问题常常归结为求解代数方程组。不同于牛顿迭代等数值计算方法，我们的目标是计算代数方程组所有的解。目前的方法包括Groebner基、吴方法、结式方法等符号计算的方法。但从计算效率的角度看，我们必须认识到这些源于实际问题的方程组往往具有大规模、稀疏等特点。如何利用系统的稀疏结构并结合计算机技术来高效率、高精度求解大规模系统既是计算数学的国际前沿问题也是计算复杂性的重要问题。我们的基本思想是利用和发展适合并行数值计算的同伦方法并结合符号计算的精确性来高效准确地求解大规模代数方程。本课题拟争取在以下三个方面取得突破：1.在理论上针对不同稀疏结构提出不同的同伦方法。2. 在算法设计和软件开发中充分利用最新的计算机技术实现高效稳定的并行计算。3. 将该方法和软件应用到工程物理、生化、经济等其他领域的实际问题，并结合这些典型问题来提高和完善我们的理论和软件。

首先，研究了零维半代数系统的求解问题，主要思想是同伦算法结合区间牛顿迭代。这样既高效也数值稳定。成果发表在2012亚洲计算机数学大会的论文集中。在此基础之上我们又研究了带重根的零维代数方程组的实根计算和验证算法，并编程实现，软件包的工作成果发表在中文核心期刊《计算机应用》。其次，我们知道高维半代数系统的求解问题长期以来是个国际难题，我们目前的工作是对于高维代数系统，通过嵌入到高维空间并加入切空间条件将流形解化为零维解，再构造特殊同伦以保证在每个流形解上都能找到一个实解。该工作发表在符号计算顶级会议ISSAC论文集中。..为化简代数方程，我们研究了稀疏多项式因式分解。第一个工作是基于混合计算的精确两变元因式分解。主要贡献在于充分利用多项式的稀疏性，克服了传统Hensel提升算法的不保持稀疏性的致命缺点。该成果已被诸多SCI期刊Science China Mathematics, Journal of Systems Science and Complexity和ACM Communications in Computer Algebra录用。另一项工作是完成了多变元数值因式分解的几何含义和几何结构分析。其次，我们基于Ruppert矩阵和同伦方法的牛顿多胞体研究包含对稀疏结构的研究。该成果已经提交到SCI期刊Math. Comp。..在应用方面，我们针对一组串联的化学反应器建模，采用快速延拓算法结合同伦方法对于n个反应器得到一般性的结论。该项工作发表在2012亚洲仿真大会的论文集中。针对大规模的微分、代数方程的化简问题，我们充分利用原系统的稀疏性，提出一种基于最小结构奇异子集的分块快速延展方法。该成果已于近期申请专利。同时，我们也将成果应用于电力潮流和生物系统稳定点计算上，成果发表于EI期刊Applied Mechanics and Materials和SCI期刊Journal of Computational and Theoretical Nanoscience和Journal of Applied Mathematics上。