Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
I would like to evaluate the chi-square of the form $\chi^2=v^{T}C^{-1}v$ where $v$ is a column vector and $C$ is a covariance matrix. Both $v$ and $C$ are known and $C$ is a $740\times740$ matrix. All quantities involved are real valued.
The straightforward fastest way I know is to compute the solution to the equation $Cx=v$ (which does not involve computing $C^{-1}$ explicitly) and then compute chi-square. Is there any algorithm that could speed up the computation of $\chi^2$?
No, as far as I know there are no shortcuts to compute a quantity of the form $v^T C^{-1} v$ that are essentially faster than $C^{-1}v$. You may save a little $O(n^2)$ effort, but this won't help against the whole algorithm which is $O(n^3)$ in practice (for small-scale, dense matrices).
If $C$ is ill-conditioned and stability is a concern, then you should probably consider using a QR factorization of the data series that has been used to compute $C$, rather than constructing $C$ itself. This is slower by a factor 2, but more stable.
And, with a matrix of that size, usually stability is a bigger concern than speed.
