Speaker
Description
Rank-structured matrices are matrices with low-rank subblocks, typically off-diagonal blocks. A significant benefit of rank structures in contrast with traditional structures is that the former type is well preserved by usual matrix operations like summation, multiplication, diagonal scaling and shifting, etc. Sometimes, even factorization and inversion preserve the structures. It is well known that traditional structured matrices like Toeplitz and Cauchy-like matrices are rank structured in Fourier space. However, the original matrices themselves may not be rank structured.
We show that, in many important applications, the relevant traditional structured matrices themselves are also rank structured. Examples include Toeplitz and circulant matrices appearing in some differential equation solutions and image processing methods. Those matrices are often scaled and/or added to other matrices, which destroys the circulant/Toeplitz structures. Thus, relevant computations like linear solutions are typically done by iterative solvers. However, for some challenging situations like differential equations with sharp variations and discontinuities in coefficients, relevant condition numbers are very large, which makes them challenging for iterative solvers. Here, we show that many circulant/Toeplitz matrices also have rank structures which are preserved under usual matrix operations. This makes it feasible to design fast direct solvers for the relevant matrices. Many circulant matrices are often generated by diagonal matrices (for the eigenvalues) related to some discretized functions. We prove that, for many different types of functions, including those with discontinuities, the circulant matrices have small off-diagonal numerical ranks. Thus, this paves the path to design fast and robust direct structured solvers for relevant linear systems. The study can also be extended to show rank structures for some other problems that are previously only proven in the asymptotic sense.
