Challenges in Linear and Polynomil Algebra in Symbolic Computation Algorithms

North Carolina State University, Raleigh NC

Investigators

Abstract

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.