A Two-pronged Progress in Structured Dense Matrix Vector Multiplication

By Christopher De Sa, Albert Gu, Rohan Puttagunta, Christopher R'e, Atri Rudra. 2018

31 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Hardware and Architecture, Information Systems, Efficiency & Compression, Numerical Methods & Scientific Computing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Hardware and Architecture

In Information Systems

In Efficiency & Compression

In Numerical Methods & Scientific Computing

Citations in the corpus

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022, methodology): “The butterﬂy pattern we use for our block-sparse attention is motivated by the fact that butterﬂy matrices [16, 67] and their products have been shown to be able to express any structured matrices with almost optimal runtime and number of parameters [17, 21].”
HiPPO: Recurrent Memory with Optimal Polynomial Projections (2020, background): “(6)It is known that large families of structured matrices related to orthogonal polynomials are efficient [22].”
Monarch: Expressive Structured Matrices for Efficient and Accurate Training (2022, background): “[16] show that all structured matrices (in the form of arithmetic circuits) can be written as products of sparse matrices, which can be represented as products of butterfly matrices [13].”
Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps (2020, methodology): “In parallel, recent theoretical results by De Sa et al. (2018) show that sparsity and the notion of structure in linear maps are fundamentally linked: any given matrix can be factored into a product of sparse matrices with total parameter count equal to the efﬁciency (i.e. minimum arithmetic…”
Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models (2021, background): “…sparse + low-rank matrices, which can capture global and local information [Candès et al., 2011, Udell and Townsend, 2019, Chen et al., 2021], and (ii) butterfly matrices [Parker, 1995, Dao et al., 2019] whose products can tightly represent any sparse matrix [De Sa et al., 2018, Dao et al., 2020].”
Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations (2019, background): “Both orthogonal polynomial transforms [12], and all of the previously introduced matrices with displacement rank structure, were signiﬁcantly generalized under a single class by De Sa et al. [8].”
Separable Layers Enable Structured Efficient Linear Substitutions (2019, background): “Circulant transforms and SELLs were later unified under low displacement rank (LDR) transformations (Zhao et al., 2017; De Sa et al., 2018).”
Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers (2021, background): “[17] Christopher De Sa, Albert Gu, Rohan Puttagunta, Christopher Ré, and Atri Rudra.”
Scatterbrain: Unifying Sparse and Low-rank Attention Approximation (2021, background): “De Sa et al. [24] shows that any structured matrix can be written as product of sparse matrices, and products of sparse matrices even with ﬁxed sparsity pattern have been shown to be eﬀective at parameterizing compressed models [1, 20, 21].”
Sparse Recovery for Orthogonal Polynomial Transforms (2019, background): “More directly, Thomas et al. [37] apply parametrized families of structured matrices directly inspired by orthogonal polynomial transforms (De Sa et al. [14]) as layers in neural networks.”