Systems of linear equations that are characterized by positive definite, diagonally dominant matrices are commonly encountered in science and engineering. In VLSI design applications, large-dimensional matrices with this property arise in simulating the behavior of on-chip power networks, in circuit placement problems, and in the solution of PDEs (e.g., for thermal analysis) using finite difference methods. There is a well-known, decades-old, analogy between the solution of these problems and running random walks on a Markov chain. However, random walk-based solvers have generally been dismissed as esoteric curiosities, and this work presents an attempt to move them to the realm of practicality. The first part of this talk develops the basic approach by adding efficient mechanisms to reuse computations for enhanced efficiency. Next, the method is studied further, and some new links to classical direct methods are uncovered. Finally, the approach is used to build a preconditioner for an iterative solver. Experimental results on real-life problems show that this method can outperform existing widely-used methods.
Sachin Sapatnekar received his BTech from IIT Bombay in 1987, his MS from Syracuse University in 1989, and his PhD from the Univ. of Illinois at Urbana-Champaign in 1992. He is currently at the Univ. of Minnesota, where he holds the Distinguished McKnight University Professorship and the Henle Professorship in the ECE dept. He has been the Editor-in-Chief of the IEEE Transactions on CAD, the General Chair for the ACM/IEEE Design Automation Conference (DAC), and the Technical Program Co-Chair for the International Symposium on VLSI Design. He is a recipient of the NSF Career Award, six conference Best Paper Awards(3 at DAC, 1 each at ICCD, ISPD, and ISQED) and a Best Poster Award (IRPS). He has received the Semiconductor Research Corporation's Technical Excellence Award (2003), the Semiconductor Industry Association University Research Award (2013), and he is a Fellow of the IEEE. He was a Senior Fulbright Scholar at the Polytechnic University of Catalonia (UPC) in Spain in 2013, and is currently a D.J. Gandhi Visiting Professor at IIT Bombay.