更新时间：
告人：夏建林副教授
美国普渡大学
报告题目: Superfast and stable algorithms for challenging numerical computations: sparse inversion and divide-and-conquer
报告时间：2013年12月11日下午15:30
报告地点：海韵实验楼108
报告摘要：In recent years, the significance of fast structured methods has been widely studied, primarily for direct solutions of large dense and sparse linear systems and special eigenvalue problems. For example, it is possible to solve certain Ax=b with one vector b or to find one eigenvalue of certain A in O(n) flops.
In this talk, we show superfast algorithms for more challenging problems. One is to find all the diagonal entries or even any n entries of A^{-1} for certain sparse A in O(n) flops. This is very useful in electronic structure computations. Recent developments cost O(n^{1.5}) in 2D and O(n^2) in 3D instead. Another problem is to find all the n eigenvalues of A in O(n) flops stably. Recent developments based on structured methods cost O(n^2), and are only for special cases such as companion matrices. Our new method is based on the divide-and-conquer idea, and can work for more general cases such as symmetric Toeplitz and HSS matrices.
For these problems, we prove the underlying structures and justify why superfast direct solutions are feasible. Also, we show how the accuracy is controlled by structured compression. The methods are not only faster, but also have significantly better backward stability than classic computations. Related stability bounds and growth factors are given.