Why You Should Care about Sparse Matrices

on YouTube ↗05m

" summary

Dense 4x4 matrices use 16 units of storage and constant‑time indexing, but graphs and nearest‑neighbor meshes scale quadratically while informative entries grow linearly, so storage and runtime must be proportional to nonzeros. Using compressed sparse row removes zeros, adds column indices, and forces log time access via binary search; element lookup may need to return a value not a reference (can't return a reference). Best sparse libraries remain Fortran/C, and the C++ standard should allow sparse row/column accessors that iterate only nonzeros.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 0:10Constant Time Access
3. 0:35Memory By Row
4. 0:45Constant Time
5. 0:55Sparse matrices
6. 1:28Practical examples
7. 1:50Key considerations
8. 2:14Squeeze out zeros
9. 2:39Compressed sparse rows
10. 3:04Efficiency
11. 3:44Conclusion

" related talks

• 19mOptimizations and abstractions for sparse machine learningCharith Mendis · Sparse 2025
• 42mDimensionality Reduction Via Sparse MatricesJelani Nelson · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 57mGraphBLAS: Building a C++ Matrix API for Graph AlgorithmsBenjamin Brock, Scott McMillan · CppCon 2021
• 40mSparse models are fast models: Improving DNN inference performance by over 10XLawrence Spracklen · Data Con LA 2021
• 15mCompiling and Compressing Structured TensorsEmilien Bauer · Sparse 2025
• 28mRandomized Constrained Matrix DecompositionsBenjamin Erichson · Randomized Numerical Linear Algebra and Applications 2018
• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 44mScalable Algorithmic Primitives for Data ScienceRichard Peng · Randomized Numerical Linear Algebra and Applications 2018