4 added 10 characters in body

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? 3 added 315 characters in body; added 37 characters in body 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$. So another way to pose the question is: can you find the height at the minimum faster than the location of the minimum? 2 added 125 characters in body; added 11 characters in body 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).

1