Fast and Efficient Parallel Inversion of Toeplitz and Block Toeplitz Matrices
Victor Ya. Pan · Birkhäuser Basel eBooks · 1989
We call an n×n matrix A well-conditioned if log(cond A) = O(log n). We compute the inverse of any n×n well-conditioned and diagonally dominant Hermitian Toeplitz matrix A (with errors 1/2N, N = nc for a constant c) by a numerically stable algorithm using O(log2n log log n) parallel arithmetic steps and n log2n/log log n processors. This dramatically improves the previous results. We also compute the inverse and all the coefficients of the characteristic polynomial of any n×n nonsingular Toeplitz matrix A filled with integers (and possibly ill-conditioned) by a distinct algorithm using O(log2n) parallel arithmetic steps, O(n2) processors, and the precision of O(n log(∥A∥1) binary digits. The results have several modifications, extensions, and further applications.