SIRD:一个同步整数关系探测算法  

SIRD:An Algorithm for Simultaneous Integer Relations Detection

作　　者：陈经纬[1,2] 冯勇[1] 秦小林[1] 张景中[1] 

机构地区：[1]中国科学院重庆绿色智能技术研究院,重庆401122 [2]中国科学院成都计算机应用研究所,四川成都610041

出　　处：《四川大学学报（工程科学版）》2011年第6期127-132,共6页Journal of Sichuan University (Engineering Science Edition)

基　　金：国家"973"计划资助项目(2011CB302400);国家自然科学基金资助项目(10771205);中国科学院西部之光资助项目

摘　　要：为了解决一组实数向量的整数关系探测问题,通过广义的Hermite约化方法来约化超平面矩阵,基于著名的PSLQ算法,给出了一个同步整数关系探测的新算法SIRD;并且在计算机代数系统Maple中采用软件精度数据类型"sfloat"实现了SIRD算法和另一个同步整数关系探测算法HJLS,数值实验说明本文的算法相比HJLS算法更高效;最后,部分采用硬件精度数据类型"hfloat"给出了SIRD算法在Maple中的另一种的实现,并将其应用到代数数极小多项式的重构问题中,进一步拓展了张景中和冯勇提出的"采用近似计算获得准确值"这一思想的应用范围.In order to reduce the hyperplane matrix when detecting simultaneous integer relations for several real vectors,a generalized Hermite reduction was presented.Based on generalized Hermite reduction and patial sum-lower trapezoidal orthogonal decomposition（PSLQ） algorithm,the algorithm of simultaneous integer relations detection（SIRD） was proposed.SIRD was implemented in computer algebra system Maple in two different routes of software float-point data type ＂sfloat＂ and hardware float point data type ＂hfloat＂.The SIRD was compared with HJLS,and the results showed that SIRD is better.Furthermore,SIRD was applied to get a complete method for finding the minimal polynomial of an unknown complex algebraic number from its approximation.

关 键 词：整数关系 代数数 极小多项式 符号数值计算 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]