User: Guest  Login
Document type:
Technical Report
Author(s):
Gero Greiner; Riko Jacob
Title:
Evaluating Non-Square Sparse Bilinear Forms on Multiple Vector Pairs in the I/O-Model
Abstract:
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...     »
Keywords:
External Memory; I/O-Model; Sparse Matrix; Lower Bounds
Year:
2010
Year / month:
2010-10-21 00:00:00
Pages:
24
 BibTeX