Fast Bit Complexity in Symbolic Computation Algorithms

符号计算算法中的快速位复杂性

• 批准号: 0305314
• 负责人: Erich Kaltofen
• 金额: $ 31.06万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-15 至 2006-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0305314&HistoricalAwards=false
• 关键词: Fast; Bit; Complexity; Symbolic; Computation

Erich Kaltofen is studying the connection of the bit cost of arithmetic on the numeric coefficients to the overall efficiency of symbolic computation algorithms. He designs and implements new algorithms for fundamental problems in exact polynomial and linear algebra and such polynomial resultants that achieve speedup through controlling the lengths of the intermediately computed rational numbers. Faster arithmetic cost is also achieved by fixed or variable precision floating point operations, and such approximate input and output data is the subject of our investigations into hybrid symbolic/numeric algorithms for polynomial factorization and structured system solving. Randomized algorithms for sparse interpolation problems are being executed as good heuristics with a limited number of coin flips in order to keep intermediate coefficients small. The algorithms in the LinBox program library for sparse, structured and black box matrices through its generic, reusable design are compiled with arithmetic that is specialized, for example, for particularly efficient finite field operations.The overarching goal of the field of symbolic computation is doing mathematics with the aid of a computer. Programs such as Mathematica by Wolfram Research Inc. and Maple by Maplesoft have already reached millions of users, who use them to automatically and error-free perform the mechanics of mathematical manipulation. Thus, the users can concentrate on the interpretation of the mathematical results and, equally important, manipulate large mathematical models that are closer to reality. Kaltofen's research contributes to the infrastructure of the underlying mathematics engine on the computer. The investigated speedups make the execution significantly faster, thus allowing even better models and providing mathematics servers to even more users ranging from practicing scientists to high school students. Kaltofen under the umbrella of the LinBox group (www.linalg.org) is making the developed software freely available. Users can download and run the algorithms and experts in the discipline can scrutinize the fine points.

Erich Kaltofen 正在研究数值系数算术的比特成本与符号计算算法的整体效率之间的联系。他为精确多项式和线性代数以及此类多项式结果中的基本问题设计并实现了新算法，通过控制中间计算的有理数的长度来实现加速。更快的算术成本还可以通过固定或可变精度浮点运算来实现，这种近似输入和输出数据是我们研究用于多项式分解和结构化系统求解的混合符号/数值算法的主题。稀疏插值问题的随机算法正在以有限的抛硬币次数作为良好的启发式执行，以保持中间系数较小。 LinBox 程序库中的稀疏、结构化和黑盒矩阵算法通过其通用、可重用的设计，使用专门的算术进行编译，例如，用于特别高效的有限域运算。符号计算领域的首要目标是借助计算机进行数学计算。 Wolfram Research Inc. 的 Mathematica 和 Maplesoft 的 Maple 等程序已经拥有数百万用户，他们使用它们自动且无差错地执行数学运算。 因此，用户可以专注于数学结果的解释，同样重要的是，可以操纵更接近现实的大型数学模型。卡尔托芬的研究为计算机底层数学引擎的基础设施做出了贡献。研究的加速使执行速度显着加快，从而允许更好的模型，并为更多用户（从实践科学家到高中生）提供数学服务器。 LinBox 集团 (www.linalg.org) 旗下的 Kaltofen 正在免费提供开发的软件。用户可以下载并运行算法，学科专家可以仔细检查其中的细节。