We consider evaluating one bilinear form defined by a (not necessarily square) sparse matrix A having h entries for w pairs of vectors. The model of computation is the semiring I/O-model with main memory size M and block size B. For a range of low densities (small h), we determine the I/O-complexity of this task for all meaningful choices of w, M, B and the dimensions, as long as M > B& sup2; (tall cache assumption). To this end, we present asymptotically optimal algorithms and matching lower bounds. Moreover, we show that this has essentially the same worst-case I/O-complexity as multiplying the matrix A with w vectors.     «

We consider evaluating one bilinear form defined by a (not necessarily square) sparse matrix A having h entries for w pairs of vectors. The model of computation is the semiring I/O-model with main memory size M and block size B. For a range of low densities (small h), we determine the I/O-complexity of this task for all meaningful choices of w, M, B and the dimensions, as long as M > B& sup2; (tall cache assumption). To this end, we present asymptotically optimal algorithms and matching lower...     »