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

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

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.