MATH Seminar
| Title: Superfast and stable direct solutions of Toeplitz systems |
|---|
| Seminar: Numerical Analysis and Scientific Computing |
| Speaker: Jianlin Xia of Department of Mathematics, Purdue University |
| Contact: Jim Nagy, nagy@mathcs.emory.edu |
| Date: 2011-01-28 at 12:50PM |
| Venue: W306 |
| Download Flyer |
| Abstract: Toeplitz matrices arise in many applications such as signal and image processing, time series analysis, solution methods for PDEs, and regularization of inverse problems. In this talk, we will discuss some ideas of structured solutions of Toeplitz linear systems. These ideas can also be used to solve some other structured systems. With the displacement structure, our methods quickly solve a Cauchy-like system converted from the Toeplitz system, based on a fact that the Cauchy-like matrix is rank structured. Semiseparable structured factorizations are used to develop different versions of superfast (roughly O(n) cost) and stable Toeplitz solvers. These versions include: direct semiseparable matrix approximation, randomized sampling together with fast Toeplitz matrix-vector products, and multi-layer structured approximation. In particular, the last version uses two layers of structured representations to achieve high efficiency: an outer layer hierarchically semiseparable (HSS) structure, and an inner Cauchy-like structure for each dense HSS generator. Fast strong rank revealing LU factorizations are used in a hierarchical scheme for the structured approximation. We test the methods on various highly ill-conditioned examples to show both the efficiency and the stability. This is joint work with Ming Gu at UC Berkeley and Yuanzhe Xi at Purdue University. |
See All Seminars