Multi-Use "Plug-And-Play" Software Packages for Black Box and Inexact Symbolic Objects

用于黑匣子和不精确符号对象的多用途“即插即用”软件包

• 批准号: 9712267
• 负责人: Erich Kaltofen
• 金额: $ 21.52万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-09-15 至 2000-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9712267&HistoricalAwards=false
• 关键词: Multi; Use; Plug; Play; Software

This project conducts research in the design of efficient algorithms, their implementation in software packages, and in making the programs accessible to non-specialist users of symbolic computation systems. Packages for the black box representation of symbolic objects and for symbolic objects containing imprecise, that is, floating point data will be constructed. The packages are generically programmed as C++ template classes with abstract underlying arithmetics; they can be compiled with a variety of fast libraries for the basic field, floating point, and polynomial operations. A server/client interface seamlessly attaches the packages to all widely-used general purpose symbolic systems such as Maple and Mathetmatica. Parallel execution of the implemented algorithms will be facilitated. Black box objects are stored as functions. For instance: a black box polynomial is a procedure that takes values for the variables as input and evaluates the polynomial at that given point; a black box matrix is a procedure that takes an arbitrary vector as input and computes the matrix times vector product. The FoxBox system is a package for computing greatest common divisors and factoring black box polynomials. The aim is to eliminate algorithmic bottlenecks in FoxBox and add black box linear algebra. For sake of speed, the project focuses on algorithms over finite fields. Efficient server/client bridge code to a variety of general purpose systems will be developed. The project will also investigate how inexact (e.g., floating point) data can be handled in the course of a symbolic computation. The allowance of floating point coefficients in a symbolic, i.e., parameterized model, is crucial for a symbolic approach to problems from the physical world. Moreover, floating point arithmetic is faster than exact arithmetic, especially for algebraic numbers. Several numerical models, such as a-posteriori iterative improvement and sensitivity analysis for perturbed input data, will be considered. The problems of Toeplitz matrix rank, polynomial complex root location, and factoring complex polynomials in many variables will be investigated. The design of a plug-and-play symbolic/numeric package will be studied.

该项目研究高效算法的设计、在软件包中的实现，以及使符号计算系统的非专业用户能够访问这些程序。将构建用于符号对象的黑盒表示和包含不精确的浮点数据的符号对象的包。这些包一般被编程为带有抽象底层算术的C++模板类；它们可以使用各种用于基本域、浮点和多项式运算的快速库进行编译。服务器/客户端接口将包无缝地附加到所有广泛使用的通用符号系统，如Maple和Mathetmatica。实现的算法的并行执行将得到促进。黑盒对象存储为函数。例如：黑盒多项式是将变量的值作为输入并计算给定点处的多项式的过程；黑盒矩阵是将任意向量作为输入并计算矩阵乘以向量积的过程。FoxBox系统是一个用于计算最大公约数和分解黑盒多项式的程序包。其目的是消除FoxBox中的算法瓶颈，并添加黑盒线性代数。为了提高速度，该项目专注于有限域上的算法。将开发到各种通用系统的高效服务器/客户机桥接代码。该项目还将调查如何在符号计算过程中处理不精确(例如浮点)数据。符号模型中的浮点系数的允许，即参数化模型，对于用符号方法解决来自物理世界的问题至关重要。此外，浮点运算比精确运算速度更快，特别是对于代数数。将考虑几种数值模型，如后验迭代改进和对扰动输入数据的灵敏度分析。将研究Toeplitz矩阵的秩数、多项式复根位置以及多元复多项式的因式分解等问题。将研究即插即用符号/数字包的设计。