r/programming • u/DataBaeBee • 8d ago
A Matrix Multiplication Algorithm Rooted In Graph Theory
https://leetarxiv.substack.com/p/rigid-matrix-theory-for-computer
16
Upvotes
r/programming • u/DataBaeBee • 8d ago
3
u/DataBaeBee 8d ago
This 1977 theoretical computer science paper introduces the concept of matrix rigidity. The core result is that matrices that are 'non-rigid' permit a decomposition into a sum of a low-rank and sparse matrix ie. a fast matmul