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.的MATHEMICAL A和Maplesoft的Maple这样的程序已经接触到了数百万用户，他们使用这些程序来自动且没有错误地执行数学操作的机制。我们的研究广泛地影响了计算机上底层数学引擎的功能和效率。所调查的问题为新任务提供了算法，并使现有程序的执行速度显著加快，从而允许使用更大的模型进行计算，并为从实习科学家到高中生的更多用户提供数学服务器。其中几个算法立即应用于工程问题，如Stewart-Gouch平台的设计。在LinBox集团(www.linalg.org)旗下的Kaltofen正在使开发的软件免费提供。将曲线、曲面或多项式的零集分解成它们的分量的问题取决于多元多项式因式分解。当系数由于浮点截断或经验测量而不精确时，因式分解不是精确的，而必须近似输入数据。我们利用稀疏内插和稠密二元和三元近似多项式因式分解的符号/数值混合算法的最新进展来研究稀疏多维模型。我们对精确稀疏和结构化线性代数算法的研究研究了中间计算有理数的长度的控制和模2的剩余算术的使用。在多项式因式分解的主题中，我们寻找多项式时间算法和NP-难证明，以解决我们所称的超解析多项式的问题，即次数可以有数百位二进制数的多项式。我们还研究了标准因式分解问题的有效解，例如通过用一个术语替换变量来进行因式分解。最后，我们研究了不用除法计算行列式和导出结果的纯行列式公式的问题。