Area-time trade-offs 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 which depend on the chosen I/O conventions are derived. We show that the VLSI complexity of matrix-vector multiplication is dominated by the information flow, 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 multiplying a sparse matrix by a vector is examined as well, since it is a special case of wide interest in many applications.