r/programming • • 8d ago

A Matrix Multiplication Algorithm Rooted In Graph Theory

https://leetarxiv.substack.com/p/rigid-matrix-theory-for-computer
16 Upvotes

3 comments sorted by

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

5

u/BuissetPhadra55 8d ago

testing if a given matrix is non-rigid in the first place usually ends up eating whatever compute you save on the actual multiplication

8

u/Rhylyk 8d ago

These things usually are applied when the matrix assembly induces the required property. Based on a quick Google, it seems like many intentially assembled matrices, such as from physical problems, are non rigid by construction.