1
$\begingroup$

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$?

$\endgroup$
11
  • $\begingroup$ Do you have to perform this computation for many vectors $v$ while $C$ remains constant? $\endgroup$ Jan 24 at 16:16
  • 1
    $\begingroup$ @BrianBorchers Also one of the papers I am referencing mentions using the Sherman-Morrison-Woodbury to compute the inverse but I couldn't figure out how it would help. Anyway all suggestions are welcome. $\endgroup$
    – user7896
    Jan 24 at 16:32
  • 1
    $\begingroup$ You could compute the Cholesky factorization of C and then update it in each iteration. This would be somewhat faster than computing the Cholesky factorization in each iteration, but shouldn't be a huge improvement since the Ai's are relatively large compared to C. $\endgroup$ Jan 24 at 17:03
  • 2
    $\begingroup$ Chances are that NumPy on your system is using a very slow version of the BLAS and LAPACK linear algebra routines (quite likely the reference implementations.) You could use Intel's distribution of Python to get the advantage of MKL's fast BLAS/LAPACK- this could easily be 5 to 10 times (or even more) faster than your current version. $\endgroup$ Jan 25 at 5:04
  • 1
    $\begingroup$ MKL will probably be slightly faster than OpenBLAS, but I wouldn't expect a huge improvement. $\endgroup$ Jan 25 at 17:08

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.