Bini D. Parallel solution of certain Toeplitz linear systems. Internal note IEI-B82-04, 1982. |

Abstract (English) |
By using the concept of approximate algorithm it is shown that 6log n + 6 parallel steps and 2n processors suffice to approximate, with any precision, the solution of a linear system with a nxn triangular Toeplitz matrix A. While 7log n + 7 steps are sufficient for an exact computation,whereas the number of processors is increased to 3nΔ2 . If A is also banded and k is its band-width the number of processors is reduced to 3n(k+l). 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 nxn matrix then the system Bx=b can be solved with no more than 9log 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,l≠0 then 13log n + O(log2≠∆k) steps and 3n(k+h) processors or 8log n + O(log∆2k) steps and max(3n(k+h),n(n+1)/2) processors are sufficient to solve the system Ax=b. Such algorithms work under the sole condition detA≠O. | |

Subject |

1) Download Document PDF |

Open access Restricted Private