What is the most efficient way to compute $b^TA^{-1}b$ for a given $A$ and $b$?
Do we have to calculate $A^{-1}b$, or is this not necessary?
edit: I forgot to mention that A is symmetric and positive definite and sparse (so usually you'd use the conjugate gradient method).
What I have is a convex quadratic $x^TAx + b^Tx$. The minimum of this is at $2Ax+b=0$, and if you plug this minimum into the original form, then you get $x^T(-b/2)+b^Tx=b^Tx/2$ and this leads you to have to compute $b^TA^{-1}b$. -1/4\cdot b^TA^{-1}b$. So another way to pose the question is: can you find the height at the minimum faster than the location of the minimum?
