NEWS
|
Location:Home>Seminars
Fast algorithms for computing the inverse of sparse matrices
Dr. Song Li, invited by Prof. Yongxing Shen, gave us a talk on Dec 7, 2015. Time & Date: 10:00 am, Dec 7, 2015 (Monday) Location: Conference Room, 2nd floor, JI Building Title: Fast algorithms for computing the inverse of sparse matrices
Abstract
Many problems require computing a subset of the inverse of a sparse matrix, such as least-square fitting, accuracy estimation, data clustering, electronic-structure analysis, and a variety of simulations in nanotechnology. In this talk, we focus on a specific problem arisen from the need for computing Green functions in the simulation of nanowires and nanotubes. All existing methods for this problem are either iterative methods or direct methods based on both Gaussian elimination and back substitution, except for the family of FIND (Fast Inverse using Nested Dissection) algorithm, which are direct methods solely based on repeated Gaussian eliminations, and therefore more accurate than all the other methods. The original FIND algorithm was also one order of magnitude faster than the best known algorithm at that time, and now is still optimal in the big-O sense for 2D and 3D problems. The speed and accuracy of FIND algorithms are achieved by leveraging a nested-dissection approach for LU factorization, decomposing the problem into a sequence of partial computations, and reusing the partial results that are stored earlier. These algorithms can be further improved through parallelization and the incorporation of some back-substitutions when they introduce negligible impact on accuracy. Biography Dr. Li obtained his PhD in Computational Mathematics from Stanford University in 2009. In the past he has worked at Accenture Technology Labs, Freie Universitaet Berlin, Google, Microsoft, and Yandex. Now he is working in a technology company in the US. His current research interests include the study and design of algorithms for some sparse-matrix computations, including the accuracy analysis, parallelization, and the interaction with existing libraries, etc.
|