General sparse matrix–matrix multiplication (SpGEMM) is a fundamental building block for
numerous applications such as algebraic multigrid method (AMG), breadth first search and …

We propose a fine-grained hypergraph model for sparse matrix-matrix multiplication
(SpGEMM), a key computational kernel in scientific computing and data analysis whose …

We consider the well-known problem of enumerating all triangles of an undirected graph.
Our focus is on determining the input/output (I/O) complexity of this problem. Let E be the …

This paper studies how to use fast matrix multiplication to speed up query processing. As
observed, computing a two-table join and then projecting away the join attribute is …

The performance of parallel algorithms for sparse matrix-matrix multiplication is typically
determined by the amount of interprocessor communication performed, which in turn …

Sparse basic linear algebra subprograms (BLAS) are fundamental building blocks for
numerous scientific computations and graph applications. Compared with Dense BLAS …

AMG is one of the most efficient and widely used methods for solving sparse linear systems.
The computational process of AMG mainly consists of a series of iterative calculations of …

Abstract A tight\varOmega ((n/M)^\log _2 7 M) lower bound is derived on the I/O complexity
of Strassen's algorithm to multiply two n * n matrices, in a two-level storage hierarchy with M …

This paper initiates the study of I/O algorithms (minimizing cache misses) from the
perspective of fine-grained complexity (conditional polynomial lower bounds). Specifically …

Self-attention is at the heart of the popular Transformer architecture, yet suffers from
quadratic time and memory complexity. The breakthrough FlashAttention algorithm revealed …