Erich Kaltofen is studying the connection of the bit cost of arithmetic on the numeric coefficients to the overall efficiency of symbolic computation algorithms. He designs and implements new algorithms for fundamental problems in exact polynomial and linear algebra and such polynomial resultants that achieve speedup through controlling the lengths of the intermediately computed rational numbers. Faster arithmetic cost is also achieved by fixed or variable precision floating point operations, and such approximate input and output data is the subject of our investigations into hybrid symbolic/numeric algorithms for polynomial factorization and structured system solving. Randomized algorithms for sparse interpolation problems are being executed as good heuristics with a limited number of coin flips in order to keep intermediate coefficients small. The algorithms in the LinBox program library for sparse, structured and black box matrices through its generic, reusable design are compiled with arithmetic that is specialized, for example, for particularly efficient finite field operations.
The overarching goal of the field of symbolic computation is doing mathematics with the aid of a 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 error-free perform the mechanics of mathematical manipulation. Thus, the users can concentrate on the interpretation of the mathematical results and, equally important, manipulate large mathematical models that are closer to reality. Kaltofen's research contributes to the infrastructure of the underlying mathematics engine on the computer. The investigated speedups make the execution significantly faster, thus allowing even better models and providing mathematics servers to even more users ranging from practicing scientists to high school students. Kaltofen under the umbrella of the LinBox group (www.linalg.org) is making the developed software freely available. Users can download and run the algorithms and experts in the discipline can scrutinize the fine points.
