Given a matrix-vector product $Ar$, where $A$ is a $d \times d$ real symmetric matrix and $r$ is a $d$ dimensional real vector.
Is there a way of calculating $A^2 r$ in $O(d)$ time given that the eigenvalues of $A$ are precomputed ?
i.e Let $A = U \Sigma U^T$, we have $Ar$ and $\Sigma$ with us and we need to calculate $A^2 r$ in $O(d)$ time.
Given $v=Ar$, I don't see how you can possibly compute $Av$ without reading all of the entries of $A$, which already requires $O(d^2)$ time. Note that the knowledge that $v$ is in the column space of $A$ doesn't really help you in the general case where $A$ is nonsingular.
Even if you know $\Sigma$, there are still $\dim SO(d) \in O(d^2)$ possible sets of eigenvectors of $A$ and you'll need to read them all in to compute $Av$.
To get $O(d)$ behavior you'd need, for example, to already know the expansion of $r$ in $A$'s eigenbasis; or for $A$ to be sparse.