Challenges in Linear and Polynomil Algebra in Symbolic Computation Algorithms

符号计算算法中线性代数和多项式代数的挑战

• 批准号: 0514585
• 负责人: Erich Kaltofen
• 金额: $ 31.94万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-06-15 至 2009-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514585&HistoricalAwards=false
• 关键词: Challenges; Linear; Polynomil; Algebra; Symbolic

Erich Kaltofen is studying efficient algorithms for symbolic computation problems in linear and polynomial algebra that can impact applications such as geometric modeling, diophantine optimization, or cryptography. The overarching goal of the field of symbolic computation is performing mathematical computations by 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 without error perform the mechanics of mathematical manipulation. Our research affects broadly the functionality and efficiency of the underlying mathematics engine on the computer. The investigated problems provide algorithms for new tasks, and make the execution of existing procedures significantly faster, thus allowing computation with bigger models and providing mathematics servers to more users ranging from practicing scientists to high school students. Several of the algorithms have immediate application to engineering problems such as the design of Stewart-Gouch platforms. Kaltofen, under the umbrella of the LinBox group (www.linalg.org), is making the developed software freely available.The problem of decomposing a curve, surface or zero-set of polynomial equations into their components hinges on multivariate polynomial factorization. When the coefficients are imprecise due to floating point truncation or empirical measurement, the factorizations cannot be exact but must approximate the input data. We study sparse multidimensional models through employing the significant recent progress in hybrid symbolic/numeric algorithms for sparse interpolation and dense bi- and trivariate approximate polynomial factorization. Our research in exact sparse and structured linear algebra algorithms studies the control of the lengths of the intermediately computed rational numbers and the use of residue arithmetic modulo a power of 2. In the subject of polynomial factorization, we seek polynomial-time algorithms and NP-hardness proofs for problems on what we call supersparse polynomials, i.e., polynomials where the term degrees can have hundreds of digits as binary numbers. We also investigate efficient solutions for standard factorization problems, such as factorization by substituting a term for the variable. Finally, we study the problem of computing the determinant without a division and of deriving pure determinantal formulas for the resultant.

Erich Kaltofen正在研究线性和多项式代数中符号计算问题的有效算法，这些算法可能会影响应用程序，例如几何建模，Diophantine优化或密码学。 符号计算领域的总体目标是通过计算机执行数学计算。 Wolfram Research Inc.的Mathematica和Maplesoft的Maple等程序已经吸引了数百万用户，他们使用它们自动自动且没有错误执行数学操纵的机制。 我们的研究广泛影响计算机上基础数学引擎的功能和效率。 调查的问题为新任务提供了算法，并使现有过程的执行速度大大更快，从而允许使用更大的模型进行计算，并提供数学服务器到更多的用户，从执业科学家到高中生。几种算法可以立即应用于工程问题，例如Stewart-Gouch平台的设计。 Kaltofen在Linbox组（www.linalg.org）的伞下，正在自由使用开发的软件。将曲线，表面或零集的多项式方程式分解为其组件中的曲线，表面或零集的问题，将其组成铰链铰链铰链铰链铰链铰链铰链铰链。 当由于浮点截断或经验测量而导致系数不精确时，因素化不能确切，但必须近似输入数据。 我们通过采用稀疏的介绍杂交/数字算法的近期进展来研究稀疏的多维模型，用于稀疏的插值以及密集的双变体近似多项式分解。 我们对精确稀疏和结构化的线性代数算法的研究研究了中等计算的有理数的长度的控制，以及使用残基算术模量2的功率为2。关于我们所谓的SuperSparse多项式的问题的硬度证明，即多项式，该术语程度可以将数百个数字作为二进制数字。 我们还研究了标准分解问题的有效解决方案，例如通过将术语替换为变量来分解。 最后，我们研究了无需分裂的计算决定因素的问题，并为此得出了纯行决定剂公式。