Algebraic and Geometric Computation with Applications

University Of California-Davis, Davis CA

Investigators

Abstract

The goal of this project is to develop algorithms and software in both algebraic-symbolic computation and computational geometry. The algorithms will be useful in a wide variety of problems of discrete mathematics, optimization, and computer science. First, regarding algebraic computation, the PI will use ideas from commutative algebra, real algebraic geometry, large-scale linear algebra, semidefinite analysis, and combinatorics to develop very fast algorithms that can solve large, but highly-structured systems of polynomial equations that carry an extra rich combinatorial structure (e.g., they are defined from a graph and their solutions correspond to colorings or matchings, or their group of automorphisms is very large). Although solving arbitrary systems of non-linear equations is a very hard problem in general, we have been able to provide fast solutions for unusually large polynomial systems with thousands of variables. The second area of work is more related to the geometry of convex polyhedra. It is common that software in Operations Research and Optimization requires a quick way to decide when a polyhedron is integrally feasible. Relying on computational geometry analysis, convex analysis and probability, the PI intends to develop fast heuristics for detecting the existence of a lattice point inside a polyhedron as well as for counting of all its lattice points. The PI hopes to incorporate these ideas to mathematical programming software. Software and Algorithms that solve systems of equations and inequalities or that decide whether a system of equations has a solution with integer numbers are extremely useful in all areas of mathematics, engineering, and beyond. Most of the problems we will consider are directly related to problems where one wishes to find an optimal arrangement or make best decisions with scarce resources. Examples include the problem of selecting the least expensive network connecting given sites or selecting the least expensive tour for visiting a given set of locations. Since such optimization problems appear in all areas of society (data mining, finances and economics, transport scheduling and circuit design, to name a few) but are very difficult to solve, researchers have explored special structures to be able to solve them in practice (e.g., in the case of the TSP) or settle for algorithms that compute near-optimal solutions. In our project we use non-traditional tools based on recent mathematical progress as a way to approach these very difficult problems. Last, but not least, the project also has a strong educational component for this project. The PI is committed to integrate this new knowledge within curriculum development, undergraduate research projects, training of graduate students and postdocs, and the development of new open source software tools for computational optimization. Several graduate and undergraduate students will play important roles in the project's development.