Some weeks ago I was thinking about matrix multiplication and fft the complexity of polynomial multiplication using fft is $O(n\cdot \log(n))$.
The naive square matrix multiplication implementation is $O(n^3)$, maybe we can map the elements from a matrix to a polynomial (maybe multivariate) something like this:
$ \begin{bmatrix}ax&b\\cxy&dy\end{bmatrix} \begin{bmatrix}e&fz\\gx&hxz\end{bmatrix} = \begin{bmatrix}(ae+bg)x&(af+bh)xz\\(ce+dg)xy&(cf+dh)xyz\end{bmatrix} $
multiplying the polynomial:
$ (ax+b+cxy+dy)(e+fz+gx+hxz) = (aex+afxz+agx^2+ahx^2z)+(be+bfz+bgx+bhxz)+(cexy+cfxyz+cgx^2y+chx^2yz)+(dey+dfyz+dgxy+dhxyz) $
simplifying: $ (ae+gb)x+agx^2+ahx^2z+be+bfz+(af+bh)xz+(ce+dg)xy +(cf+dh)xyz+cgx^2y+chx^2y+dey+dfyz$
removing all terms except terms with $x$: $(ae+gb)x+(af+hb)xz+(ce+dg)xy+(cf+dh)xzy$
Can this be generalized for other cases? Using fft the complexity should be $O(n\cdot \log(n))$ or the tree variables increase the complexity?
Thanks for your time.