摘 要: 针对多交换策略的HJLS-PSLQ算法无法保证终止性的问题，分析了无法终止的原因，进而提出带限制条件的多交换HJLS-PSLQ算法改进。首先分析了原版HJLS-PSLQ算法的终止性，然后考察多交换策略下的不等式成立条件，进而发现交换元素不能保证关系结果范数逐步增大。在改进算法中，增加了交换候选元素的下界，使之能保证算法的终止性，最终完善了多交换算法的改进与证明。最后将它使用在寻找最小多项式的应用中，对比已有的HJLS-PSLQ算法，表明多交换改进算法确实能减少算法的循环次数并减少约2/3的时间。
关键词: 整数关系；并行计算；HJLS；PSLQ
0引言
整数探测算法作为新兴的计算数论中一个重要部分，在越来越多的理论应用中扮演着“开拓者”的角色。尤其是在新公式、新理念的发现上，起到了决定性的作用，这个过程被称做“实验数学”。实验数学是伴随着计算机运算能力的迅猛发展而发展起来的。在当今科技日新月异的时代，科学理论的发展借助计算机的发展而敏捷创新，实验数学正是在此酝应而生。
在数学定理的推导证明与应用的过程中，以前不仅需要艰深的数学理论知识，而且由于中间过程的膨胀问题，符号计算被认为是低效且繁杂的。然而，工程中使用的数值计算只能给出近似的结果，对于多步骤的过程无法保证可靠性。
最新的理念研究结合符号计算与数值计算，使用近似计算作为中间过程，却最终得到精确的符号表达式。这种方法采用的是误差可控的符号-数值混合计算，或称为零误差计算[1]。一个典型的应用是重构有理数算法[2]，可以从有理数的的近似小数中恢复出它的确切值。许多零误差算法，如代数数重建[3,4]、多项式分解[5,6]等，最后都转化为求整数关系的问题。
非零向量被称为向量的整数关系，如果，其中“”表示向量的内积。那么整数关系的问题即是任意给定一个向量，找出其中满足的最短向量。
对于二维实向量的解答可以追溯到欧氏几何的时代的辗转相除法，在其后的二千年间不断有学者继续研究这个问题，包括雅可比、哈密尔顿等都留有手稿。然而对于更高维的向量，直到1977年才由Ferguson和Forcade突破欧几里得算法，可以得到任意维数的整数关系或者断言在指定长度内没有满足条件的向量[7]。其后，在1986年Hastad证明了该问题的一个多项式时间算法，即HJLS[8]。紧接着，Ferguson和Bailey发表一个更常用的整数关系探测算法PSLQ[9]。Borwein证明PSLQ和HJLS都是基于1979年公布的算法的泛化[10]。此外，Meichsner 证明HJLS的消去等价于PSLQ的参数设置[11]。特别的，Chen、Stehle 和Villard在2013年对HJLS和PSLQ从格的角度创新重新阐释[12]。
作者：李柳奇