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




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.


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.


友情链接: 上海交通大学 密西根学院
沪交ICP备        Copyright©2017 上海交大密西根学院沈泳星课题组 版权所有
地址:东川路800号密西根学院龙宾楼504室 邮政编码:200240 联系电话:021-34206765 ext.5041