Preconditioning for Toeplitz-like Systems in Evolutionary Differential Equations

In this project, we develop efficient iterative methods for Toeplitz-like systems arising from solving time-dependent partial differential equations (PDEs). These PDEs arise in numerous areas in applied science and engineering, with a growing list of crucial applications such as image processing, numerical solution of convolution integral equations, queueing networks, and option pricing, just to name a few. When it comes to solving differential equations, one common numerical approach is to first discretize the equation by a mesh and then solve the corresponding linear system. One needs to further refine the mesh in order to obtain more accurate approximations.

The following two main reasons motivate the development of this proposed research project. On one hand, solving those linear systems is often computationally challenging due to their enormous size. On the other hand, in a myriad of applications, the linear systems to be inverted are frequently Toeplitz-like. Therefore, it is of high importance to develop efficient solvers which provide fast computations for these systems.

One of our main contributions is to propose novel numerical linear algebra solver for the Toeplitz-like systems and theoretically prove their rapid convergence rate. To the best of our knowledge, our proposal is the first attempt to employ the minimal residual method (MINRES) with non-circulant preconditioners for a large class of nonsymmetric ill- conditioned Toeplitz systems in order to achieve theoretically guaranteed convergence. Such an approach is in stark contrast to most existing iterative methods utilizing the generalized minimal residual method whose preconditioning based largely on heuristics.

Based on our experience with Toeplitz-like systems, we first study and identify the asymptotic eigenvalue distribution of the linear systems arising from the PDE problems of interest, including fractional differential equations. With such knowledge about eigenvalues, we construct accordingly effective preconditioners. Then, we will theoretically prove that the eigenvalues of the preconditioned matrix are clustered around ±1, which entails rapid convergence of MINRES. Preliminary results show that our designed preconditioners can lead to significant improvement in convergence, which outperform several existing circulant preconditioners. The spectra of the preconditioned matrices in the examples are observed to be clustered, which is in accordance with our proposed preconditioning theory.