A VLSI fast solver for tridiagonal linear systems
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.
scientific article; zbMATH DE number 4068162
scientific article