I'm doing some numerics (related to Gaussian processes) and need to calculate the matrix multiplication $\Sigma^{-1} \mathbf{v}\ $ as fast as possible. An implementation I am looking at finds the Cholesky decomposition of $\Sigma$ and then uses that to calculate $\Sigma^{-1} \mathbf{v}\ $ which should be $\mathcal{O} (n^3)$ (coming from the Cholesky). I wanted to know if there is a faster (but still stable) way? I know for example that matrix inversion itself can be done in less than $\mathcal{O}(n^3)$.
EDIT: Will also need to calculate $Tr(\Sigma^{-1} M)$ for a matrix $M$.