Sivan Toledo Tel-Aviv University
The talk will focus on one class of graph algorithms in numerical linear algebra, but will mention a few more. The algorithms that are the main focus of the talk construct preconditioners (informally, approximate inverses) for accelerating the iterative solution of linear systems of equations. The algorithms that I will discuss were originally proposed by Pravin Vaidya a decade ago, but have not received much attention. These algorithms construct preconditioners by modeling the coefficient matrix as a graph and dropping edges from the graph. What is unique about them is that a graph-embedding analysis can yield provable bounds on the performance of the preconditioner, both in terms of construction and application costs, and in terms of convergence rates. I will describe numerical experiments that explore the behavior of these preconditioners in practice (none has been previously published) and compare them to other state-of-the-art preconditioners, as well as an extension of Vaidya's algorithm. Other algorithms that I will mention include: * A tree-based scheduling algorithm for out-of-core triangular factorization of sparse positive-definite matrices. * Using wide vertex separators to reduce fill in the triangular factorization of general sparse matrices. The first class of algorithms represents joint work with Doron Chen, Bruce Hendrickson, and Erik Boman, the second algorithm is joint work with Vladimir Rotkin, and the third with Igor Brainman.