VLSI implementation of fast solvers for band linear systems with constant coefficient matrix
type: Item
instance of: scholarly article
title: VLSI implementation of fast solvers for band linear systems with constant coefficient matrix
zbMATH Open document ID: 0591.65025
DOI: 10.1016/0020-0190(85)90022-5
published in: Information Processing Letters
publication date: 1985-01-01T00:00:00Z
review text: Some special linear transforms of a vector by a matrix with constant entries are studied. The most significant example in this class is probably the DFT, for which several optimal VLSI designs have been obtained. The transforms considered here involve the inverses of fixed \((2k+1)\)-diagonal matrices. Such transforms solve the associated band linear systems which often arise from the discretization of boundary value problems by difference methods. The special structure of the inverses of band matrices allows detecting VLSI layouts which can be split into two parts with reciprocal low flow of information. A recursive VLSI design is derived for which time \(T=O(\log n)\) and area \(A=O(nk \log^ 3n)\) suffice to solve the problem.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 65T40
zbMATH DE Number: 3949590
zbMATH Keywords: discrete Fourier transform
zbMATH Keywords: VLSI design
zbMATH Keywords: linear transform
zbMATH Keywords: band
zbMATH Keywords: linear system
author: Bruno Codenotti
author: Francesco Romani
author: Grazia Lotti
MaRDI profile type: Publication
full work available at URL: 0020-0190(85)90022-5
OpenAlex ID: W2043007994
cites work: Marching Algorithms for Elliptic Boundary Value Problems. I: The Constant Coefficient Case
cites work: Q3675517
cites work: Inverses of banded matrices
cites work: Q5543004
cites work: The Methods of Cyclic Reduction, Fourier Analysis and the FACR Algorithm for the Discrete Solution of Poisson’s Equation on a Rectangle
Recommended article: A VLSI fast solver for tridiagonal linear systems
Recommended article: Q4725754
Recommended article: Q3740242
Recommended article: FAST IMPLEMENTATION OF MULTIVARIABLE LINEAR SYSTEMS VIA VLSI ARRAY PROCESSORS
Recommended article: Efficient VLSI implementation of iterative solutions to sparse linear systems
Recommended article: VLSI systems for band matrix multiplication
Recommended article: Fast Solvers for Systems of Linear Equations with Block-Band Matrices
Recommended article: Q3727380
Recommended article: Q4026816
Recommended article: Q3771604
description: scientific article; zbMATH DE number 3949590