News for hackers. Stuff that matters.
Re:NP-hard does not mean hard (2017) by adalacelove on Thursday August 17, 2023 @01:56AM (#37157781)
Staying in the realm of polynomial complexity matrix multiplication comes to mind, where we are approaching more and more O(n^2), where O(n^3) is the naive, but more common implementation.
Re:NP-hard does not mean hard (2017) by shenberg on Thursday August 17, 2023 @04:23AM (#37158711)
In terms of practical algorithms, the Strassen algorithm (O(n^2.8)) is the only one that has runtime advantages for matrix sizes that aren't enormous, and even then, it's not always used because it has two non-trivial costs: reduced numerical stability and more memory space requirements for intermediate results.
Re:NP-hard does not mean hard (2017) by adgjlsfhk1 on Thursday August 17, 2023 @12:11PM (#37163915)
It actually doesn't require more memory for intermediate results (see the Strassen reloaded paper). It's more just that it's a ton of work to implement well (even compared to a regular gemm which is already hard), and the benefits only start showing up at pretty large (~4000x4000) matrices.