Collaborative Research: Randomized and Structure-Based Algorithms in Commutative Algebra

Illinois Institute Of Technology, Chicago IL

Investigators

Abstract

Systems of multivariate polynomial equations are ubiquitous in optimization, statistics, biology, and other fields of science and engineering. Solving such systems is a cornerstone of computational algebra today and the main focus of this project. The project addresses fundamental problems in symbolic computation with multivariate polynomials, with particular interest in very large systems that appear, for example, in biological data modeling and data mining. Such systems are so large that they cannot be completely read into the computer's memory. This project proposes the use of probabilistic and statistical analysis to cleverly select and sample smaller subsystems that lead to the desired solution. The problems attacked are fundamental questions of practical relevance. The project will also have educational and training activities in the development of human resources. In addition to many students working with the investigators, the project includes a Summer School on the foundational mathematical concepts from the areas relevant to this interdisciplinary research project. The target audience is graduate students; the School will foster a sense of community among the students and enhance further interdisciplinary collaboration. This research project approaches the problem of solving systems of polynomial equations, and of finding generators for polynomial ideals using a probabilistic method -- focusing on providing low expected runtime and the use of random choices -- for computational algebra problems that have high worst case complexity. The project uses the underlying combinatorial structure of certain families of problems (e.g. polynomial system feasibility) for significant speed-up. The resulting algorithms and software will be of use in commutative algebra, statistics, optimization, graph theory, and other fields where large-scale systems of polynomial equations arise naturally. The project adapts to the problem under study a sampling technique that has been used in computational geometry and optimization. The theoretically expected running time will be linear in the number of input polynomials. There are several applications including statistics and optimization, where key applied methods rely on algorithms to compute such ideal generators. Furthermore, the research will increase the use of combinatorial structures in polynomial computational problems, in particular, for the calculation of Nullstellensatz infeasibility certificates and syzygies. Applications have been found in graph theory, and further applications are expected in combinatorics, coding theory, and systems biology.