most recent 30 from http://mathoverflow.net 2013-05-19T05:44:47Z http://mathoverflow.net/feeds/question/73028 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73028/numerical-linear-algebra-how-to-compute-bta-1b-efficiently Jules 2011-08-17T03:18:59Z 2011-08-27T14:19:03Z

<p>What is the most efficient way to compute $b^TA^{-1}b$ for a given $A$ and $b$?</p> <p>Do we have to calculate $A^{-1}b$, or is this not necessary?</p> <p>edit: I forgot to mention that A is symmetric and positive definite and sparse (so usually you'd use the conjugate gradient method).</p> <p>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 $-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?</p>

http://mathoverflow.net/questions/73028/numerical-linear-algebra-how-to-compute-bta-1b-efficiently/73847#73847 Bart 2011-08-27T14:19:03Z 2011-08-27T14:19:03Z

<p>This is possibly an answer from a practical point of view: If you use the CG method for solving $x=A^{-1}b$ then $b^T A^{-1}b$ can be obtained along the way. However, it has been shown that computing $b^T A^{-1}b$ during the iteration can converge faster than first solving for $x$ and then multiplying $b^T x$. See "Z. Strakos and P. Tichy, On efficient numerical approximation of the bilinear form c*A-1b , SIAM Journal on Scientific Computing (SISC), 33, 2011, pp. 565-587" and the references therein for the positive definite case.</p>