A new algorithm for solving Toeplitz linear systems

In this paper, we are interested in solving the Toeplitz linear systems.  By exploiting the special Toeplitz structure, we give a new decomposition form of the coefficient matrix.  Based on this matrix decomposition form and combined with the Sherman–Morrison formula, we propose an efficient algorithm for solving the considered problem.  A typical example is presented to illustrate the different steps of the proposed algorithm. In addition, numerical tests are given showing the efficiency of our algorithm.

Toeplitz matrix
Sherman–Morrison formula
decomposition method
  1. Bunchy J. R.  Stability of methods for solving Toeplitz systems of equations.  SIAM Journal on Scientific Computing.  6 (2), 349–364 (1985).
  2. Chesnakov A., Van Barel M.  A direct method to solve block banded block Toeplitz systems with non-banded Toeplitz block.  Journal of Computational and Applied Mathematics.  234 (5), 1485–1491 (2010).
  3. Bini D.  Parallel solution of certain Toeplitz linear systems.  SIAM Journal on Computing.  13 (2), 268–276 (1984).
  4. Lin F.-R., Ching W.-K., Ng M. K.  Fast inversion of triangular Toeplitz matrices.  Theoretical Computer Science.  315 (2–3), 511–523 (2004).
  5. Dongarra J. J., Moler C. B., Bunch J. R., Stewart G. W.  LINPACK user's guide. SIAM Press (1979).
  6. Hockney R. W.  A fast direct solution of Poisson's equation using Fourier analysis.  Journal of the ACM.  12 (1), 95–113 (1965).
  7. Widlund O. B.  On the use of fast methods for separable finite difference equations for the solution of general elliptic problems.  In: Sparse matrices and their applications, Rose D. J., Willoughby R. A. (eds)).  The IBM Research Symposia Series. Springer, Boston, MA. 121–131 (1972).
  8. Malcolm M. A., Palmer J.  A fast method for solving a class of tridiagonal linear systems.  Communications of the ACM.  17 (1), 14–17 (1974).
  9. Fischer D., Golub G., Hald O., Levia C., Widlund O.  On Fourier–Toeplitz methods for separable elliptic problems.  Mathematics of Computation.  28 (126), 349–368 (1974).
  10. Rojo O.  A new method for solving symmetric circulant tridiagonal systems of linear equations.  Computers & Mathematics with Applications.  20 (12), 61–67 (1990).
  11. Chen M.  On the solution of circulant linear systems.  SIAM Journal on Numerical Analysis.  24 (3), 668–683 (1987).
  12. Belhaj S., Dridi M., Salam A.  A fast algorithm for solving banded Toeplitz systems.  Computers & Mathematics with Application.  70 (12), 2958–2967 (2015).