Usage of matrix multiplication for distance products

Question

This is more of a validation question, for the current best known results.

On one hand, we have classical matrix multiplication. Its running time is denoted as $n^\omega$.

On the other, we have distance products, where an operation similar to matrix multiplication takes place, yet its definition differs, as stated in the link.

There are obvious connections between these $2$ problems. Consider $\left({n+1}\right)^{a_{i,j}}$ for any $a_{i,j}\in A$. Now perform classical matrix multiplication. The value cannot increase over a power of $n+1$, as there are at most $n$ elements in each row/column. After having the product, consider the largest power of $n+1$ in every entry. After performing a $\log_{n+1}$ operation on that value you will receive the exact value that should have been the distance product.

Does that not mean distance products (and hence, all pairs shortest paths) can be solved in $\tilde O (n^\omega)$?

I believe my algorithm "cheats" a bit. Where exactly? I considered the maximal power of $n+1$ within each entry. I think this might require $O(n)$ time, hence making my entire algorithm not efficient enough.

I came across a paper by U.Zwick from 2000, where a $1+\varepsilon$-approximation is found in $\tilde O \left(\frac{n^\omega}{\varepsilon}\cdot\log W\right)$, where $W$ is the largest weight.

My question would therefore be:

1. Is there no efficient way to compute exact distance products by utilizing matrix multiplication? Or: what is exactly most currently known efficient way?
2. Are there other approximation ratios for distance products utilizing only matrix multiplication whose runtime is exactly $\tilde O(n^\omega)$?

Perhaps, my confusion arises from the fact that while these two problems seem to be similar, a reduction between them is not immediate.

Answer 1

Nice idea! But no, that doesn't work, alas. The problem with your approach is that the numbers become enormous, which makes matrix multiplication slow.

It is tempting to say that the running time of Strassen's algorithm is $O(n^{2.8074})$, and the running time of matrix multiplication is $O(n^\omega)$. Such a statement isn't exactly right, or at least, it has the potential to be misleading.

What is more accurate is to say that Strassen's algorithm can multiply two matrices using only $O(n^{2.8074})$ additions, subtractions, and multiplications. This does not imply that the running time is $O(n^{2.8074})$, because there is no guarantee that you can perform an addition, subtract, or multiplication in $O(1)$ time. If all numbers stay fairly small (not too large), then it is reasonable to treat the time to add, subtract, or multiple two numbers as $O(1)$. But when the numbers might get large, you can no longer ignore this this issue. The total running time will be something like $O(n^{2.8074} b^2)$ where all intermediate values fit into a $b$-bit integer (this can be reduced a bit using fast multiplication algorithms, but let's run with it for now).

This makes clear that the running time of Strassen's algorithm increases if matrix entries grow with $n$. Similar comments apply to other matrix multiplication algorithms as well.

In your approach, you need to deal with numbers that might be about as large as $(n+1)^n$. These numbers require about $b \approx n \lg n$ bits to represent. Therefore, the running time of your approach becomes something like $O(n^\omega (n \lg n)^2)$, and this is much more than $O(n^\omega)$, and in fact, is worse than $O(n^3)$.

As far as we know, computing ($\min$,$+$)-matrix products (i.e., all-pairs shortest distance computations) is harder than computing ($+$,$\times$)-matrix products (i.e., classical matrix multiplication). part of the intuition is that $+$ has an inverse ($-$), but there is no obvious analog to that for $\min$. I am not aware of any efficient reduction between them.