Area-time tradeoffs for matrix-vector multiplication

The area-time complexity of the matrix-vector multiplication problem is studied in four models of VLSI computation. Both upper and lower bounds to different measures of area-time complexity are derived which depend on the chosen I/O conventions. We will show that the VLSI complexity of matrix-vector multiplication is dominated either by the information flow, or by the number of arithmetic operations needed to solve the problem, or by the size of data to be stored into the circuit. The problem of multipling a sparse matrix by a vector is examined as well, since it is a special case of wide interest in many applications.