Parallel solution of toeplitzlike linear systems

AbstractThe known algorithms invert an n × n Toeplitz matrix in sequential arithmetic time O(n log2 n), but their parallel time is not better than linear in n. We present a weakly numerically stable algorithm that numerically inverts an n × n well-conditioned Toeplitz matrix A in sequential time O(n log4 n log log n) or in parallel time of O(log3 n) using O(n log n log log n) processors. The algorithm keeps all its advantages being applied to the inversion of Toeplitzlike matrices, having smaller displacement ranks (which makes it applicable to pseudo-inversion of Toeplitzlike matrices of full rank)