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

结题报告
项目介绍
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 }}
empty
内容获取失败,请点击重试
重试联系客服
title开始分析
查看分析示例
此项目为已结题,我已根据课题信息分析并撰写以下内容,帮您拓宽课题思路:

AI项目思路

AI技术路线图

相似国自然基金

{{ 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 }}
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了

AI项目解读示例

课题项目:调控A型流感病毒诱导IFN-β表达的机制研究

AI项目摘要:

本研究聚焦于TRIM2蛋白在A型流感病毒诱导的IFN-β表达中的调控机制。A型流感病毒是全球性健康问题,其感染可导致严重的呼吸道疾病。IFN-β作为关键的抗病毒因子,其表达水平对抗病毒防御至关重要。然而,TRIM2如何调控IFN-β的表达尚未明确。本研究假设TRIM2通过与病毒RNA或宿主因子相互作用,影响IFN-β的产生。我们将采用分子生物学、细胞生物学和免疫学方法,探索TRIM2与A型流感病毒诱导IFN-β表达的关系。预期结果将揭示TRIM2在抗病毒免疫反应中的作用,为开发新的抗病毒策略提供理论基础。该研究对理解宿主抗病毒机制具有重要科学意义,并可能对临床治疗流感病毒感染提供新的视角。

AI项目思路:

科学问题:TRIM2如何调控A型流感病毒诱导的IFN-β表达?
前期研究:已有研究表明TRIM2参与抗病毒反应,但其具体机制尚不明确。
研究创新点:本研究将深入探讨TRIM2在IFN-β表达中的直接作用机制。
技术路线:包括病毒学、分子生物学、细胞培养和免疫检测技术。
关键技术:TRIM2与病毒RNA的相互作用分析,IFN-β启动子活性检测。
实验模型:使用A型流感病毒感染的细胞模型进行研究。

AI技术路线图

        graph TD
          A[研究起始] --> B[文献回顾与假设提出]
          B --> C[实验设计与方法学准备]
          C --> D[A型流感病毒感染模型建立]
          D --> E[TRIM2与病毒RNA相互作用分析]
          E --> F[TRIM2对IFN-β启动子活性的影响]
          F --> G[IFN-β表达水平测定]
          G --> H[TRIM2功能丧失与获得研究]
          H --> I[数据收集与分析]
          I --> J[结果解释与科学验证]
          J --> K[研究结论与未来方向]
          K --> L[研究结束]
      
关闭
close
客服二维码