A VLSI fast solver for tridiagonal linear systems (Q1108739)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A VLSI fast solver for tridiagonal linear systems |
scientific article |
Statements
A VLSI fast solver for tridiagonal linear systems (English)
0 references
1986
0 references
The area-time complexity of a VLSI solver for tridiagonal linear systems is studied. Both a lower and an upper bound are derived which meet to within the exponent of the logarithmic factor. The proposed VLSI design derives from the parallel version of the well-known odd-even reduction algorithm for tridiagonal linear systems, which requires O(log n) parallel steps. The algorithm is optimal with respect to the parallel complexity.
0 references
VLSI model
0 references
lower bound
0 references
area-time complexity
0 references
tridiagonal linear systems
0 references
odd-even reduction algorithm
0 references
