So I had to answer the following question:Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, but $k$ is. In fact, we may even be interested in calculating this number modulo $n \in \mathbb{N}$.If the question had been of length exactly $k$, then the well known way is to take $A$ the adjacency matrix of $G$, and compute $A^k_{i, j}$. Since this can be done using exponentiation by squaring, we get $O(n^\omega \log n)$, where $\omega$ is the exponent of matrix multiplication.In this case, the number I'm after is $\displaystyle \left(\sum_{r = 1}^k A^r\right)_{i, j}$. If these were numbers, or we knew that $A - I$ was invertible, we could compute the equivalent expression $\displaystyle \frac{A^{k + 1} - I}{A - I}$. In general, however, we do not know this, and we cannot invert $A - I$.With that introduction, the idea of the algorithm is as follows:Using the fact that $A^1 + A^2 + ... + A^k = T + A^{\lfloor\frac{k}{2}\rfloor} \cdot T$, where $T = A^1 + A^2 + ... + A^{\lfloor\frac{k}{2}\rfloor}$, plus $A^k$ if $k$ is odd. To avoid exponentiation $A$ each time, we maintain the invariant that after calling $F(t)$, $A$ is now $A^t$. Since we make at most three multiplications, and decrease $k$ by half each time, we again make $O(n^\omega\log n)$ operations. If we are interested in this number modulo $n$, even better, since these multiplications can all be done modulo $n$.Code:A a global matrix, mutable input.T a global matrix, output.F(k):  If k == 0:    T := I.    Return.  If k == 1:    T := A.    Return.  k' := floor(k / 2).  F(k').  T := T + A * T.  A := A * A.  If k == 1 (mod 2):    A := A * A'.    T := T + A.A' := A.F(k).I feel this is a ridiculously simple algorithm, but I've failed to find any references to it. Does this technique have a name? I'm almost certain it must be well known!
An algorithm to compute the number of paths of length at most k
ds.algorithms;reference request;graph theory;linear algebra;matrices