Scientific applications of iterative Toeplitz solvers

Abstract

Recent research on using the preconditioned conjugate gradient method as an iterative method for solving Toeplitz systems has brought much attention. One of the main important results of this methodology is that the complexity of solving a large class of Toeplitz systems can be reduced to O(nlogn) operations as compared to the O(nlog 2 n) operations required by fast direct Toeplitz solvers, provided that a suitable preconditioner is chosen under certain conditions on the Toeplitz operator. In this paper, we survey some applications of iterative Toeplitz solvers to Toeplitz-related problems arising from scientific applications. These applications include partial differential equations, queueing networks, signal and image processing, integral equations, and time series analysis.