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

Split-and-invert $B$.

In some applications, $B$ is Hermitian positive definite and well-conditioned. In this case, it is recommended to compute first a sparse Cholesky decomposition

\begin{displaymath}
B=LL^{\ast},
\end{displaymath}

with $L$ a lower triangular matrix; see §10.3. The equivalent standard eigenvalue problem is
\begin{displaymath}
(L^{-1} AL^{-\ast}) \tilde{x} = \lambda \tilde{x}
\quad \m...
...tilde{y}^{\ast} (L^{-1}AL^{-\ast}) = \lambda \tilde{y}^{\ast},
\end{displaymath} (218)

where $\tilde{x} = L^{\ast} x$ and $\tilde{y} = L^{\ast} y$. As in Invert B, matrices like $L^{-1} AL^{-\ast}$ should never be evaluated explicitly, more in particular because they will in general not be sparse. For the application of an iterative method for the standard eigenvalue problem, we only need to provide the efficient evaluation of matrix-vector products, like

\begin{displaymath}
r = (L^{-1} AL^{-\ast})q
\end{displaymath}

or

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

where $q$ and $p$ are given vectors. In practice, the vector $r = (L^{-1} AL^{-\ast})q$ can be formed in three steps:

		 (a) 		 		 solve $L^{\ast} u = q$ for $u$, 

(b) form $ w = A u $,
(c) solve $L r = w $ for $r$.
The vector $s = (L^{-1} A^{\ast} L^{-\ast}) p$, when necessary, can be formed as follows:

		 (a)$^{\prime}$ solve $L^{\ast} u = p$ for $u$, 

(b)$^{\prime}$ form $ w = A^{\ast} u $,
(c)$^{\prime}$ solve $L s = w $ for $s$.
Since $L$ is a triangular matrix, the solutions of linear systems with $L$ or $L^{\ast}$ can be obtained by forward and backward substitutions. Sparsity can be exploited in a straightforward manner in all these steps.


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