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.
It is not necessary to compute $A^k$ in your case. You can do a matrix-vector product with $A=D+pq^T$ in about $5d$ operations, and so multiplying with $A^k$ via $$ A^k v = A (A (A \cdots (Av))) $$ is going to cost you $5kd$ operations. The last dot product, $u^T A^k v$ is going to add $2d$ operations to that, for a total of $(5k+2)d$.
Assuming $k\ll d$, this is likely optimal. If $k\gtrsim d$, then you're already in the $O(d^2)$ case and the Laplace transform case is probably going to win.
