Take a node in a graph and consider it as a user in twitter. A link between two users is the minimum retweet time. The link represents the close connection between users. You may be interested to compute the distance among all users. Why ? To determine clusters, to find the closest nit of friends, to find relations between celebrity, or because WTF we can.

In the era of large graphs it may be interesting to compute distances among nodes. If a weighed edge represents the distance between two nodes, we could compute the all-pairs shortest path (APSP) so that to know, given any node, what is its distance from any other node in the graph. APSP and MM are computationally equivalent (**“the design and analysis of computer algorithms” **Aho, Hopcroft, and Ullman 1974. This is a great book to have anyway, I stole my advisor’s copy) and we have shown that incidentally they are the same. I will clarify in the post.

Recursive algorithms are extremely appealing for the design of matrix computation because of their natural cache locality exploitation and for their intuitive formulation. In this section, we present a recursive D&C algorithm derived from Kleene’s algorithm Figure 1.(a). Notice that Kleene’s algorithm was originally designed to solve the transitive closure (TC) of an adjacency matrix. That is, finding whether or not there is a path connecting two nodes in directed graph. However, Kleene’s algorithm is also a standard algorithm/solution for the APSP. In fact, in a closed semi-ring TC and APSP are the same problem and Kleene’s algorithm is a solution (when the scalar operators ∗ and + are specified as in the following paragraph) and it determines every edge of the (shortest) path directly [2].

A brief description of Kleene’s algorithm follows. We divide the basic problem into two sub-problems, and we solve each subproblem directly using the Floyd-Warshall algorithm, see Figure 1.(a). Then, we perform several MMs to combine the results of the subproblems using a temporary matrix; where the scalar addition of two numbers is actually the minimum of the two numbers –i.e., a + b = min(a, b)– and the scalar multiplication of two numbers is the (regular arithmetic) addition –i.e., a ∗ b = a + b.

Figure 1.(a) Figure 1.(b)

Figure 1.(c)

In this case, the MM is defined in a closed semi-ring and using the properties within, we reorganize the algorithm in Figure 1.(a) and obtain the R-Kleene algorithm in Figure 1.(b). Thus, R-Kleene is a solution for APSP in a closed semi-ring. Please, note that in literature it is suggested to use a power method using MM (log(n) times) but as you can see it is not necessary.

We can say that the ASPS can be formulated as a self-matrix multiplication. This finding is not that interesting per se: MM is highly parallel while APSP was known as really sequential making it not very compelling for large graphs.

So if you like to compute the shortest path across all nodes in a large graph, relatively dense and usign a highly parallel algorithm: R-Kleene + MM is the algorithm for you hands down.

**What is the connection with Fast MM ?**

Fast MM are in general **NOT** applicable so that to speed up the MM. This is because Fast MMs deploy cancellation operations (substractions or addition by opposite). In the APSP problem the + operation is a **min()** operation that is not invertable. Let me clarify this point: take *a+b = c* where the operation + is the arithmetic addition, then having *c*, and having either operand we can get the other: *b = c – a* or *a = c – b. *Unfortunately, *min()* does have this basic property (infact this is a semiring dang it). In the literature, there are example show to extend a few problem from the semiring to a ring and making possible to use Fast MM.

If your links are discrete numbers (integers), there are simple way to extend the problem to a ring. I will love to see how fast algorithms will do here, in this case no numerical error to bother either.

For more information, please take a look at our Algorithmica paper.