Parallel Solution of Certain Toeplitz Linear Systems
Author:
- 1 May 1984
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 13 (2) , 268-276
Abstract
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} \ne 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 \ne 0$.
Keywords
This publication has 11 references indexed in Scilit:
- On the Asymptotic Complexity of Matrix MultiplicationSIAM Journal on Computing, 1982
- Partial and Total Matrix MultiplicationSIAM Journal on Computing, 1981
- On Certain Parallel Toeplitz Linear System SolversSIAM Journal on Scientific and Statistical Computing, 1981
- Approximate Solutions for the Bilinear Form Computational ProblemSIAM Journal on Computing, 1980
- Border rank of a p×q×2 tensor and the optimal approximation of a pair of bilinear forms1980
- Relations between exact and approximate bilinear algorithms. ApplicationsCalcolo, 1980
- O(n2.7799) complexity for n × n approximate matrix multiplicationInformation Processing Letters, 1979
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976
- Time and Parallel Processor Bounds for Linear Recurrence SystemsIEEE Transactions on Computers, 1975
- An Adaptation of the Fast Fourier Transform for Parallel ProcessingJournal of the ACM, 1968