The Hardness of Minimum Fill-In: A Dark Secret of the Old Chinese Art (Yixin Cao)

Abstract

Gaussian elimination is a simple technique known to Chinese more than 2200 years ago. When applied to real engineering applications we’re dealing with today, however, the old technique may not work well. One particular problem is that large matrices arisen from these applications tend to be sparse, while a naive implementation of Gaussian elimination might accidentally turn too many zeroes into nonzero entries, so-called the fill-in. The problem of minimizing fill-in while performing Gaussian elimination has been studied by, among others, Klein, Lipton, Ravi, Tarjan, and Yannakakis. We’ll survey algorithms and complexity results of this problem, and present the first proof that it has no polynomial time approximation schema. We’ll also introduce other computational problems originated from large-scale sparse matrix computation, and their connection to graph problems.

This talk is based on joint work with R. B. Sandeep (IIT Hyderabad and MTA SZTAKI).

Time

Speaker

Room