Multivariate computation arises naturally in the contexts of computational algebra, computational algebraic geometry, and computational number theory. It also arises in a variety of domains including robotics, computer vision, solid modeling, automatic geometric theorem proving, and coding theory. The confluence of interest from these research areas has made it all the more important to investigate efficient methods for multivariate algebraic computation.
The works on effective Hilbert irreducibility theorem in the 1980's paved the way for designing provably efficient randomized algorithms for the fundamental problems of multivariate factorization and GCD. The theorem also laid the foundation for the novel black-box approach due to Kaltofen and Trager, as well as a related approach using straight-line programs. The geometric ideas inherent in the Hilbert irreducibility theorem and the related theory are yet to be fully exploited from an algorithmic point of view beyond their applications to multivariate factorization and GCD. The goal of this research is to utilize these ideas as the basis of efficient randomized algorithms for more general multivariate computational problems. On the one hand, effective Hilbert irreducibility will be extended as the basis of randomized reductions in a more general geometric setting. On the other hand, the black-box approach will be explored as a general paradigm for the construction of efficient algorithms for multivariate computations. The objectives are: (1) To design randomized algorithms that are substantially more efficient than the existing algorithms, and (2) To apply the results to computational number theory and computational algebraic geometry, with further application to cryptography and coding theory, and other areas as well. The investigation will initially center around a set of problems that involve multivariate polynomial systems including: solving a system of multivariate polynomials; decomposing an algebraic set defined by a system of multivariate polynomials into irreducible components; computing the degree of each component of an algebraic set; sampling random points on a component of an algebraic set; deciding if a polynomial vanishes on a algebraic set; and determining the local dimension at a point of an algebraic set. These problems provide a fertile ground for the investigation and they have many interesting applications which will also be explored in this project.
This research will likely impact the theory and practice of multivariate computations and lead to a deeper understanding of the usefulness of randomization in the context of algebraic and geometric computations.
