# Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition

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?

• I think that the vector y should be equal to x? 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.