I would like to know what is the maximum speed-up of algebraic computation when we work in the word RAM model.
This question is motivated by this theorem from Ryan's paper:
Theorem 1.2 Let $(R, +, \times)$ be a semiring on $K$ elements. For all $\epsilon ∈ (0, 1)$, every $n×n$ matrix $A$ over $R$ can be preprocessed in $O(n^{2+ε\log_2 K})$ time such that every subsequent matrix-vector multiplication can be performed in $O(n^2/(ε \log n)^2 )$ steps on a pointer machine or a $(\log n)$-word RAM, assuming operations in $R$ take constant time.
For Matrix-vector multiplication over a field there is a lower bound by Winograd of $\Omega(n^{2})$ additional gates for an arithmetic circuit, which has the matrix and vector as input. But the theorem above says that there is an algorithm in the word RAM model that, with some preprocessing time, can multiply faster by a factor of $\log^{2}n$.
Is there any other example of an algebraic computation where a speed-up of more than $\log^{2}n$ or even more than a polylogarithmic factor can be achieved?
