A VLSI fast solver for tridiagonal linear systems
type: Item
instance of: scholarly article
title: A VLSI fast solver for tridiagonal linear systems
zbMATH Open document ID: 0654.65026
DOI: 10.1016/0020-0190(86)90107-9
author: Bruno Codenotti
author: Grazia Lotti
published in: Information Processing Letters
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65Y05
zbMATH DE Number: 4068162
zbMATH Keywords: VLSI model
zbMATH Keywords: lower bound
zbMATH Keywords: area-time complexity
zbMATH Keywords: tridiagonal linear systems
zbMATH Keywords: odd-even reduction algorithm
MaRDI profile type: Publication
full work available at URL: 0020-0190(86)90107-9
OpenAlex ID: W2009857890
cites work: Information transfer and area-time tradeoffs for VLSI multiplication
cites work: Fast Parallel Matrix Inversion Algorithms
cites work: The complexity of a VLSI adder
cites work: Q3730020
cites work: Parallel Tridiagonal Equation Solvers
Recommended article: Q3740242
Recommended article: A fast vector algorithm for solving tridiagonal linear equations
Recommended article: Q4725754
Recommended article: A fast parallel algorithm for the solution of tridiagonal linear systems
Recommended article: Fast solvers for tridiagonal Toeplitz linear systems
Recommended article: VLSI implementation of fast solvers for band linear systems with constant coefficient matrix
Recommended article: FAST IMPLEMENTATION OF MULTIVARIABLE LINEAR SYSTEMS VIA VLSI ARRAY PROCESSORS
Recommended article: A fast algorithm for solving tridiagonal quasi-Toeplitz linear systems
Recommended article: A fast algorithm for solving special tridiagonal systems
Recommended article: Efficient VLSI implementation of iterative solutions to sparse linear systems
description: scientific article; zbMATH DE number 4068162