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 和 Mathematica。 将促进所实施的算法的并行执行。 黑盒对象存储为函数。 例如：黑盒多项式是一个将变量值作为输入并在给定点计算多项式的过程；黑盒矩阵是一个以任意向量作为输入并计算矩阵乘以向量乘积的过程。 FoxBox 系统是一个用于计算最大公约数和因式分解黑盒多项式的软件包。 目的是消除FoxBox中的算法瓶颈并添加黑盒线性代数。 为了速度，该项目重点关注有限域上的算法。 将开发针对各种通用系统的高效服务器/客户端桥接代码。 该项目还将研究如何在符号计算过程中处理不精确（例如浮点）数据。 在符号（即参数化模型）中允许浮点系数对于用符号方法解决物理世界的问题至关重要。 此外，浮点运算比精确运算更快，特别是对于代数数。 将考虑几种数值模型，例如后验迭代改进和扰动输入数据的敏感性分析。 将研究托普利茨矩阵秩、多项式复数根位置以及多变量中的复数多项式因式分解问题。 将研究即插即用符号/数字包的设计。