A black box approach to problems in computational algebra

We give efficient algorithms for various problems in computational algebra. The most significant algorithms are those for interpolation, factorization and GCD computation of multivariate polynomials over finite fields and for algebraic set decomposition over perfect fields.; The algorithms are based on the idea of black boxes for evaluating polynomials and rational functions, introduced by Kaltofen and Trager. We formalize this idea by defining the black box representation of multivariate polynomials and rational functions and by defining black box algorithms for algebraic computations (algorithms whose input/output polynomials and rational functions are in the black box representation). We show that for many problems, the black box algorithms have to be randomized Monte-Carlo if they are to be efficient.; Efficient black box algorithms lead to efficient sparse representation algorithms if we have efficient sparse interpolation algorithms. We develop a parallel algorithm for sparse multivariate polynomial interpolation over finite fields. Our algorithm is by far the most time and processor efficient algorithm for the sparse interpolation problem when the finite field is large. Consequently, we obtain parallel sparse representation algorithms for factorization and GCD computation over finite fields. The time and processor efficiency of these algorithms improve upon that of the previously known algorithms for these problems.; We give efficient black box algorithms for a variety of algebraic computations and checking problems. Results from the theory of self-testing of polynomials are useful in designing some of the black box checking algorithms. We develop an efficient black box algorithm for the algebraic set decomposition problem over perfect fields. As a result, we also have an efficient sparse representation algorithm for the algebraic set decomposition problem over perfect fields. We demonstrate the usefulness of the black box representation by showing that considerable information can be efficiently extracted from the black box representation of an algebraic variety. This suggests a general paradigm for efficiently performing multivariate computations, that of using the black box representation and employing efficient black box algorithms.