Tag Info

Powers of convergent DPR1 matrices in $O(d)$ time?
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)))$$ ...