next up previous contents index
Next: Error Bounds for the Up: Further Details: Error Bounds Previous: Balancing and Conditioning   Contents   Index

Computing s and ${\rm sep}$

To explain s and ${\rm sep}$, we need to introduce the spectral projector P [94,76], and the separation of two matrices A and B, ${\rm sep}(A,B)$ [94,98].

We may assume the matrix A is in Schur form, because reducing it to this form does not change the values of s and ${\rm sep}$. Consider a cluster of $m \geq 1$ eigenvalues, counting multiplicities. Further assume the n-by-n matrix A is

A = \left( \begin{array}{cc} A_{11} & A_{12} \\ 0 & A_{22} \end{array} \right)
\end{displaymath} (4.1)

where the eigenvalues of the m-by-m matrix A11 are exactly those in which we are interested. In practice, if the eigenvalues on the diagonal of A are in the wrong order, routine xTREXC can be used to put the desired ones in the upper left corner as shown.

We define the spectral projector, or simply projector P belonging to the eigenvalues of A11 as

P = \left( \begin{array}{cc} I_m & R \\ 0 & 0 \end{array} \right)
\end{displaymath} (4.2)

where R satisfies the system of linear equations

A11R - RA22 = A12. (4.3)

Equation (4.3) is called a Sylvester equation. Given the Schur form (4.1), we solve equation (4.3) for R using the subroutine xTRSYL.

We can now define s for the eigenvalues of A11:

s = \frac{1}{\Vert P\Vert _2} = \frac{1}{\sqrt{1+\Vert R\Vert _2^2}}.
\end{displaymath} (4.4)

In practice we do not use this expression since |R|2 is hard to compute. Instead we use the more easily computed underestimate
\frac{1}{\sqrt{1+\Vert R\Vert _F^2}}
\end{displaymath} (4.5)

which can underestimate the true value of s by no more than a factor $\sqrt { \min ( m,n-m ) }$. This underestimation makes our error bounds more conservative. This approximation of s is called RCONDE in xGEEVX and xGEESX.

The separation ${\rm sep}(A_{11},A_{22})$ of the matrices A11 and A22 is defined as the smallest singular value of the linear map in (4.3) which takes X to A11X - XA22, i.e.,

{\rm sep}(A_{11},A_{22}) = \min_{X \neq 0} \frac{\Vert A_{11}X - XA_{22}\Vert _F}
{\Vert X \Vert _F}.
\end{displaymath} (4.6)

This formulation lets us estimate ${\rm sep}(A_{11},A_{22})$ using the condition estimator xLACON [59,62,63], which estimates the norm of a linear operator $\Vert T \Vert _1$ given the ability to compute Tx and TTx quickly for arbitrary x. In our case, multiplying an arbitrary vector by T means solving the Sylvester equation (4.3) with an arbitrary right hand side using xTRSYL, and multiplying by TT means solving the same equation with A11 replaced by A11T and A22 replaced by A22T. Solving either equation costs at most O(n3) operations, or as few as O(n2) if $m \ll n$. Since the true value of ${\rm sep}$ is |T|2 but we use |T|1, our estimate of ${\rm sep}$ may differ from the true value by as much as $\sqrt{m(n-m)}$. This approximation to ${\rm sep}$ is called RCONDV by xGEEVX and xGEESX.

Another formulation which in principle permits an exact evaluation of ${\rm sep}(A_{11},A_{22})$ is

{\rm sep}(A_{11},A_{22}) = \sigma_{\min} ( I_{n-m} \otimes A_{11} -
A_{22}^T \otimes I_m )
\end{displaymath} (4.7)

where $X \otimes Y \equiv [ x_{ij} Y]$ is the Kronecker product of X and Y. This method is generally impractical, however, because the matrix whose smallest singular value we need is m(n-m) dimensional, which can be as large as n2/4. Thus we would require as much as O( n4 ) extra workspace and O(n6) operations, much more than the estimation method of the last paragraph.

The expression ${\rm sep}(A_{11},A_{22})$ measures the ``separation'' of the spectra of A11 and A22 in the following sense. It is zero if and only if A11 and A22 have a common eigenvalue, and small if there is a small perturbation of either one that makes them have a common eigenvalue. If A11 and A22 are both Hermitian matrices, then ${\rm sep}(A_{11},A_{22})$ is just the gap, or minimum distance between an eigenvalue of A11 and an eigenvalue of A22. On the other hand, if A11 and A22 are non-Hermitian, ${\rm sep}(A_{11},A_{22})$ may be much smaller than this gap.

next up previous contents index
Next: Error Bounds for the Up: Further Details: Error Bounds Previous: Balancing and Conditioning   Contents   Index
Susan Blackford