Challenges in Linear and Polynomil Algebra in Symbolic Computation Algorithms

Erich Kaltofen正在研究线性和多项式代数中符号计算问题的有效算法，这些算法可以影响几何建模、投芬图优化或密码学等应用。符号计算领域的首要目标是用计算机进行数学计算。Wolfram Research Inc.开发的Mathematica和Maplesoft开发的Maple等程序已经拥有数百万用户，他们使用这些程序自动无误地执行数学操作机制。我们的研究广泛地影响了计算机上底层数学引擎的功能和效率。所研究的问题为新任务提供了算法，并使现有程序的执行速度大大加快，从而允许使用更大的模型进行计算，并为从执业科学家到高中生的更多用户提供数学服务器。其中一些算法可以直接应用于工程问题，例如Stewart-Gouch平台的设计。在LinBox集团（www.linalg.org）的保护下，Kaltofen正在免费提供开发的软件。将曲线、曲面或零集多项式方程分解成它们的分量的问题取决于多元多项式分解。当系数由于浮点截断或经验测量而不精确时，分解不能精确，但必须近似于输入数据。我们通过使用最近在稀疏插值和密集的二元和三元近似多项式分解的混合符号/数值算法中取得的重大进展来研究稀疏多维模型。我们在精确稀疏和结构化线性代数算法中研究了中间计算有理数长度的控制和残差算术对2的幂模的使用。在多项式分解的主题中，我们寻求多项式时间算法和np -硬度证明，用于我们称之为超稀疏多项式的问题，即多项式的项度可以有数百位二进制数。我们还研究了标准分解问题的有效解决方案，例如通过替换变量项来分解。最后，我们研究了不除法计算行列式的问题，并推导出结式的纯行列式公式。

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.