next up previous contents index
Next: Split-and-invert . Up: Transformation to Standard Problems Previous: Transformation to Standard Problems   Contents   Index

Invert $B$.

If $B$ is nonsingular, then the problem (8.1) is equivalent to
\begin{displaymath}
(B^{-1}A) x = \lambda x \quad \mbox{and} \quad
\tilde{y}^{\ast} (B^{-1} A) = \lambda \tilde{y}^{\ast},
\end{displaymath} (216)

where $\tilde{y} = B^{\ast} y$. Alternatively, the problem (8.1) is also equivalent to
\begin{displaymath}
(AB^{-1})\tilde{x} = \lambda \tilde{x} \quad \mbox{and} \quad
y^{\ast} (AB^{-1}) = \lambda y^{\ast},
\end{displaymath} (217)

where $\tilde{x} = B x$. If the right eigenvectors are of primary interest, then (8.3) is preferable, since it avoids an additional back transformation.

For an iterative method, as described in Chapter 7, for the reduced standard eigenvalue problem (8.3) or (8.4), it is not necessary to evaluate the product $B^{-1}A$ or $AB^{-1}$. This is a key observation in the treatment of large sparse $A$ and $B$. One only needs to evaluate matrix-vector products, like

\begin{displaymath}
r = (B^{-1}A) q,
\end{displaymath}

for a given vector $q$. For a two-sided Lanczos-type method, the vector

\begin{displaymath}
s = (B^{-1}A)^{\ast}p
\end{displaymath}

is also necessary for given vector $p$. Note that the vector $r = (B^{-1}A) q$ can be computed in two steps:

		 (a) 		 		 form $u = A q$, 

(b) solve $B r = u$ for $r$.
Similarly, the vector $s = (B^{-1}A)^{\ast}p$, if necessary, can be evaluated as

		 (a)$^{\prime}$ solve $B^{\ast} v = p$ for $v$,  

(b)$^{\prime}$ form $s = A^{\ast} v$.
One can exploit sparsity in each of these steps. In general, the iterative methods, with the exception of the Jacobi-Davidson method, require accurate solution of the linear systems at step (b) (and (b)$^{\prime}$). If possible, a direct linear system solver, say, using LU factorization of $B$, is preferable. See §10.3 for the discussions on dense or sparse LU factorization.

The error introduced by this transformation to standard form can be proportional to $\Vert A\Vert _2 \Vert B^{-1}\Vert _2$. If $B$ is ill-conditioned, then the approach is potentially suspect. In that situation, one may consider the SI for the transformation or the usage of the Jacobi-Davidson method discussed below.


next up previous contents index
Next: Split-and-invert . Up: Transformation to Standard Problems Previous: Transformation to Standard Problems   Contents   Index
Susan Blackford 2000-11-20