Effective algorithm for multiplying matrix and vector

Question

I've got two matrices $n\times n$: $A$ and $B$ and a vector $v$ and I want to find the result of: $(A^2-B)\cdot v$ and I know it can be done in $O(n^2)$ time but don't know how. Straightforward algorithm would firstly find the matrix $A^2-B$ and then multiply it by $v$ in $O(n^2)$ time, but the first action would take time $O(n^3)$ (even if smaller by some trick, it would not be $O(n^2)$). Can anybody help me come up with and algorithm that works in $O(n^2)$ time?

Answer 1

If you can compute $Av$ in $O(n^2)$ time, then finding $(A^2-B)v$ is just doing this three times, with a subtraction. Now, if you want to compute this for lots of vectors, at some point it's faster to just save the matrix $A^2-B$ for future computations. But for just one, three matrix multiplications is faster.