SIRD:一个同步整数关系探测算法
SIRD:An Algorithm for Simultaneous Integer Relations Detection
作者：陈经纬(中国科学院 重庆绿色智能技术研究院；中国科学院 成都计算机应用研究所;中国科学院 研究生院)；冯勇(中国科学院 重庆绿色智能技术研究院)；秦小林(中国科学院 重庆绿色智能技术研究院)；张景中(中国科学院 重庆绿色智能技术研究院)
Author：Chen Jingwei(Chongqing Inst. of Green and Intelligent Technol.,CAS;Chengdu Inst. of Computer Application,CAS;Graduate Univ., CAS)；Feng Yong(Chongqing Inst. of Green and Intelligent Technol.,CAS)；Qin Xiaolin(Chongqing Inst. of Green and Intelligent Technol.,CAS)；Zhang Jingzhong(Chongqing Inst. of Green and Intelligent Technol.,CAS)
收稿日期：2011-05-04 年卷（期）页码：2011,43(6):127-132
期刊名称：工程科学与技术
Journal Name：Advanced Engineering Sciences
关键字：整数关系；代数数；极小多项式;符号数值计算
Key words：integer relation;algebraic number;minimal polynomial;symbolic-numeric computation
基金项目：国家“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.
【关闭】
