Solving systems of symmetric Toeplitz tridiagonal equations: Rojo’s algorithm revisited

摘要

More than 20 years ago, Rojo published [1] an algorithm for solving linear systems where the matrix is tridiagonal symmetric Toeplitz and diagonal dominant. The technique proposed by Rojo is very efficient, O(n), and has been applied successfully in the solution of other similar problems: circulant tridiagonal systems, pentadiagonal Toeplitz systems, etc. In this article we extend Rojo’s algorithm to the case of non-diagonal dominant matrices, thus completing a good tool in the aforementioned applications. Other algorithms that solve the same problem are also analysed and compared with the new version of Rojo’s algorithm.