4
$\begingroup$

Suppose $A$ is a triangular matrix. What is the most efficient known algorithm to compute the polynomial (in $x$) matrix $(xI-A)^{-1}$?

Of course, $(xI-A)^{-1}= N(x)/p_A(x)$, where $p_A$ is the characteristic polynomial of $A$, which is easy to compute once we know an eigendecomposition of $A$. But what about $N(x)$?

I am aware of the Leverrier-Fadeev algorithm, which requires $O(n^4)$ operations if $A$ is $n\times n$. Moreover, it makes use of power iteration, which can lead to numerical instability.

$\endgroup$

1 Answer 1

4
$\begingroup$

The Leverrier-Faddeev algorithm for a triangular matrix ? No kidding !

Here $N(x)=Adjoint(xI-A)$. It suffices to inverse a triangular matrix; cf. this algorithm, the complexity of which, is $\approx n^3/3$:

http://www.iaeng.org/publication/WCE2012/WCE2012_pp100-102.pdf

Yet, here, we multiply polynomials in $K[x]$ and not only elements in $K$.

EDIT 2: answer to Michele. 1. Of course, the complexity of the above cited method is $\approx n^4/3$ mult. in $K$ (using FFT for the product of polynomials).

  1. About the instability, let $A\in M_n(\mathbb{Z})$, where the $a_{i,j}$ have $k$ digits; then some coefficients of the entries of $N(x)$ have almost $kn$ digits (see $N(x)[1,n]$). You have the same problem when you calculate the gcd of $2$ polynomials over $\mathbb{Z}$. If you work with finite-precision arithmetic, then of course there is a real risk.

  2. Michele, about the complexity of L-F, you are right - I completely forgot the formula $N(x)=\sum_{i=1}^n x^{n-i}N_i$ where $N_i=AN_{i-1}+p_{i-1}I$ and $p_i=coeff(p_A(x),n-i)$. I tested this method and, indeed, it is fast and good if you work in extended precision. Otherwise you can proceed as follows (cf. point 4).

  3. Choose $n$ values $(x_i)_i$ s.t. the matrices $x_iI-A$ are well-conditioned and calculate the $((x_i-A)^{-1})_i$, that is the $(N(x_i))_i$ (a complexity in $n^4/3$ again). According to point 3., it remains to solve a linear system in the unknowns $(N_i)_i$; the essential task is to inverse a Vandermonde matrix, that can be done in $O(n^3)$ and even in $O(n^2)$ in a numerically stable way (cf. http://www.unix.eng.ua.edu/~japalmore/papers/vandermonde3.pdf ).

$\endgroup$
4
  • $\begingroup$ But a multiply in $K[x]$ costs $O(n)$, leading us again to an overall complexity of $O(n^4)$. Not to speak of numerical instability problems arising when working in $K[x]$ with finite-precision arithmetic. $\endgroup$
    – Michele
    Nov 27, 2014 at 10:05
  • $\begingroup$ concerning comment 1. You don't need to make Leverrier-Faddeev to work in $K[x]$ to recover $N(x)=adj(xI-A)$. In fact, L-F recovers $n$ (constant) matrices $N_0,...,N_{n-1}$ which are the coefficients of $N(x)$ seen as a polynomial matrix, $N(x)=N_0+N_1 x+...+N_{n-1}x^{n-1}$, and does so working in $K$ (plus, it also computes the characteristic polynomial $p_A(x)$. See e.g.jstor.org/discover/10.2307/…) So the overall complexity is still $O(n^4)$. $\endgroup$
    – Michele
    Nov 27, 2014 at 19:00
  • 1
    $\begingroup$ What do you mean when you say "no kidding!"? $\endgroup$
    – S. Carnahan
    Nov 28, 2014 at 17:39
  • $\begingroup$ In my mind "no kidding"="is it a joke ?", that is about the Michele's sentence: " where $p_A$ is the characteristic polynomial of $A$, which is easy to compute once we know an eigendecomposition of A"; that is funny when one knows that $A$ is a triangular matrix. This seems to me absolutely innocuous. Compare with "Récoltes et semailles", the book written by Grothendieck; at least, read the introduction (chapter 0). $\endgroup$
    – loup blanc
    Nov 28, 2014 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.