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
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 The GSL Team.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".
(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library – Reference Manual: Sparse Matrices Overview</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Sparse Matrices Overview">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Sparse Matrices Overview">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Sparse-Matrices.html#Sparse-Matrices" rel="up" title="Sparse Matrices">
<link href="Sparse-Matrices-Allocation.html#Sparse-Matrices-Allocation" rel="next" title="Sparse Matrices Allocation">
<link href="Sparse-Matrices.html#Sparse-Matrices" rel="previous" title="Sparse Matrices">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>
</head>
<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Sparse-Matrices-Overview"></a>
<div class="header">
<p>
Next: <a href="Sparse-Matrices-Allocation.html#Sparse-Matrices-Allocation" accesskey="n" rel="next">Sparse Matrices Allocation</a>, Up: <a href="Sparse-Matrices.html#Sparse-Matrices" accesskey="u" rel="up">Sparse Matrices</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Overview-7"></a>
<h3 class="section">41.1 Overview</h3>
<a name="index-sparse-matrices_002c-overview"></a>
<p>These routines provide support for constructing and manipulating
sparse matrices in GSL, using an API similar to <code>gsl_matrix</code>.
The basic structure is called <code>gsl_spmatrix</code>. There are
three supported storage formats for sparse matrices: the triplet,
compressed column storage (CCS) and compressed row storage (CRS)
formats. The triplet format stores triplets <em>(i,j,x)</em> for each
non-zero element of the matrix. This notation means that the
<em>(i,j)</em> element of the matrix <em>A</em>
is <em>A_{ij} = x</em>. Compressed column storage stores each column of
non-zero values in the sparse matrix in a continuous memory block, keeping
pointers to the beginning of each column in that memory block, and storing
the row indices of each non-zero element. Compressed row storage stores
each row of non-zero values in a continuous memory block, keeping pointers
to the beginning of each row in the block and storing the column indices
of each non-zero element. The triplet format is ideal
for adding elements to the sparse matrix structure while it is being
constructed, while the compressed storage formats are better suited for
matrix-matrix multiplication or linear solvers.
</p>
<a name="index-gsl_005fspmatrix"></a>
<p>The <code>gsl_spmatrix</code> structure is defined as
</p>
<div class="example">
<pre class="example">typedef struct
{
size_t size1;
size_t size2;
size_t *i;
double *data;
size_t *p;
size_t nzmax;
size_t nz;
gsl_spmatrix_tree *tree_data;
void *work;
size_t sptype;
} gsl_spmatrix;
</pre></div>
<p>This defines a <var>size1</var>-by-<var>size2</var> sparse matrix. The number of non-zero
elements currently in the matrix is given by <var>nz</var>. For the triplet
representation, <var>i</var>, <var>p</var>, and <var>data</var> are arrays of size <var>nz</var>
which contain the row indices, column indices, and element value, respectively.
So if <em>data[k] = A(i,j)</em>, then <em>i = i[k]</em> and <em>j = p[k]</em>.
</p>
<p>For compressed column storage, <var>i</var> and <var>data</var> are arrays of size
<var>nz</var> containing the row indices and element values, identical to the triplet
case. <var>p</var> is an array of size <em>size2 + 1</em> where <em>p[j]</em> points
to the index in <var>data</var> of the start of column <var>j</var>. Thus, if
<em>data[k] = A(i,j)</em>, then <em>i = i[k]</em> and <em>p[j] <= k < p[j+1]</em>.
</p>
<p>For compressed row storage, <var>i</var> and <var>data</var> are arrays of size
<var>nz</var> containing the column indices and element values, identical to the triplet
case. <var>p</var> is an array of size <em>size1 + 1</em> where <em>p[i]</em> points
to the index in <var>data</var> of the start of row <var>i</var>. Thus, if
<em>data[k] = A(i,j)</em>, then <em>j = i[k]</em> and <em>p[i] <= k < p[i+1]</em>.
</p>
<p>The parameter <var>tree_data</var> is a binary tree structure used in the triplet
representation, specifically a balanced AVL tree. This speeds up element
searches and duplicate detection during the matrix assembly process.
The parameter <var>work</var> is additional workspace needed for various operations like
converting from triplet to compressed storage. <var>sptype</var> indicates
the type of storage format being used (triplet, CCS or CRS).
</p>
<p>The compressed storage format defined above makes it very simple
to interface with sophisticated external linear solver libraries
which accept compressed storage input. The user can simply
pass the arrays <var>i</var>, <var>p</var>, and <var>data</var> as the
inputs to external libraries.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Sparse-Matrices-Allocation.html#Sparse-Matrices-Allocation" accesskey="n" rel="next">Sparse Matrices Allocation</a>, Up: <a href="Sparse-Matrices.html#Sparse-Matrices" accesskey="u" rel="up">Sparse Matrices</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
