整数关系探测的误差可控算法与应用
项目介绍
AI项目解读
基本信息
- 批准号:11501540
- 项目类别:青年科学基金项目
- 资助金额:18.0万
- 负责人:
- 依托单位:
- 学科分类:A0410.算法复杂性与近似算法
- 结题年份:2018
- 批准年份:2015
- 项目状态:已结题
- 起止时间:2016-01-01 至2018-12-31
- 项目参与者:赵恒军; 徐晨; 杨文强; 周双;
- 关键词:
项目摘要
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.
近年来,误差可控的符号-数值混合计算已越来越受到学术界和工业界的重视。其中,一个重要的研究方向以采用近似计算获得准确值为研究内容,并被成功地应用到包括信息技术、数字化设计制造等国民经济关键领域。然而这一方向所采用的基本工具之一——整数关系探测算法(二十世纪十大算法之一)——的复杂度理论仅建立在精确实数计算模型下,缺乏实际的位复杂度分析,阻碍了该方向的发展。本项目针对这一现状,拟通过揭示整数关系探测和格约化之间的本质联系、改进浮点格约化算法的相关技术,设计基于浮点算术的误差可控高效整数关系探测算法,并给出其位复杂度分析。鉴于申请者在整数关系探测、格约化以及采用近似计算获得准确值等方面已有一定的研究基础,通过本项目的实施,有望攻克整数关系探测算法的位复杂度分析难题,进而推动采用近似计算获得准确值这一方向的进一步发展。
结项摘要
整数关系探测问题是指:对给定的一组实数 x_1, …, x_n,如何找到一组不全为零的整数 m_1,..., m_n 使得 m_1*x_1+...+m_n*x_n=0?该问题在计算机科学、计算数论、量子场论等诸多领域有重要应用,并由此开创了“实验数学”——用计算的方式发现数学定理——的数学研究新范式,同时,也是张景中院士、冯勇研究员提出的“采用近似计算获得准确值”这一符号数值计算新思想的理论基础。针对已有的 PSLQ 整数关系探测算法( “二十世纪十大算法”之一)缺乏有效的数值分析和数值算法,而基于格基约化 LLL 算法的整数关系计算的理论复杂度上界与实验结果差距明显等问题,本项目主要完成了以下工作:.建立了这两类整数关系探测算法之间的联系,成功设计出采用 PSLQ 算法的策略来进行格基约化的算法。论文发表在国际会议 ICCSN 2017 上,也在第九届全国计算机数学学术会议上报告了相关工作。.基于上述格约化算法与整数关系探测算法之间的联系,我们通过借鉴数值格约化算法的已有经验,成功解决了 PSLQ 算法的数值稳定性问题,设计并分析了相应的数值 PSLQ 算法。论文已在线发表在 JCR 数学类一区刊物 Math. Comp. 上. .应用 LLL 算法求解整数关系时,理论上的复杂度上界与实际的观察出入很大。针对这一问题,我们提出了一个全新的 LLL 算法分析工具,证明了 LLL 算法中迭代次数的一个新的上界。该上界与传统分析得到的上界相比,降低了一个因子 n,这里的 n 是指求解问题的维数。相关论文发表在 ACM 符号与代数计算顶级会议 ISSAC 上。.本项目的实验研究也已完成,我们对已有的计算整数关系问题的开源软件进行了系统的评估与分析,得出的结论是目前基于LLL格基约化的方法应是整数关系计算的首选,而软件包首选推荐本项目的合作者之一,法国 CNRS 的 Gilles Villard 研究员主导开发的 hplll,该软件较 UC Berkley 的 D. H. Bailey 教授开发的 PSLQ 算法的软件包MPFUN2015 效率提高近百倍。相关论文已形成初稿,拟投 ACM 符号与代数计算顶级会议 ISSAC。
项目成果
期刊论文数量(2)
专著数量(0)
科研奖励数量(0)
会议论文数量(5)
专利数量(0)
基于 HElib 的安全电子投票方案
- DOI:--
- 发表时间:2017
- 期刊:计算机应用研究
- 影响因子:--
- 作者:王永恒;徐晨;陈经纬;吴文渊
- 通讯作者:吴文渊
The PSLQ algorithm for empirical data
经验数据的 PSLQ 算法
- DOI:10.1090/mcom/3356
- 发表时间:2018
- 期刊:Mathematics of Computation
- 影响因子:2
- 作者:Yong Feng;Chen Jingwei;Wenyuan Wu
- 通讯作者:Wenyuan Wu
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:{{ item.doi || "--"}}
- 发表时间:{{ item.publish_year || "--" }}
- 期刊:{{ item.journal_name }}
- 影响因子:{{ item.factor || "--"}}
- 作者:{{ item.authors }}
- 通讯作者:{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:{{ item.authors }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:{{ item.authors }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:{{ item.authors }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:{{ item.authors }}
数据更新时间:{{ patent.updateTime }}
其他文献
一种金属有机DMIT类材料的光限幅实验研究
- DOI:--
- 发表时间:--
- 期刊:功能材料
- 影响因子:--
- 作者:崔浩;陈经纬;王新强;范贺良;任诠
- 通讯作者:任诠
An Efficient Algorithm to Factorize Sparse Bivariate Polynomials over the Rationals
有理数上稀疏二元多项式因式分解的有效算法
- DOI:--
- 发表时间:2012
- 期刊:ACM Communications in Computer Algebra
- 影响因子:0.1
- 作者:吴文渊;陈经纬;冯勇
- 通讯作者:冯勇
并行LLL算法研究综述
- DOI:--
- 发表时间:2019
- 期刊:计算机工程与应用
- 影响因子:--
- 作者:刘洋;陈经纬;冯勇;吴文渊
- 通讯作者:吴文渊
Incremental PSLQ with Application to Algebraic Number Reconstruction
增量 PSLQ 在代数数重构中的应用
- DOI:--
- 发表时间:2013
- 期刊:ACM Communications in Computer Algebra
- 影响因子:0.1
- 作者:冯勇;陈经纬;吴文渊
- 通讯作者:吴文渊
国际资本流动、金融发展与技术溢出效应关系研究
- DOI:--
- 发表时间:2016
- 期刊:《产经评论》(CSSCI增)
- 影响因子:--
- 作者:陈创练;张年华;陈经纬
- 通讯作者:陈经纬
其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:{{ item.doi || "--" }}
- 发表时间:{{ item.publish_year || "--"}}
- 期刊:{{ item.journal_name }}
- 影响因子:{{ item.factor || "--" }}
- 作者:{{ item.authors }}
- 通讯作者:{{ item.author }}
内容获取失败,请点击重试
查看分析示例
此项目为已结题,我已根据课题信息分析并撰写以下内容,帮您拓宽课题思路:
AI项目摘要
AI项目思路
AI技术路线图
请为本次AI项目解读的内容对您的实用性打分
非常不实用
非常实用
1
2
3
4
5
6
7
8
9
10
您认为此功能如何分析更能满足您的需求,请填写您的反馈:
相似国自然基金
{{ item.name }}
- 批准号:{{ item.ratify_no }}
- 批准年份:{{ item.approval_year }}
- 资助金额:{{ item.support_num }}
- 项目类别:{{ item.project_type }}
相似海外基金
{{
item.name }}
{{ item.translate_name }}
- 批准号:{{ item.ratify_no }}
- 财政年份:{{ item.approval_year }}
- 资助金额:{{ item.support_num }}
- 项目类别:{{ item.project_type }}