A parallel algorithm for solving Toeplitz linear systems
For solving Toeplitz linear systems it is considered a cyclic reduction of the system by solving a system which contains the Toeplitz tridiagonal part and then correcting by accounting for the remaining elements in the coefficient matrix. The total number of operations for the sequential solution is given by \(6n+5\log_2n+4t\), where \(t\) is the number of components that needed to be corrected.
scientific article; zbMATH DE number 1311081