I'm interested in computing of the product $M^n v$, where $M$ is an $m\times m$ matrix (over a semiring) and $v$ is column-vector, with the smallest number of multiplications in the underlying semiring and in the regime of $n=\Theta(m)$.

If we first compute $M^n$ using fast exponentiation, this would take $\Theta(\log n)$ matrix multiplications, totaling in $\Theta(m^3\log n)$ semiring multiplications (assuming naive matrix multiplication).

On the other hand, if we just iteratively compute $M^k v$ for $k=1,2,\dots,n$, each time multiplying a vector by $M$, then it'd take us $\Theta(m^2n)$ semiring multiplications.

So, fast exponentiation appears to be useless. Is there any other way to speed up things here?

  • 1
    $\begingroup$ Is $M$ a diagonalizable matrix? Or maybe can be converted to Jordan normal form? In that case, this might help you. $\endgroup$
    – nir shahar
    Commented Jan 20, 2022 at 22:31
  • $\begingroup$ @nirshahar: Diagonalizable matrices exist over fields, in my case matrix is over a semiring, which in fact contains no invertible elements except the multiplicative identity. $\endgroup$ Commented Jan 20, 2022 at 23:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.