Information Technology Reference
In-Depth Information
α
00
α
α
α
α
01
02
α
11
α
α
10
12
13
α
20
α
21
α
22
α
α
23
24
α
α
α
31
α
32
α
33
α
00
α
10
α
11
α
21
α
22
α
32
α
33
α
43
α
44
α
54
α
55
34
35
45
α
42
α
43
α
44
*
α
53
α
54
α
55
α
20
α
31
α
42
α
53
*
*
Fig. 1.
6
×
6 symmetric and matrix with bandwidth
k
= 2 (left); packed storage scheme
used in BLAS and LAPACK (right)
A
yields a large reduction in the number of computations and in memory re-
quirements. In particular, due to the symmetry of
A
, only its lower/upper part
needs to be stored. Additionally, due to its band structure, the null elements
that lie out of the band do not need to be kept. The number of arithmetic oper-
ations may also be reduced as all the computations involving null elements are
not necessary. Band matrices present also favorable differences when compared
with unstructured sparse matrices. Specifically, storage formats for unstructured
sparse matrices are complex, as the position of each nonzero must also be stored,
but for band matrices the data layout can be simplified because the structure
of the nonzeros is regular and, consequently, it is not necessary to maintain the
coordinates of each element of the matrix. Additionally, the memory accesses
can be performed with a regular and predictable pattern.
The positive properties of symmetric band matrices, and the availability of
reordering techniques (e.g. the RCM method [3]) to transform symmetric sparse
matrices, in some cases, into symmetric narrow-band matrices has motivated the
exploitation of these favourable properties in several engineering applications,
including real optimization, numerical solution of partial differential equations,
and control theory problems; see, among others, [5,2].
The advantages of exploiting the structure of symmetric band matrices moti-
vated the inclusion of specific routines in BLAS and LAPACK [1]. The BLAS
specification defines a compact storage format for symmetric band matrices (see
Figure 1) that is a trade-off between minimal storage and optimal access pattern
to the matrix elements. In particular, the symmetric band storage format stores
(
k
+1)
m
elements, where
k
represents the number of nonzero super- and sub-
diagonals, and
m
is the number of rows and columns of the matrix. Only a few
null elements are stored (marked in Figure 1 with the symbol “*”). However, the
main feature of this storage format is that it permits a memory access pattern
very convenient for today's cache-based architectures.
The support of BLAS for symmetric band matrices comprises a small set of
routines that implement some key linear algebra operations. This is the case
for routine sbmv, which computes a matrix-vector product where the matrix
presents a symmetric band structure. Similarly, LAPACK gives support to some
operations with band matrices; e.g., matrix factorizations and linear system
solvers [4].
×
