New answers tagged

3 votes

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))) $$ ...

Top 50 recent answers are included