Structured Matrices and Polynomials: Unified Superfast Algorithms

By Victor Y. Pan. 2001

408 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/7c9411bc50b6a33947575f37ae16931578beae23

How researchers see this paper

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

1. Tri Dao
2. Albert Gu
3. Christopher R'e
4. Beidi Chen
5. Jimmy Smith
6. Atri Rudra
7. Nimit Sharad Sohoni
8. Ankit Gupta

Citations in the corpus

• A Two-pronged Progress in Structured Dense Matrix Vector Multiplication (2018, background): “Indeed at this point connections between structured matrices and polynomials is well established [8, 43,44].”
• Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps (2020, background): “For example, the DFT is a crucial step in the standard filter bank speech preprocessing pipeline (Jurafsky & Martin, 2014), and is commonly used when dealing with time series data in general (Panaretos & Tavakoli, 2013).”
• Efficiently Modeling Long Sequences with Structured State Spaces (2021, methodology): “Computing with Cauchy matrices is an extremely well-studied problem in numerical analysis, with both fast arithmetic and numerical algorithms based on the famous Fast Multipole Method (FMM) (Pan, 2001; 2015; 2017).”
• FTRANS: energy-efficient acceleration of transformers using FPGA (2020, methodology): “Based on the circulant convolution theorem [14, 17], instead of directly performing the matrix-vector multiplication, we could use the fast Fourier transform (FFT)-based multiplication method, and it is equivalent to matrix-vector multiplication.”
• On the Parameterization and Initialization of Diagonal State Space Models (2022, background): “In fact, Vandermonde matrices are closely related to Cauchy matrices, which are the computational core of S4’s DPLR algorithm, and have identical complexity [17].”
• Survey on Deep Neural Networks in Speech and Vision Systems (2019, methodology): “using a mathematical framework of structured matrices to represent large dense matrices such as neural network parameters (weight matrices). Structured matrices, such as Toeplitz, Vandermonde, Couchy [190], essentially utilize various parameter sharing mechanisms to represent a �×� matrix with much ”
• Structured matrices and newton's iteration: unified approach (2000, background): “Alternatively, the problem can be reduced to the one with a strongly regular operator [32].”
• Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations (2019, background): “Traditional classes of structured matrices such as the Toeplitz, Hankel, Vandermonde, and Cauchy matrices are ubiquitous in engineering and signal processing [33].”
• Simplified State Space Layers for Sequence Modeling (2022, methodology): “The resulting operations are equivalent to computing Cauchy kernels [28, 29] which allow for efficient implementations of computing the convolution kernel.”
• Efficient Public Key Encryption Based on Ideal Lattices (2009, background): “Generate r ∈ ZIM 2 uniformly and de ne the Toeplitz matrix MGL ∈ Z`M×`i 2 (allowing fast multiplication [26]) whose ith row is [ri, .”
• Monarch: Expressive Structured Matrices for Efficient and Accurate Training (2022, background): “(2) In the setting of dense-to-sparse (D2S) fine-tuning of pretrained models, a long-standing problem for most classes of structured matrices is the lack of tractable algorithms to approximate dense pretrained weight matrices (Pan, 2012).”
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture (2015, methodology): “…conjecture will be important not only in proving tight hardness results for well-studied dynamic problems, but also in developing faster algorithms; for example, as mentioned earlier it can be used to show the limits of some specific approaches to attack the minimum Steiner tree and minimum cut…”
• Optimal Designs for Rational Function Regression (2010, methodology): “The bottleneck in these methods is either polynomial root-finding, which can be carried out in nearly linear time in the degree of the polynomial (Pan 2001), or the reconstruction of a measure on finite support from its canonical moments, which can also be carried out relatively easily (Dette and…”
• Structured Transforms for Small-Footprint Deep Learning (2015, background): “Fast numerical linear algebra algorithms extend to such matrices [18].”