Daily Archives: 2010/02/20

Floyd-Warshall-Roy, 2

Posted on by

Let G = (V,E) be a weighted digraph having n vertices and let A = A_G denote its n \times n adjacency matrix. We identify the vertices with the set \{1,2,\dots, n\}. As mentioned in the previous post, the FWR algorithm is an example of dynamic programming. In the book Algebraic Statistics for Computational Biology by L. Pachter and B. Sturmfels, and the book Introduction to Tropical Geometry by D Maclagan and Sturmfels, this algorithm is described using the tropical matrix powers of A. In fact, in the latter book, the corresponding section is titled “Dynamic programming”. They formulate it “tropically” as follows.

Theorem: The entry of the matrix A\odot n-1 in row i and column j equals the length of a shortest path from vertex i to vertex j in G. (Here A\odot n-1 denotes the n-1-st tropical power of A.)

How do you compute the tropical power of a matrix? Tropical matrix arithmetic (addition and multiplication) is the obvious extension of the addition and multiplication operations on the tropical semiring. This semiring, ({\mathbb{R}} \cup \{\infty \}, \oplus, \odot), is defined with the operations as follows: x \oplus y = {\rm min}(x,y), x \odot y = x+y. The ordinary product of two n\times n matrices takes O(n^3) operations (roughly the same number of additions and multiplications). The tropical product of two n\times n matrices still takes O(n^3) operations (but only additions and comparisons, no multiplications). Of course, ordinary powers, as well as tropical powers, can be computed using the repeated squaring algorithm. This implies that the complexity of computing the N-th (tropical) power of an n \times n matrix A is O(M\log(N)), where M is the complexity of computing the (tropical) product of two n \times n matrices.

At the current time, the complexity of ordinary matrix multiplication is best estimated by either Strassen’s algorithm (for practical use) or the Coppersmith-Winograd algorithm (for theoretically best known). The CW algorithm can multiply two n \times n matrices in O(n^{2.376}) time. However, the implied “big-O” constant is so large that the algorithm is not practical. Strassen’s algorithm can multiply two n \times n matrices in O(n^{\log_2(7)+o(1)})=O(n^{2.807}) time.

Question: Do these complexity estimates extend to tropical matrix multiplication?

If so, then the complexity of computing the matrix A\odot n-1 is O(n^{2.807}), using Strassen’s algorithm. This is better than the O(n^3) estimate for the FWR algorithm mentioned in the previous post.

In fact, these observations seem so “obvious” that the fact that Sturmfels did not mention them in two different books, makes me wonder if the above question is more difficult to answer than it seems!