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
|
<!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 Scheme for Narrow Band Matrices</TITLE>
<META NAME="description" CONTENT="Local Storage Scheme for Narrow Band 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="tex2html3236" HREF="node85.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3234" 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="tex2html3228" HREF="node83.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3238" 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="tex2html3239" 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="tex2html3237" HREF="node85.html">Local Storage Schemes for </A>
<B>Up:</B> <A NAME="tex2html3235" HREF="node81.html">In-Core Narrow Band and </A>
<B> Previous:</B> <A NAME="tex2html3229" HREF="node83.html">The Block Mapping</A>
<BR> <P>
<H2><A NAME="SECTION04443000000000000000">Local Storage Scheme for Narrow Band Matrices</A></H2>
<A NAME="seclocalband"> </A>
<P>
Let us first discuss how to distribute
a narrow band matrix <I>A</I><A NAME="2792"> </A>
over a one-dimensional process grid
using a block-column distribution.
We assume that the coefficient band
matrix <I>A</I><A NAME="2793"> </A><A NAME="2794"> </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">)
with a bandwidth <I>BW</I>=2 if the matrix
<I>A</I> is symmetric positive definite,
and <I>BWL</I>=2 and <I>BWU</I>=2 if the matrix
<I>A</I> is nonsymmetric. The matrix <I>A</I> is
represented by the following.
<P>
<BR><IMG WIDTH=418 HEIGHT=153 ALIGN=BOTTOM ALT="displaymath15326" SRC="img343.gif"><BR>
<P>
If we assume that the matrix <I>A</I>
is nonsymmetric band, the user may
choose to perform partial pivoting
or no pivoting during the factorization
(PxGBTRF<A NAME="2827"> </A><A NAME="2828"> </A><A NAME="2829"> </A><A NAME="2830"> </A>
or PxDBTRF<A NAME="2831"> </A><A NAME="2832"> </A><A NAME="2833"> </A><A NAME="2834"> </A>,
respectively). Both strategies
assume a block-column distribution
of the coefficient matrix, but
additional storage is required
for fill-in if partial pivoting
is selected. First, let us assume
that we have selected no pivoting,
and we distribute this matrix 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=92 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline15352" SRC="img344.gif">. The
processes would contain the local
arrays found in figure <A HREF="node84.html#fignonsymmbandnp7">4.9</A>.
Figure <A HREF="node84.html#fignonsymmbandnp7">4.9</A>
also illustrates that the leading
dimension of the local arrays
containing the coefficient matrix
must be at least <I>BWL</I>+1+<I>BWU</I> for
the non-pivoting narrow band linear
solver.
<P>
<P><A NAME="2881"> </A><A NAME="fignonsymmbandnp7"> </A><IMG WIDTH=299 HEIGHT=149 ALIGN=BOTTOM ALT="figure2837" SRC="img345.gif"><BR>
<STRONG>Figure 4.9:</STRONG> Mapping of local arrays for nonsymmetric band matrix <I>A</I>
(no pivoting)<BR>
<P>
<P>
If, however, we select partial pivoting
and distribute this same matrix 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="node84.html#fignonsymmbandpp7">4.10</A>.
The amount of additional storage
required for fill-in is represented
by <I>F</I> in the figure and is equal
to the sum of the lower bandwidth
(number of subdiagonals), BWL, and
the upper bandwidth (number of
superdiagonals), BWU. In this
example, <I>BWL</I>=2 and <I>BWU</I>=2.
Refer to the leading comments
of the routine PxGBTRF for
further details. Figure <A HREF="node84.html#fignonsymmbandpp7">4.10</A>
also illustrates that the leading
dimension of the local arrays
containing the coefficient matrix
must be at least 2*(<I>BWL</I>+<I>BWU</I>)+1
for the partial pivoting narrow
band linear solver.
<P>
<P><A NAME="2930"> </A><A NAME="fignonsymmbandpp7"> </A><IMG WIDTH=299 HEIGHT=235 ALIGN=BOTTOM ALT="figure2886" SRC="img347.gif"><BR>
<STRONG>Figure 4.10:</STRONG> Mapping of local arrays for nonsymmetric band matrix
<I>A</I> (partial pivoting)<BR>
<P>
<P>
Let us now assume that the matrix <I>A</I> is
symmetric positive definite band with <I>BW</I>=2,
and 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="node84.html#figLsymmband7">4.11</A>. We would
then call the routine
PxPBTRF<A NAME="2934"> </A><A NAME="2935"> </A><A NAME="2936"> </A><A NAME="2937"> </A>
with <I>BW</I>=2 to perform the factorization,
for example.
<P>
<P><A NAME="2971"> </A><A NAME="figLsymmband7"> </A><IMG WIDTH=299 HEIGHT=106 ALIGN=BOTTOM ALT="figure2938" SRC="img348.gif"><BR>
<STRONG>Figure 4.11:</STRONG> Mapping of local arrays for symmetric positive definite
band 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="node84.html#figUsymmband7">4.12</A>.
<P>
<P><A NAME="3008"> </A><A NAME="figUsymmband7"> </A><IMG WIDTH=299 HEIGHT=106 ALIGN=BOTTOM ALT="figure2975" SRC="img349.gif"><BR>
<STRONG>Figure 4.12:</STRONG> Mapping of local arrays for symmetric positive definite
band matrix <I>A</I> (UPLO='U')<BR>
<P>
<P>
Figures <A HREF="node84.html#figLsymmband7">4.11</A>
and <A HREF="node84.html#figUsymmband7">4.12</A> also
illustrate that the leading
dimension of the local arrays
containing the coefficient matrix
must be at least <I>BW</I>+1 for the
symmetric positive definite narrow
band linear solver.
<P>
The <IMG WIDTH=7 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline15263" SRC="img329.gif"> notation in
figures <A HREF="node84.html#fignonsymmbandnp7">4.9</A>,
<A HREF="node84.html#fignonsymmbandpp7">4.10</A>, <A HREF="node84.html#figLsymmband7">4.11</A>,
and <A HREF="node84.html#figUsymmband7">4.12</A> and the
<I>F</I> notation in figure <A HREF="node84.html#fignonsymmbandpp7">4.10</A>
signify an entry in which one
need not store a value in that
position of the local array.
These storage positions, however,
are required and overwritten
during the computation.
<P>
The <IMG WIDTH=93 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline15189" SRC="img320.gif"> matrix of
right-hand-side vectors <I>B</I>
(for example, used in
PxGBTRS<A NAME="3018"> </A><A NAME="3019"> </A><A NAME="3020"> </A><A NAME="3021"> </A>, PxDBTRS<A NAME="3022"> </A><A NAME="3023"> </A><A NAME="3024"> </A><A NAME="3025"> </A>,
and PxPBTRS<A NAME="3026"> </A><A NAME="3027"> </A><A NAME="3028"> </A><A NAME="3029"> </A>)
is assumed to be a dense matrix
distributed in a block-row manner
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="tex2html3236" HREF="node85.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3234" 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="tex2html3228" HREF="node83.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3238" 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="tex2html3239" 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="tex2html3237" HREF="node85.html">Local Storage Schemes for </A>
<B>Up:</B> <A NAME="tex2html3235" HREF="node81.html">In-Core Narrow Band and </A>
<B> Previous:</B> <A NAME="tex2html3229" HREF="node83.html">The Block Mapping</A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
