Suppose $u$,$v$ are vectors and $A$ is a convergent $d\times d$ diagonal + rank-1 matrix.
How do I estimate $u^T A^k v$ in $O(d)$ time?
Powers of convergent diagonal $D$ can be computed in $O(d)$ time by utilizing Laplace transform. For a general DPR1 matrix, there's $O(d^2)$ algorithm but I need something that works much faster.