整数关系探测的误差可控算法与应用

项目名称： 整数关系探测的误差可控算法与应用

项目编号： No.11501540

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 陈经纬

作者单位： 中国科学院重庆绿色智能技术研究院

项目金额： 18万元

中文摘要： 近年来，误差可控的符号-数值混合计算已越来越受到学术界和工业界的重视。其中，一个重要的研究方向以采用近似计算获得准确值为研究内容，并被成功地应用到包括信息技术、数字化设计制造等国民经济关键领域。然而这一方向所采用的基本工具之一——整数关系探测算法（二十世纪十大算法之一）——的复杂度理论仅建立在精确实数计算模型下，缺乏实际的位复杂度分析，阻碍了该方向的发展。本项目针对这一现状，拟通过揭示整数关系探测和格约化之间的本质联系、改进浮点格约化算法的相关技术，设计基于浮点算术的误差可控高效整数关系探测算法，并给出其位复杂度分析。鉴于申请者在整数关系探测、格约化以及采用近似计算获得准确值等方面已有一定的研究基础，通过本项目的实施，有望攻克整数关系探测算法的位复杂度分析难题，进而推动采用近似计算获得准确值这一方向的进一步发展。

中文关键词： 误差可控算法；整数关系；格约化；浮点算术

英文摘要： Over the last few decades, error-controllable hybrid symbolic-numeric computation has been receiving increasing attention from both academic community and industry. In this field, there exists an important direction that focuses on the topic of obtaining exact value by approximate computing. Many results of this direction have been successfully applied in several areas, including information technology and digital design and manufacturing. However, as one of the most frequently used tools in this direction, the integer relation finding algorithm, named one of the top 10 algorithms in the twentieth century, has no bit-complexity analysis, while it is only analyzed under the exact real arithmetic model. This state has already impeded the direction of obtaining exact value by approximate computing. In the present project, we are going to investigate the essential link between integer relation finding and lattice reduction, adapt the techniques used in floating-point lattice reduction algorithms, design efficient floating-point integer relation finding algorithms, and analyze their bit-complexity bounds. The applicant has had several research results related to integer relation finding, lattice reduction and obtaining exact value by approximate computing. In view of these facts, the bit-complexity bounds of the integer relation finding algorithm will be hopefully disclosed during this project.

英文关键词： error-controllable algorithm;integer relation;lattice reduction;floating-point arithmetic