Parallel Solution of Certain Toeplitz Linear Systems
Dario A. Bini · SIAM Journal on Computing · 1984
Using the concept of approximate algorithm it is shown that $6\log n + 6$ parallel steps and $2n$ processors suffice to approximate, with any precision, the solution of a linear system with an $n \times n$ triangular Toeplitz matrix A. Moreover, $7\log n + 7$ steps are sufficient for an exact computation, whereas the number of processors is increased to $( \frac{5}{2} )n^2 $. If A is also banded and k is its bandwidth, the number of processors is reduced to $( \frac{5}{2} )n(k + 1)$. Two applications are shown. It is proved that if B is any matrix belonging to the algebra generated over the complex field by a given $n \times n$ matrix, then the system $Bx = b$ can be solved with no more than $9\log n + 4$ steps with $O(n^2 )$ processors. It is proved that, given a Toeplitz matrix $A = (a_{i,j} )$ such that $a_{i,j} = 0$ if $i - j > k$ or $j - i > h$, $a_{k,1} e 0$, then $13\log n + O(\log ^2 k)$ steps and $\max ( (\frac{5}{2} )n(k + h), n(n + 1)/ 2 )$ processors are sufficient to solve the system $Ax = b$. Such algorithms work under the sole condition $\det A e 0$.