I have the following quadratic form I need to evaluate:

$x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors.

Now assume that I am given for free both $A^{-1}$ and the Cholesky decomposition $A = L D L^T$. I understand that it still will be faster to evaluate $x^T A^{-1} y$ using a Cholesky decomposition, rather than directly.

Can you relate to the computational complexity (+ references) of each alternative?

  • $\begingroup$ I think that the vector y should be equal to x? $\endgroup$ – Hsien-Ming Ku Jul 24 '15 at 23:12

It depends on the matrix. If $A=\alpha I$, you need one less operation with $A^{-1}$ than with the Cholesky factor. Usually, the reason why the Cholesky factor version is faster is that it is more sparse, but this is highly dependent on the matrix. It will be difficult to get a formal result, I imagine.

| cite | improve this answer | |

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.