论文部分内容阅读
随着计算机计算能力的迅猛发展,计算机所能处理问题的规模越来越大,提高计算的可信性和高效性已成为工业界和科学界的共同目标.符号计算可以得到问题的精确结果,但计算复杂度高;数值计算可以高效地处理实际问题,但仅能得到近似结果.因此,由符号和数值计算各自的优点孕育而生的符号-数值混合计算已成为近年来一个炙手可热的研究方向.然而,准确值和近似值之间存在一个天然的鸿沟.幸运的是,张景中、冯勇等提出了“采用近似计算获得准确值”的思想,并成功给出了针对有理数域的解决方案.本文着眼于将上述思想的适用范围扩大至代数数域,讨论若干相关的计算问题,设计、分析和实现解决这些问题的高效、可信的算法,并探讨它们在符号-数值混合计算中的应用.
本文的主要创新在于:
一、发现了欧几里得格和线性空间的求交问题与欧几里得空间中有限生成加法子群的分解问题之间的对偶关系,以此为基础对二十世纪十大算法之一的整数关系探测算法PSLQ给出了一个新的理解,并从中得到第一个计算欧几里得空间中有限生成加法子群分解的算法.
二、克服了PSLQ算法对于一组复数只能输出Gauss整数关系的不足,提出SIRD同步整数关系探测算法.并以此为基础提出了解决代数数极小多项式近似重构问题的一个新的、完整的、有效的解决方案.
三、给出了一个计算有理系数二元多项式有理不可约因子的新算法.理论分析和实验数据均说明,该算法非常高效,尤其是对稀疏的有理系数二元多项式,效果甚佳.
本文也讨论了一个基于高次代数数近似值的有理系数二元多项式因式分解算法,该算法对较小规模的实例具有较好的效果.
此外,对于著名的LLL算法的一种特殊情形,本文采用一个全新的复杂度分析方法得到了一个有趣的结果.