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
|
<!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>Local Storage Schemes for Tridiagonal Matrices</TITLE>
<META NAME="description" CONTENT="Local Storage Schemes for Tridiagonal Matrices">
<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="tex2html3248" HREF="node86.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3246" HREF="node81.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3240" HREF="node84.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3250" 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="tex2html3251" 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="tex2html3249" HREF="node86.html">Array Descriptor for Narrow </A>
<B>Up:</B> <A NAME="tex2html3247" HREF="node81.html">In-Core Narrow Band and </A>
<B> Previous:</B> <A NAME="tex2html3241" HREF="node84.html">Local Storage Scheme for </A>
<BR> <P>
<H2><A NAME="SECTION04444000000000000000">Local Storage Schemes for Tridiagonal Matrices</A></H2>
<P>
<A NAME="examplestridiag"> </A>
<P>
A global tridiagonal matrix
<I>A</I><A NAME="3033"> </A>,
represented as three vectors
(<I>DL</I>, <I>D</I>, <I>DU</I>), should be
distributed over a one-dimensional
process grid assuming a block-column
data distribution. We assume that
the coefficient tridiagonal matrix
<I>A</I><A NAME="3034"> </A><A NAME="3035"> </A>
is of size <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline15332" SRC="img341.gif"> (<IMG WIDTH=67 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline15334" SRC="img342.gif">)
and is represented by the following.
<P>
<BR><IMG WIDTH=418 HEIGHT=153 ALIGN=BOTTOM ALT="displaymath15653" SRC="img350.gif"><BR>
<P>
If we first assume that the matrix <I>A</I> is
nonsymmetric (diagonally dominant like),
and it is known <EM>a priori</EM> that no
pivoting is required for numerical stability,
the user may choose to perform no pivoting
during the factorization
(PxDTTRF<A NAME="3059"> </A><A NAME="3060"> </A><A NAME="3061"> </A><A NAME="3062"> </A>).
If we distribute this matrix
(assuming no pivoting) onto
a <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline14534" SRC="img252.gif"> process grid
with a block size of <IMG WIDTH=80 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline15430" SRC="img346.gif">,
the processes would contain the
local arrays found in figure <A HREF="node85.html#figtridiagnp7">4.13</A>.
<P>
<P><A NAME="3098"> </A><A NAME="figtridiagnp7"> </A><IMG WIDTH=344 HEIGHT=110 ALIGN=BOTTOM ALT="figure3064" SRC="img351.gif"><BR>
<STRONG>Figure 4.13:</STRONG> Mapping of local arrays for nonsymmetric tridiagonal
matrix <I>A</I><BR>
<P>
<P>
Finally, a global symmetric positive
definite tridiagonal matrix <I>A</I><A NAME="3101"> </A>,
represented as two vectors (<I>D</I> and <I>E</I>),
should be distributed over a one-dimensional
<A NAME="3102"> </A><A NAME="3103"> </A>
process grid assuming a block-column data
distribution.
<P>
Let us now assume that this matrix <I>A</I>
is symmetric positive definite and that
we distribute this matrix assuming lower
triangular storage (UPLO='L') onto a
<IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline14534" SRC="img252.gif"> process grid with a block
size <IMG WIDTH=80 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline15430" SRC="img346.gif">. The processes would
contain the local arrays found in
figure <A HREF="node85.html#figLbidiag7">4.14</A>. We would
then call the routine
PxPTTRF<A NAME="3105"> </A><A NAME="3106"> </A><A NAME="3107"> </A><A NAME="3108"> </A>
to perform the factorization, for example.
<P>
<P><A NAME="3137"> </A><A NAME="figLbidiag7"> </A><IMG WIDTH=331 HEIGHT=88 ALIGN=BOTTOM ALT="figure3109" SRC="img352.gif"><BR>
<STRONG>Figure 4.14:</STRONG> Mapping of local arrays for symmetric positive definite
tridiagonal matrix <I>A</I> (UPLO='L')<BR>
<P>
<P>
If we then distributed this same
matrix assuming upper triangular
storage (UPLO='U') onto a <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline14534" SRC="img252.gif">
process grid with a block size <IMG WIDTH=80 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline15430" SRC="img346.gif">,
the processes would contain the local
arrays found in figure <A HREF="node85.html#figUbidiag7">4.15</A>.
<P>
<P><A NAME="3169"> </A><A NAME="figUbidiag7"> </A><IMG WIDTH=331 HEIGHT=88 ALIGN=BOTTOM ALT="figure3141" SRC="img353.gif"><BR>
<STRONG>Figure 4.15:</STRONG> Mapping of local arrays for symmetric positive definite
tridiagonal matrix <I>A</I> (UPLO='U')<BR>
<P>
<P>
Note that in the tridiagonal cases,
it is not necessary to maintain the
empty storage positions as designated
by <IMG WIDTH=7 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline15263" SRC="img329.gif"> in the narrow band routines.
<P>
The matrix of right-hand-side
vectors <I>B</I> (for example, used in
PxDTTRS<A NAME="3172"> </A><A NAME="3173"> </A><A NAME="3174"> </A><A NAME="3175"> </A>
and PxPTTRS<A NAME="3176"> </A><A NAME="3177"> </A><A NAME="3178"> </A><A NAME="3179"> </A>)
is assumed to be a dense matrix distributed
block-row across the process grid. Thus,
consecutive blocks of rows of the matrix
<I>B</I> are assigned to successive processes
in the process grid, as described in
section <A HREF="node82.html#sec1dbd">4.4.1</A>.
<P>
<HR><A NAME="tex2html3248" HREF="node86.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3246" HREF="node81.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3240" HREF="node84.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3250" 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="tex2html3251" 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="tex2html3249" HREF="node86.html">Array Descriptor for Narrow </A>
<B>Up:</B> <A NAME="tex2html3247" HREF="node81.html">In-Core Narrow Band and </A>
<B> Previous:</B> <A NAME="tex2html3241" HREF="node84.html">Local Storage Scheme for </A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
