Use of Interval Arithmetic in Symbolic Computation

区间运算在符号计算中的应用

• 批准号: 9211016
• 负责人: Jeremy Johnson
• 金额: $ 4.41万
• 依托单位: Drexel University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-07-01 至 1994-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9211016&HistoricalAwards=false
• 关键词: Use; Interval; Arithmetic; Symbolic; Computation

This project explores the use of interval arithmetic in symbolic computation. Interval arithmetic provides an efficient and error free method of combining floating point arithmetic with exact computation. The primary goal of this project is to develop and analyze hybrid interval/symbolic algorithms that provide a practical efficiency gain to time consuming algebraic algorithms such as Collins' Cylindrical Algebraic Decomposition based Quantifier Elimination. Reduced execution times will allow more complicated and interesting problems to be solved. Example hybrid algorithms include Lehmer's multiprecision integer GCD algorithm, real algebraic number sign computation, algebraic number inequality tests, polynomial root bound computation, polynomial real root isolation, and potentially approximate algebraic polynomial GCD calcuation. Preliminary study of some of these algorithms show the potential merits of this approach. An interval arithmetic package will be implemented for the SAC2-C computer algebra library. Using this package all algorithms will be implemented and carefully analyzed empirically and theoretically. The empirical study will be used to investigate the performance gain achieveable through the use of the proposed methods. Furthermore, empirical results will provide useful information on the effectiveness and limitations of interval methods in exact compuation. Programs with detailed documentation and analysis will be made available to the research community.

本专题探讨区间算术在符号运算中的应用。 计算 区间算术提供了一个有效的和错误的 浮点运算与精确运算相结合的自由方法 计算 该项目的主要目标是开发和 分析混合区间/符号算法，提供了一个实用的 效率增益耗时代数算法，如 基于柯林斯圆柱代数分解的量词 淘汰 减少执行时间将允许更复杂和 有趣的问题要解决。 示例混合算法包括Lehmer的多精度整数GCD 算法，真实的代数数符号计算，代数数 不等式检验，多项式根界计算，多项式真实的 根隔离和潜在的近似代数多项式GCD 计算 对其中一些算法的初步研究表明， 这种方法的潜在优点。 将为SAC 2-C实施一个区间算术包 计算机代数图书馆 使用此软件包，所有算法都将 实施和仔细分析的经验和理论。 的 实证研究将被用来调查的性能增益 可通过使用所提出的方法来实现。 此外，委员会认为， 实证结果将提供有用的信息的有效性 以及区间方法在精确计算中的局限性。 程序 详细的文件和分析将提供给 研究社区。