VLSI implementation of fast solvers for band linear systems with constant coefficient matrix (Q1075016)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | VLSI implementation of fast solvers for band linear systems with constant coefficient matrix |
scientific article |
Statements
VLSI implementation of fast solvers for band linear systems with constant coefficient matrix (English)
0 references
1985
0 references
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.
0 references
discrete Fourier transform
0 references
VLSI design
0 references
linear transform
0 references
band
0 references
linear system
0 references
0 references