Computing the inner products of a covariance matrix I have an explicit expression for the elements of the precision matrix $Q_{k,j}$. The expression I want to compute is the inner product of the covariance matrix $\vec{v}^{\text{T}}\cdot\Pi\cdot\vec{v}$ with a known vector $\vec{v}$.
Is there a way to compute this quantity without finding the inverting the precision matrix? Thanks!
 A: In general, if we know $Q$, computing $\mathbf v^{\mathsf T}Q^{-1}\mathbf v$ is going to be a hard problem even if it does not require the inverse. ("Hard" in the sense of having the same complexity as associated problems; it's still polynomial-time.)
For example, suppose $\mathbf v = (1,0,0,0,\dots,0,0)$. Then $\mathbf v^{\mathsf T}Q^{-1}\mathbf v = (Q^{-1})_{11}$, so we're looking for one specific entry of the inverse matrix. This is $\operatorname{adj}(Q)_{11} / \det(Q)$, which is a ratio of two determinants of pretty large matrices. Moreover, the denominator of this fraction will often be $\det(Q)$ even when we simplify, so it seems clear that any method for computing this will result in a method for computing $\det(Q)$. That won't be fast.
We can avoid explicitly computing $Q^{-1}$, though, which will be faster in practice. For example, we can solve $Q\mathbf x = \mathbf v$ and then take $\mathbf v^{\mathsf T}\mathbf x$. Solving this system by Gaussian elimination still takes $O(n^3)$ time, same as finding the inverse, but the constant is better. Also, you avoid potential numerical stability issues in cases where $Q$ is close to not having an inverse.
