Randomized Algorithms for Computational Algebra

Speaker: 

Sonja Petrovic, Associate Professor, Department of Applied Mathematics, Illinois Institute of Technology

Description: 

Many computer algebra systems offer excellent algorithms for manipulation of polynomials. But despite great success in the field, many algebraic problems have bad worst-case complexity. 

In prior work with Jesus De Loera and Despina Stasi, we imported an efficient randomized sampling algorithm from geometric optimization to computational algebra problems. The algorithm relies on computing with small-size subsystems, embedded in an iterative biased sampling scheme. In the end, the local information is used to make a global decision about the entire system. We were able to import this technology to computational algebra by using the notion of violator spaces, which give a general framework to work with LP-type problems. We showed that the theory of violator spaces applies to polynomial ideal problems. 

This talk will review the definition of a violator space including a simple example, outline the randomized algorithm, and specify the three ingredients necessary for the algorithm to work (and converge to a solution in expected linear time). We will then see how to apply the framework to one of the foundational problems related to solving systems of polynomial equations. This is also joint work with Sara Zelenberg.