1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<!--Converted with LaTeX2HTML 96.1-h (September 30, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->
<HTML>
<HEAD>
<TITLE>Eigenvalues, Eigenvectors, and Schur Factorization</TITLE>
<META NAME="description" CONTENT="Eigenvalues, Eigenvectors, and Schur Factorization">
<META NAME="keywords" CONTENT="slug">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<LINK REL=STYLESHEET HREF="slug.css">
</HEAD>
<BODY LANG="EN" >
<A NAME="tex2html2940" HREF="node64.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html2938" HREF="node62.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html2934" HREF="node62.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html2942" HREF="node1.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="http://www.netlib.org/utk/icons/contents_motif.gif"></A> <A NAME="tex2html2943" HREF="node190.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="http://www.netlib.org/utk/icons/index_motif.gif"></A> <BR>
<B> Next:</B> <A NAME="tex2html2941" HREF="node64.html">Singular Value Decomposition</A>
<B>Up:</B> <A NAME="tex2html2939" HREF="node62.html">Nonsymmetric Eigenproblems</A>
<B> Previous:</B> <A NAME="tex2html2935" HREF="node62.html">Nonsymmetric Eigenproblems</A>
<BR> <P>
<H3><A NAME="SECTION04335100000000000000">Eigenvalues, Eigenvectors, and Schur Factorization</A></H3>
<P>
<A NAME="1982"> </A>
Let <I>A</I> be a square <I>n</I>-by-<I>n</I> matrix. A scalar <IMG WIDTH=8 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline12778" SRC="img69.gif"> is called
an <B>eigenvalue</B><A NAME="1984"> </A> and a nonzero column vector <I>v</I> the corresponding
<B>right eigenvector</B><A NAME="1986"> </A> if <IMG WIDTH=63 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline13982" SRC="img186.gif">. A nonzero column vector <I>u</I>
satisfying <IMG WIDTH=91 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline13986" SRC="img187.gif">
is called the <B>left eigenvector</B><A NAME="1988"> </A>.
The first basic task
of the routines described in this section
is to compute, for a given matrix <I>A</I>, all <I>n</I> values of <IMG WIDTH=8 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline12778" SRC="img69.gif"> and,
if desired, their associated right eigenvectors <I>v</I> and/or
left eigenvectors <I>u</I>.
<P>
A second basic task is to compute the <B>Schur factorization</B> of a matrix <I>A</I>.
<A NAME="1990"> </A>
If <I>A</I> is complex, then its Schur factorization is <IMG WIDTH=87 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline14002" SRC="img188.gif">, where
<I>Z</I> is unitary and <I>T</I> is upper triangular. If <I>A</I> is real, its
Schur factorization is <IMG WIDTH=85 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline14010" SRC="img189.gif">, where <I>Z</I> is orthogonal,
and <I>T</I> is upper quasi-triangular (1-by-1 and 2-by-2 blocks on
its diagonal).
The columns of <I>Z</I> are called the <B>Schur vectors </B> of <I>A</I>.
<A NAME="1992"> </A>
The eigenvalues of <I>A</I> appear on the diagonal of <I>T</I>; complex conjugate
eigenvalues of a real <I>A</I> correspond to 2-by-2 blocks on the diagonal
of <I>T</I>.
<P>
These two basic tasks can be performed in the following stages:
<P>
<OL>
<LI> A general matrix <I>A</I> is reduced to <B>upper Hessenberg form</B><A NAME="1995"> </A> <I>H</I>
<A NAME="1996"> </A>
<A NAME="1997"> </A>
which is zero below the first subdiagonal. The reduction may be written
<IMG WIDTH=89 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline14044" SRC="img190.gif"> with <I>Q</I> orthogonal if <I>A</I> is real, or
<IMG WIDTH=91 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline14050" SRC="img191.gif"> with <I>Q</I> unitary if <I>A</I> is complex.
The reduction is performed by subroutine PxGEHRD, which
represents
<A NAME="1998"> </A><A NAME="1999"> </A><A NAME="2000"> </A><A NAME="2001"> </A>
<I>Q</I> in a factored form, as described in section <A HREF="node66.html#secorthog">3.4</A>.
The routine PxORMHR<A NAME="2003"> </A><A NAME="2004"> </A> (or in the complex case PxUNMHR) is provided to<A NAME="2005"> </A><A NAME="2006"> </A>
multiply another matrix by <I>Q</I> without forming <I>Q</I> explicitly.
<LI> The upper Hessenberg matrix <I>H</I> is reduced to Schur form <I>T</I>,
<A NAME="2007"> </A>
giving the Schur factorization <IMG WIDTH=85 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline14066" SRC="img192.gif">
(for <I>H</I> real) or <IMG WIDTH=87 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline14070" SRC="img193.gif"> (for <I>H</I> complex). The matrix <I>S</I> (the Schur vectors
of <I>H</I>) may
optionally be computed as well. Alternatively <I>S</I> may be postmultiplied
into the matrix <I>Q</I> determined in stage 1, to give the matrix <I>Z</I> = <I>Q S</I>, the
Schur vectors of <I>A</I>. The eigenvalues<A NAME="2008"> </A> are obtained from the
diagonal of <I>T</I>. All this is done by subroutine PxLAHQR.
<A NAME="2009"> </A><A NAME="2010"> </A>
<P>
</OL>
<P>
The algorithm used in PxLAHQR is similar to the LAPACK routine xLAHQR.
Unlike xLAHQR, however, instead of sending one double shift through
the largest unreduced submatrix, this algorithm sends multiple double shifts
and spaces them apart so that there can be parallelism across
several processor row/columns.
Another critical difference is that this algorithm
applies multiple double shifts in a block fashion, as
opposed to xLAHQR which applies one double shift at a time, and xHSEQR
from LAPACK which attempts to achieve a blocked code by combining the
double shifts into one single large multi-shift.
For complete details, please refer to [<A HREF="node189.html#lawn121">79</A>].
<P>
See table <A HREF="node63.html#tabcompeig2">3.9</A> for a complete list of the routines.
<P>
<P><A NAME="2015"> </A><A NAME="tabcompeig2"> </A><IMG WIDTH=741 HEIGHT=154 ALIGN=BOTTOM ALT="table2014" SRC="img194.gif"><BR>
<STRONG>Table 3.9:</STRONG> Computational routines for the nonsymmetric eigenproblem<BR>
<P><HR><A NAME="tex2html2940" HREF="node64.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html2938" HREF="node62.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html2934" HREF="node62.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html2942" HREF="node1.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="http://www.netlib.org/utk/icons/contents_motif.gif"></A> <A NAME="tex2html2943" HREF="node190.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="http://www.netlib.org/utk/icons/index_motif.gif"></A> <BR>
<B> Next:</B> <A NAME="tex2html2941" HREF="node64.html">Singular Value Decomposition</A>
<B>Up:</B> <A NAME="tex2html2939" HREF="node62.html">Nonsymmetric Eigenproblems</A>
<B> Previous:</B> <A NAME="tex2html2935" HREF="node62.html">Nonsymmetric Eigenproblems</A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
