VLSI implementation of fast solvers for band linear systems with constant coefficient matrix (Q1075016)

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.