Timing analysis of a parallel algorithm for Toeplitz matrices on a MIMD parallel machine (Q1179257)

The authors present and implement a Levinson-type algorithm for solving Toeplitz systems on a shared bus and a shared memory parallel MIMD machine. They observed that the speedup depends on the matrix size. For a large matrix the efficiency is over \(75\%\). Processing time of the algorithm for a fixed size Toeplitz matrix decreases when the number of processors increases, up to an optimal number of processors due to the limitation of the communication through the shared bus.