In the paper "Fast Computation of SimRank for Static and Dynamic Information Networks", Li et al. discuss a linear-algebra computation on static and dynamic SimRank. They use the original SimRank formulation by Widom et al. with a small modification --- this allows them to use matrix operations but simrank of node with itself is no longer 1 (somewhat higher).
They use kronecker product, vectorization operator, low-rank (k) approximation, and SVD decomposition to compute four precomputed matrices of sizes k^2k^2, n^2k^2, k^2n^2, and k^21 (the middle two can be made sparse with thresholding) in O(k^4*n^2) time. Further, for each query pair the require O(k^4) time. Further, they demonstrate a procedure for updation of those matrices in the case of dynamic graphs.
Critical review: While they highlight their non-iterative simrank computation framework, decomposition of matrices is still iterative, and their algorithm also requires inversion which can be expensive as noted in their runtime and storage costs.