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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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 ).

Improve this answer
$\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
    Commented 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
    Commented Nov 27, 2014 at 19:00
  • 1
    $\begingroup$ What do you mean when you say "no kidding!"? $\endgroup$
    – S. Carnahan ♦
    Commented 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
    Commented Nov 28, 2014 at 19:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .