8
$\begingroup$

Morris Marden's "Geometry of Polynomials" displays a number of formulae that allow one to estimate bounds on the largest root of a polynomial that do not involve actual rootfinding. Having been inspired by this, and since this particular problem crops up in one of the things I'm working on, I was wondering if one could get good estimates of the spectral radius of a general dense n-by-n matrix A that has been previously processed as follows:

  1. a similarity transformation to upper Hessenberg form ($A=QHQ^T$, $Q$ orthogonal and $H$ upper Hessenberg); and
  2. subtracting the identity multiplied by the mean of the eigenvalues from $H$ ($H'=H-\frac{trace(H)}{n}I$, this corresponds geometrically to centering the eigenvalues around the origin of the complex plane).

As much as possible, I am trying to avoid having to resort to an eigenvalue method (e.g. QR (too much effort!), power method (the power method can misbehave when there is more than one eigenvalue whose modulus is equal to the spectral radius)) since I only need a quick 2-3 digit approximation of the spectral radius. I have considered actually expanding $H'$ to its characteristic polynomial (equivalently, a similarity transformation of $H'$ to a Frobenius companion matrix) so that the formulae listed in Marden can apply, but after reading Wilkinson's wonderful book "The Algebraic Eigenvalue Problem" where he details how unstable the computation of coefficients of the characteristic polynomial can get from a matrix, I suppose that idea is shot.

My other naïve attempts at estimating the spectral radius include using $||H'||_\infty$ as an estimate, and deriving rough bounds using Gerschgorin's theorem; the problem I've seen is that both attempts tend to overestimate the spectral radius by a significant factor.

Is there a way to estimate the spectral radius more cheaply and noniteratively than actually computing eigenvalues?

Improve this question
$\endgroup$
9
  • 4
    $\begingroup$ I would guess no. The matrix $A = \begin{pmatrix} 0 & N \\ 0 & 0 \end{pmatrix}$ has spectral radius $0$, whereas the matrix $B = \begin{pmatrix} 0 & N \\ \frac{1}{\sqrt{N}} & 0 \end{pmatrix}$ has spectral radius $\sqrt{N}$. So in order to compute the spectral radius you need to look at all entries, and not ignore small ones. $\endgroup$
    – Helge
    Commented Aug 13, 2010 at 9:19
  • $\begingroup$ Well I am certainly not expecting an O(n) algorithm for this to exist! ;) As I had already mentioned, all the matrices I will be dealing with have already undergone a preliminary reduction to upper Hessenberg form, and I suppose the problem eases slightly if the Hessenberg matrix is reducible (in that I can consider diagonal blocks separately). $\endgroup$
    – J. M. isn't a mathematician
    Commented Aug 13, 2010 at 9:27
  • $\begingroup$ So you want something between better than O(n^3), I guess. The example above shows that one at least needs O(n^2). I guess the method based on Gerschgorin's theorem is a O(n^2) algorithm ... $\endgroup$
    – Helge
    Commented Aug 13, 2010 at 12:41
  • 1
    $\begingroup$ Then compute $B = A^* A$, which is O(n^3) many operations, and then compute the largest eigenvalue of $B$, should work. $\endgroup$
    – Helge
    Commented Aug 13, 2010 at 17:36
  • 1
    $\begingroup$ Er... A* is the conjugate transpose here, right? So this is a prescription to find the largest singular value (a.k.a. the 2-norm) of A. I need the modulus of the largest eigenvalue of A, and that's not the same thing unless A is symmetric (which on the other hand does succumb to a Gerschgorin-based algorithm (since all eigenvalues of a symmetric matrix are real ;) ), as I have found). Symmetric matrices really are so much nicer! $\endgroup$
    – J. M. isn't a mathematician
    Commented Aug 13, 2010 at 23:25

2 Answers 2

Reset to default
2
$\begingroup$

Why are you trying to avoid eigenvalue calculations in the first place? I think Arnoldi methods (such as Arpack, used e.g. in Matlab's eigs) would do a respectable job, and maybe even the power method itself --- when there are multiple eigenvalues with about the same modulus, convergence to the eigenvectors is problematic, but the growth factor should be a reliable approximation of the spectral radius nevertheless.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Well I certainly don't need to get all the eigenvalues (as a QR algorithm implementation is wont to do) just for the sole purpose of estimating the spectral radius! I just need a good estimate computable from the entries of the Hessenberg matrix (I am working with dense matrices here; Arnoldi/Lanczos-type methods as I understand are better suited for the sparse case). With the power method, I had mentioned how troublesome convergence can get for matrices with equimodular dominant eigenvalues. If quick estimates of the largest root can be done for polynomials, why not for the spectral radius? $\endgroup$
    – J. M. isn't a mathematician
    Commented Aug 13, 2010 at 15:07
1
$\begingroup$

This is more a comment than an answer, but I do not have the reputation for it. As far as I know, the numarical range (and the quadratic numerical range) is quite often used to give estimates on the location of the eigenvalues. I suppose thay can also be used to estimate the spectral radius. See Gustafson/Rao: Numerical range, Springer, and the literature mentioned in it. Unfortunately, I am not an expert in this field...

Improve this answer
$\endgroup$

You must log in to answer this question.

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