代数方程组求解及其复杂度分析

Many practical problems can be transformed into solving polynomial systems, for example, the isotopic meshing of algebraic curves and surfaces, crack cryptography, etc. They are used widely in the fields of geometry model, computational sciences, engineering, cryptology, etc. By the development of technology, the requirement for reliability of solutions and efficiency of algorithm has been increased. Then, hybrid methods which have both the precision of numerical methods and the efficiency of symbolical methods occur. We will analysis the complexity of existence methods solving algebraic systems. After finding the modules consuming most resource, we would find approaches to improve the efficiency, and find the real roots of the general zero dimensional algebraic systems with any given precision. For some special algebraic systems, we will raise the high quality algorithms and develop the software.

科学与工程中的许多问题都可以归结为代数方程组的求解，如代数曲线曲面的误差可控的逼近，密码的破解等。他们在几何造型、密码学等方面有着重要的应用。随着科技的进步和工业需求的提升，我们对解的可信度和求解效率的要求也随之提高。兼顾符号计算的精确性和数值计算的高效率从而诞生了符号和数值混合计算。本项目拟通过对已有算法进行复杂度分析，针对现有求解算法中运算量大的模块，找到提高效率的途径，并运用符号和数值混合计算方法对一般零维代数系统给出给定精度的逼近实解，并对一些特殊的系统给出可信解、形成高效快速算法并开发软件。

科学与工程中的许多问题都可以归结为代数方程组的求解，如代数曲线曲面的误差可控的逼近，密码的破解等。他们在几何造型、密码学等方面有着重要的应用。随着科技的进步和工业需求的提升，我们对解的可信度和求解效率的要求也随之提高。兼顾符号计算的精确性和数值计算的高效率从而诞生了符号和数值混合计算。本项目通过对已有算法进行复杂度分析，针对现有求解算法中运算量大的模块，找到提高效率的途径，并运用符号和数值混合计算方法对双变元零维代数方程组和一般零维代数系统两种系统分别给出了给定精度的逼近实解，并分别进行了复杂度分析，形成了高效快速算法和完成了Maple程序。通过理论分析和实验对比，两种算法均比现有的绝大多数算法速度更快，效率更高。在此基础上，我们完成了两篇学术论文，稿件正在修改中，即将投出。此外，我们还申请了两项专利，其中一项已经获得授权，一项已经进入实际审查流程。我们认为，通过一年的努力，我们完成了项目立项时设定的目标。