A Parallel Algorithm For Toeplitz Triangular Matrices
Ming-kui Chen 1, Hao Lu 11 Department of Mathematics, Xi'an Jiaotong University, Xi'an, China
Received 1987-4-2 Revised Online 2006-12-8
A new parallel algorithm for inverting Toeplitz triangular matrices as well as solving Toeplitz triangular linear systems is presented in this paper. The algorithm possesses very good parallelism, which can easily be adjusted to match the natural hardware parallelism of the computer systems, that was assumed to be much smallar than the order n of the matrices to be considered since this is the usual case in practical applications. The parallel time complexity of the algorithm is $O([n/p|\log n+\log^2p)$, where p is the hardware parallelism.