<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Created by GNU Texinfo 6.5, http://www.gnu.org/software/texinfo/ -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Storage of Sparse Matrices (GNU Octave (version 5.1.0))</title>
<meta name="description" content="Storage of Sparse Matrices (GNU Octave (version 5.1.0))">
<meta name="keywords" content="Storage of Sparse Matrices (GNU Octave (version 5.1.0))">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<link href="index.html#Top" rel="start" title="Top">
<link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="Basics.html#Basics" rel="up" title="Basics">
<link href="Creating-Sparse-Matrices.html#Creating-Sparse-Matrices" rel="next" title="Creating Sparse Matrices">
<link href="Basics.html#Basics" rel="prev" title="Basics">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.indentedblock {margin-right: 0em}
blockquote.smallindentedblock {margin-right: 0em; font-size: smaller}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
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.nolinebreak {white-space: nowrap}
span.roman {font-family: initial; font-weight: normal}
span.sansserif {font-family: sans-serif; font-weight: normal}
ul.no-bullet {list-style: none}
-->
</style>
<link rel="stylesheet" type="text/css" href="octave.css">
</head>
<body lang="en">
<a name="Storage-of-Sparse-Matrices"></a>
<div class="header">
<p>
Next: <a href="Creating-Sparse-Matrices.html#Creating-Sparse-Matrices" accesskey="n" rel="next">Creating Sparse Matrices</a>, Up: <a href="Basics.html#Basics" accesskey="u" rel="up">Basics</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Storage-of-Sparse-Matrices-1"></a>
<h4 class="subsection">22.1.1 Storage of Sparse Matrices</h4>
<p>It is not strictly speaking necessary for the user to understand how
sparse matrices are stored. However, such an understanding will help
to get an understanding of the size of sparse matrices. Understanding
the storage technique is also necessary for those users wishing to
create their own oct-files.
</p>
<p>There are many different means of storing sparse matrix data. What all
of the methods have in common is that they attempt to reduce the complexity
and storage given a priori knowledge of the particular class of problems
that will be solved. A good summary of the available techniques for storing
sparse matrix is given by Saad <a name="DOCF8" href="#FOOT8"><sup>8</sup></a>.
With full matrices, knowledge of the point of an element of the matrix
within the matrix is implied by its position in the computers memory.
However, this is not the case for sparse matrices, and so the positions
of the nonzero elements of the matrix must equally be stored.
</p>
<p>An obvious way to do this is by storing the elements of the matrix as
triplets, with two elements being their position in the array
(rows and column) and the third being the data itself. This is conceptually
easy to grasp, but requires more storage than is strictly needed.
</p>
<p>The storage technique used within Octave is the compressed column
format. It is similar to the Yale format.
<a name="DOCF9" href="#FOOT9"><sup>9</sup></a>
In this format the position of each element in a row and the data are
stored as previously. However, if we assume that all elements in the
same column are stored adjacent in the computers memory, then we only
need to store information on the number of nonzero elements in each
column, rather than their positions. Thus assuming that the matrix has
more nonzero elements than there are columns in the matrix, we win in
terms of the amount of memory used.
</p>
<p>In fact, the column index contains one more element than the number of
columns, with the first element always being zero. The advantage of
this is a simplification in the code, in that there is no special case
for the first or last columns. A short example, demonstrating this in
C is.
</p>
<div class="example">
<pre class="example"> for (j = 0; j < nc; j++)
for (i = cidx(j); i < cidx(j+1); i++)
printf ("nonzero element (%i,%i) is %d\n",
ridx(i), j, data(i));
</pre></div>
<p>A clear understanding might be had by considering an example of how the
above applies to an example matrix. Consider the matrix
</p>
<div class="example">
<pre class="example"> 1 2 0 0
0 0 0 3
0 0 0 4
</pre></div>
<p>The nonzero elements of this matrix are
</p>
<div class="example">
<pre class="example"> (1, 1) ⇒ 1
(1, 2) ⇒ 2
(2, 4) ⇒ 3
(3, 4) ⇒ 4
</pre></div>
<p>This will be stored as three vectors <var>cidx</var>, <var>ridx</var> and <var>data</var>,
representing the column indexing, row indexing and data respectively. The
contents of these three vectors for the above matrix will be
</p>
<div class="example">
<pre class="example"> <var>cidx</var> = [0, 1, 2, 2, 4]
<var>ridx</var> = [0, 0, 1, 2]
<var>data</var> = [1, 2, 3, 4]
</pre></div>
<p>Note that this is the representation of these elements with the first row
and column assumed to start at zero, while in Octave itself the row and
column indexing starts at one. Thus the number of elements in the
<var>i</var>-th column is given by <code><var>cidx</var> (<var>i</var> + 1) -
<var>cidx</var> (<var>i</var>)</code>.
</p>
<p>Although Octave uses a compressed column format, it should be noted
that compressed row formats are equally possible. However, in the
context of mixed operations between mixed sparse and dense matrices,
it makes sense that the elements of the sparse matrices are in the
same order as the dense matrices. Octave stores dense matrices in
column major ordering, and so sparse matrices are equally stored in
this manner.
</p>
<p>A further constraint on the sparse matrix storage used by Octave is that
all elements in the rows are stored in increasing order of their row
index, which makes certain operations faster. However, it imposes
the need to sort the elements on the creation of sparse matrices. Having
disordered elements is potentially an advantage in that it makes operations
such as concatenating two sparse matrices together easier and faster, however
it adds complexity and speed problems elsewhere.
</p>
<div class="footnote">
<hr>
<h4 class="footnotes-heading">Footnotes</h4>
<h3><a name="FOOT8" href="#DOCF8">(8)</a></h3>
<p>Y. Saad "SPARSKIT: A basic
toolkit for sparse matrix computation", 1994,
<a href="https://www-users.cs.umn.edu/~saad/software/SPARSKIT/paper.ps">https://www-users.cs.umn.edu/~saad/software/SPARSKIT/paper.ps</a></p>
<h3><a name="FOOT9" href="#DOCF9">(9)</a></h3>
<p><a href="https://en.wikipedia.org/wiki/Sparse_matrix#Yale_format">https://en.wikipedia.org/wiki/Sparse_matrix#Yale_format</a></p>
</div>
<hr>
<div class="header">
<p>
Next: <a href="Creating-Sparse-Matrices.html#Creating-Sparse-Matrices" accesskey="n" rel="next">Creating Sparse Matrices</a>, Up: <a href="Basics.html#Basics" accesskey="u" rel="up">Basics</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
