I thought this recent paper may be of interest https://arxiv.org/abs/2504.17033

It claims to have found a new algorithm that is faster than Dystra and is the order of O(m log^{2/3}n)

I admit the technical details went over my head, but there is an outline algorithm in the paper, but they don't link to an implemented version.