- This event has passed.
Colloquium – Jianlin Xia (Purdue University)
September 24 @ 11:00 am - 12:00 pm
Topic: Fast Solutions of Large Linear Systems and Eigenvalue Problems by Exploring Structures
Abstract: Solving large linear systems and eigenvalue problems remains to be the key computational tasks in scientific computing, data processing, and engineering simulations. Practical numerical problems often introduce various structures into the matrix representations. In this talk, we show the existence of certain hidden rank structures in some linear systems and eigenvalue problems and discuss how to explore the structures to design efficient solvers. Such structures often arise from discretized PDEs and integral equations, and also from other computations such as Toeplitz matrices, polynomial root finding, fast multipole methods, and N-body problems. The structures enable to represent or approximate dense matrices or blocks by data-sparse forms so that it is feasible to design direct dense and sparse linear solvers in nearly O(n) complexity. The structures can also significantly accelerate the computations in eigenvalue solution methods such as QR iterations and the divide-and-conquer method. For rank-structured Hermitian matrices, it needs only about O(n) complexity to find the entire eigenvalue decomposition. Structured solvers also have other significant advantages such as enhanced numerical stability, convenient accuracy control, and natural integration with randomization strategies. In fact, we can show that the solvers often have superior stability due to reduced error propagation.