Constructing equivalent algebraic expressions for matrix equations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T00:18:06Z http://mathoverflow.net/feeds/question/109569 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109569/constructing-equivalent-algebraic-expressions-for-matrix-equations Constructing equivalent algebraic expressions for matrix equations mks 2012-10-13T23:38:16Z 2012-10-14T09:18:26Z <p>I have an expression involving matrices, of the form:</p> <p>$$f(k)=x^T A_k^{-1}A x$$ </p> <p>where $x$ is a $1\times N$ vector, $A_k = A + k I$ and $A$ is an $N\times N$ matrix ($A_k$ is invertible for all $k$) and $k>0$. It is known that $f(k)$ is real and monotonic increasing, but nothing more. I need to further analyze the behaviour of $f(k)$ and the simplest way would be to plugin my matrices and plot it. However, this becomes computationally intensive for large $N$ as it involves calculating the inverses repeatedly. </p> <p>One thought I had was to create a one-to-one map from $f(k)$ to an equivalent algebraic expression $g(k)$, which is easy to evaluate and investigate analytically. Indeed, if the expression had involved traces of inverses, one could've used the Stieltjes transform for some insight, but that doesn't seem likely here. </p> <p>My question is: Are there general approaches/references I can look at to learn how to tackle such problems? </p> http://mathoverflow.net/questions/109569/constructing-equivalent-algebraic-expressions-for-matrix-equations/109587#109587 Answer by Dima Pasechnik for Constructing equivalent algebraic expressions for matrix equations Dima Pasechnik 2012-10-14T07:42:18Z 2012-10-14T09:18:26Z <p>Just use the usual Cramer rule for the inverse of $A+kI$. This shows that $f(k)$ is a rational function of $k$ with degrees of numerator and denominator bounded by $N$, which you can find, e.g. numerically, by Pade approximation.</p> <p>More sophisticated techniques, used in combinatorics, for tackling this kind of stuff, are called "transfer matrices". See e.g. Vol.I of R. Stanley's <a href="http://math.mit.edu/~rstan/ec/" rel="nofollow">book</a>, where in the 2nd edition, available online, it starts on p.573. </p> <p>EDIT: while numerically this might not be optimal, at least this tells you upfront what kind of function you are dealing with. And if you're only interested in the asymptotic behaviour of $f(k)$ for large $k$, then with a bit of luck you might not even need to compute the full rational form expression for $f(k)$.</p> http://mathoverflow.net/questions/109569/constructing-equivalent-algebraic-expressions-for-matrix-equations/109588#109588 Answer by Federico Poloni for Constructing equivalent algebraic expressions for matrix equations Federico Poloni 2012-10-14T07:59:50Z 2012-10-14T07:59:50Z <p>Another approach would be an improved version of what René Pannekoek suggests in a comment: compute the Schur form (not the Jordan form, which is hopelessly numerically unstable) of $A=QTQ^H$; get for free the Schur form of $A+kI=Q(T+kI)Q^H$; set $y=Q^H x$; rewrite as $f(x)=y^H(T+kI)^{-1}Ty$. This lowers your computational cost for evaluating the function in $K$ different points from $O(n^3K)$ to $O(n^3+n^2K)$ (precompute the Schur form, and do for each point one matrix product with $Q$, one with $T$, one triangular system to solve with $T+kI$).</p> <p>I did not check the details, but I assume that Dima Pasechnik's method is $O(n^4+Kn)$, since you need $O(n)$ matmuls to precompute the Padé approximation. If you combine the two ideas (first reduce to Schur form, then compute a Padé approximation of $g(y)=y^H(T+kI)^{-1}Ty$), I think that you can get $O(n^3+nK)$.</p> <p>I am afraid that the Padé part could be more numerically unstable though. Since $f(k)$ has poles in the eigenvalues of $A$, I guess that the denominator of the order-$n$ Padé approximant is the characteristic polynomial of $A$, and generally working with characteristic polynomials isn't a good idea numerically.</p>