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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
<!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>Eigenvalue Problems</TITLE>
<META NAME="description" CONTENT="Eigenvalue Problems">
<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="tex2html3695" HREF="node120.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3693" HREF="node117.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3689" HREF="node118.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3697" 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="tex2html3698" 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="tex2html3696" HREF="node120.html">Performance Evaluation</A>
<B>Up:</B> <A NAME="tex2html3694" HREF="node117.html">Solving Linear Systems of </A>
<B> Previous:</B> <A NAME="tex2html3690" HREF="node118.html">Solving Linear Least Squares </A>
<BR> <P>
<H3><A NAME="SECTION04526200000000000000">Eigenvalue Problems</A></H3>
<A NAME="subseceig"> </A>
<P>
ScaLAPACK includes block algorithms for
solving symmetric<A NAME="4024"> </A> and nonsymmetric
eigenvalue problems as well as for computing the singular value
decomposition.
<P>
The first step in solving many types of eigenvalue problems is to reduce
the original matrix to a ``condensed form'' by orthogonal
transformations.
<A NAME="4025"> </A>
<A NAME="4026"> </A>
In the reduction to condensed
forms, the unblocked algorithms
all use elementary Householder
matrices and have good vector
performance. Block forms of
these algorithms have been
developed [<A HREF="node189.html#lawn92">28</A>],
but all require additional
operations, and a significant
proportion of the work must
still be performed by the
Level 2 PBLAS. Thus, there
is less possibility of
compensating for the extra
operations.
<P>
The algorithms concerned are listed below:
<P>
<UL>
<LI> Reduction of a symmetric matrix to tridiagonal
form<A NAME="4029"> </A> to solve a
symmetric eigenvalue problem: ScaLAPACK routine
PSSYTRD<A NAME="4030"> </A>/PDSYTRD<A NAME="4031"> </A>
applies a symmetric block update of the form
<BR><IMG WIDTH=340 HEIGHT=21 ALIGN=BOTTOM ALT="displaymath16854" SRC="img404.gif"><BR>
using the Level 3 PBLAS routine PSSYR2K<A NAME="4032"> </A>/PDSYR2K<A NAME="4033"> </A>;
Level 3 PBLAS account for at most half the work.
<LI> Reduction of a rectangular matrix to bidiagonal
form<A NAME="4034"> </A> to compute a singular
value decomposition: ScaLAPACK routine PSGEBRD
<A NAME="4035"> </A>/PDGEBRD<A NAME="4036"> </A> applies
a block update of the form
<BR><IMG WIDTH=339 HEIGHT=21 ALIGN=BOTTOM ALT="displaymath16855" SRC="img405.gif"><BR>
using two calls to the Level 3 PBLAS routine PSGEMM/PDGEMM;
Level 3 PBLAS account for at most half the work.
<LI> Reduction of a nonsymmetric matrix to Hessenberg
form<A NAME="4037"> </A><A NAME="4038"> </A>
to solve a nonsymmetric eigenvalue problem: ScaLAPACK routine
PSGEHRD<A NAME="4039"> </A>/PDGEHRD<A NAME="4040"> </A> applies a
block update of the form
<BR><IMG WIDTH=369 HEIGHT=21 ALIGN=BOTTOM ALT="displaymath16856" SRC="img406.gif"><BR>
Level 3 PBLAS account for at most three-quarters of the work.
<P>
</UL>
<P>
Extra work must be performed
to compute the <I>N</I>-by-<I>K</I>
matrices <I>X</I> and <I>Y</I> that
are required for the block
updates (<I>K</I> is the block
size), and extra workspace
is needed to store them.
<P>
Following the
reduction of
a dense symmetric matrix
to tridiagonal
form <I>T</I>, one
must compute the
eigenvalues and
(optionally)
eigenvectors
of <I>T</I>. The
current version
of ScaLAPACK
includes two
different
routines
PSSYEVX<A NAME="4042"> </A>/PDSYEVX<A NAME="4043"> </A>
and PSSYEV<A NAME="4044"> </A>/PDSYEV<A NAME="4045"> </A>
for solving symmetric
eigenproblems.
PSSYEVX/PDSYEVX
uses bisection and
inverse iteration.
PSSYEV/PDSYEV
uses the <I>QR</I> algorithm.
Table <A HREF="node119.html#tabevxperf">5.12</A><A NAME="4047"> </A>
and Table <A HREF="node119.html#tabevperf">5.13</A><A NAME="4049"> </A>
show the execution time
in seconds of the routines
PSSYEVX/PDSYEVX and
PSSYEV<A NAME="4050"> </A>/PDSYEV<A NAME="4051"> </A>,
respectively,
for computing the
eigenvalues and
eigenvectors of
symmetric matrices
of order <I>N</I>.
The performance of PSSYEVX<A NAME="4052"> </A>/PDSYEVX<A NAME="4053"> </A>
deteriorates in the face of large clusters of eigenvalues.
ScaLAPACK uses a nonscalable definition of clusters (because
we chose to remain consistent with LAPACK). Hence, matrices
larger than <I>N</I>=1000 tend to have at least one very large cluster
(see section <A HREF="node126.html#subsecperfsyevx">5.3.6</A>). This needs further study.
More
detailed information
concerning the performance
of these routines may be
found in [<A HREF="node189.html#lawn86">40</A>].
Table <A HREF="node119.html#tabsvdperf">5.14</A><A NAME="4057"> </A>
shows the execution time
in seconds of the routines
PSGESVD<A NAME="4058"> </A>/PDGESVD<A NAME="4059"> </A>
for computing the
singular values and
the corresponding
right and left
singular vectors
of a general matrix
of order <I>N</I>.
<P>
<P><A NAME="4061"> </A><A NAME="tabevxperf"> </A><IMG WIDTH=747 HEIGHT=584 ALIGN=BOTTOM ALT="table4060" SRC="img407.gif"><BR>
<STRONG>Table 5.12:</STRONG> Execution time in seconds of
PSSYEVX/PDSYEVX for square
matrices of order <I>N</I><BR>
<P>
For computing the eigenvalues and eigenvectors of a Hessenberg
matrix--or rather, for computing its Schur factorization--
two flavors of block algorithms have been developed. The first
algorithm implemented in the routine
PSLAHQR<A NAME="4081"> </A>/PDLAHQR<A NAME="4082"> </A>
results from the parallelization of the <I>QR</I> algorithm.
The key idea is to generate many shifts at once rather than two
at a time, thereby allowing all bulges to carry out up-to-date
shifts. The second algorithm that is currently implemented as a
prototype code<A NAME="4083"> </A>
is based on the computation of the matrix sign function
[<A HREF="node189.html#baidemmel92a">14</A>, <A HREF="node189.html#lawn91">13</A>, <A HREF="node189.html#baidemmel97">12</A>].
In this section, however, only performance results of the
first approach are reported.
<P><A NAME="4086"> </A><A NAME="tabevperf"> </A><IMG WIDTH=747 HEIGHT=584 ALIGN=BOTTOM ALT="table4085" SRC="img408.gif"><BR>
<STRONG>Table 5.13:</STRONG> Execution time in seconds of
PSSYEV/PDSYEV for square
matrices of order <I>N</I><BR>
<P>
<P><A NAME="4107"> </A><A NAME="tabsvdperf"> </A><IMG WIDTH=747 HEIGHT=483 ALIGN=BOTTOM ALT="table4106" SRC="img409.gif"><BR>
<STRONG>Table 5.14:</STRONG> Execution time in seconds of
PSGESVD/PDGESVD for square
matrices of order <I>N</I><BR>
<P>
Table <A HREF="node119.html#tabpdlahqr">5.15</A><A NAME="4127"> </A>
summarizes performance results obtained for the ScaLAPACK
routine PDLAHQR doing a full Schur decomposition of an
order <I>N</I> upper Hessenberg matrix. The supercomputers
the table gives timings for are the Intel XP/S MP Paragon
supercomputer and technology from the Intel ASCI Option Red
Supercomputer. For both machines, we assume only one CPU
is being used for computation on this code.
The Schur decomposition is based on iteratively
applying orthogonal similarity transformations on a Hessenberg matrix
<I>H</I> such as
<BR><IMG WIDTH=294 HEIGHT=21 ALIGN=BOTTOM ALT="displaymath16857" SRC="img410.gif"><BR>
until <I>T</I> becomes pseudo-upper triangular (i.e., in the real case,
having one by one or two by two subdiagonal blocks.)
The serial performance (assuming roughly <IMG WIDTH=38 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline16994" SRC="img411.gif"> flops) of the LAPACK
routine DLAHQR for computing a complex Schur decomposition is around
8.5 Mflops on the Intel MP Paragon supercomputer. The enhanced performance
shown in Table <A HREF="node119.html#tabpdlahqr">5.15</A> is slightly faster, a bit above 9 Mflops,
and ends up peaking around 10 Mflops because of the block application
of Householder transforms found in the ScaLAPACK serial auxiliary
routine DLAREF. For the technology behind the Intel ASCI Option Red
Supercomputer, it peaks at several times the speed of the Paragon, and has
a slightly faster drop off in efficiency. For further details and timings,
please see [<A HREF="node189.html#lawn121">79</A>].
<P><A NAME="4131"> </A><A NAME="tabpdlahqr"> </A><IMG WIDTH=746 HEIGHT=325 ALIGN=BOTTOM ALT="table4130" SRC="img412.gif"><BR>
<STRONG>Table 5.15:</STRONG> Execution time in seconds of
PDLAHQR for square
matrices of order <I>N</I><BR>
<P>
A more detailed performance analysis of the eigensolvers
included in the ScaLAPACK software library can be found
in [<A HREF="node189.html#henry97a">48</A>, <A HREF="node189.html#lawn121">79</A>].
Finally, we note that research into parallel algorithms
for symmetric and nonsymmetric eigenproblems continues
[<A HREF="node189.html#bai92a">11</A>, <A HREF="node189.html#huss93a">86</A>, <A HREF="node189.html#dhillonparlett97">45</A>],
and future versions of ScaLAPACK will be updated
to contain the best algorithms available.
<P>
<HR><A NAME="tex2html3695" HREF="node120.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3693" HREF="node117.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3689" HREF="node118.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3697" 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="tex2html3698" 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="tex2html3696" HREF="node120.html">Performance Evaluation</A>
<B>Up:</B> <A NAME="tex2html3694" HREF="node117.html">Solving Linear Systems of </A>
<B> Previous:</B> <A NAME="tex2html3690" HREF="node118.html">Solving Linear Least Squares </A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
