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正在研究线性和多项式代数中符号计算问题的有效算法，这些问题可能会影响几何建模，丢番图优化或密码学等应用程序。 符号计算领域的首要目标是通过计算机进行数学计算。 Wolfram Research Inc.的Mathematica等程序。和Maple的Maplesoft，已经达到了数百万用户，谁使用它们来自动和没有错误地执行数学运算的机制。 我们的研究广泛地影响了计算机上底层数学引擎的功能和效率。 所研究的问题提供了新任务的算法，并使现有程序的执行速度显着加快，从而允许更大的模型计算，并提供数学服务器给更多的用户，从实践科学家到高中生。有几个算法直接应用于工程问题，如斯图尔特-古奇平台的设计。Kaltofen在LinBox集团（www.linalg.org）的保护下，正在免费提供开发的软件。将曲线、曲面或多项式方程的零集分解为它们的分量的问题取决于多元多项式因式分解。 当系数由于浮点截断或经验测量而不精确时，因子分解不能精确，但必须近似输入数据。 我们研究稀疏多维模型，通过采用稀疏插值和密集的二元和三元近似多项式因式分解的混合符号/数值算法的显着最新进展。 我们在精确稀疏和结构化线性代数算法的研究研究控制的长度的中间计算的有理数和使用剩余算术模2的幂。 在多项式因式分解的主题中，我们寻求多项式时间算法和NP-困难证明，用于我们称之为超解析多项式的问题，即，多项式，其中术语度可以具有数百位作为二进制数。 我们还研究了标准因式分解问题的有效解决方案，例如用一个项代替变量的因式分解。 最后，我们研究的问题，计算行列式没有一个部门和推导纯行列式公式的结果。