|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices
|
|
Packit |
67cb25 |
single: matrices, sparse
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
***************
|
|
Packit |
67cb25 |
Sparse Matrices
|
|
Packit |
67cb25 |
***************
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This chapter describes functions for the construction and
|
|
Packit |
67cb25 |
manipulation of sparse matrices, matrices which are populated
|
|
Packit |
67cb25 |
primarily with zeros and contain only a few non-zero elements.
|
|
Packit |
67cb25 |
Sparse matrices often appear in the solution of partial
|
|
Packit |
67cb25 |
differential equations. It is beneficial to use specialized
|
|
Packit |
67cb25 |
data structures and algorithms for storing and working with
|
|
Packit |
67cb25 |
sparse matrices, since dense matrix algorithms and structures
|
|
Packit |
67cb25 |
can be very slow and use huge amounts of memory when applied
|
|
Packit |
67cb25 |
to sparse matrices.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The header file :file:`gsl_spmatrix.h` contains the prototypes for the
|
|
Packit |
67cb25 |
sparse matrix functions and related declarations.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, overview
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Overview
|
|
Packit |
67cb25 |
========
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
These routines provide support for constructing and manipulating
|
|
Packit |
67cb25 |
sparse matrices in GSL, using an API similar to :type:`gsl_matrix`.
|
|
Packit |
67cb25 |
The basic structure is called :type:`gsl_spmatrix`. There are
|
|
Packit |
67cb25 |
three supported storage formats for sparse matrices: the triplet,
|
|
Packit |
67cb25 |
compressed column storage (CCS) and compressed row storage (CRS)
|
|
Packit |
67cb25 |
formats. The triplet format stores triplets :math:`(i,j,x)` for each
|
|
Packit |
67cb25 |
non-zero element of the matrix. This notation means that the
|
|
Packit |
67cb25 |
:math:`(i,j)` element of the matrix :math:`A`
|
|
Packit |
67cb25 |
is :math:`A_{ij} = x`. Compressed column storage stores each column of
|
|
Packit |
67cb25 |
non-zero values in the sparse matrix in a continuous memory block, keeping
|
|
Packit |
67cb25 |
pointers to the beginning of each column in that memory block, and storing
|
|
Packit |
67cb25 |
the row indices of each non-zero element. Compressed row storage stores
|
|
Packit |
67cb25 |
each row of non-zero values in a continuous memory block, keeping pointers
|
|
Packit |
67cb25 |
to the beginning of each row in the block and storing the column indices
|
|
Packit |
67cb25 |
of each non-zero element. The triplet format is ideal
|
|
Packit |
67cb25 |
for adding elements to the sparse matrix structure while it is being
|
|
Packit |
67cb25 |
constructed, while the compressed storage formats are better suited for
|
|
Packit |
67cb25 |
matrix-matrix multiplication or linear solvers.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. type:: gsl_spmatrix
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This structure is defined as::
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
typedef struct
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t size1;
|
|
Packit |
67cb25 |
size_t size2;
|
|
Packit |
67cb25 |
size_t *i;
|
|
Packit |
67cb25 |
double *data;
|
|
Packit |
67cb25 |
size_t *p;
|
|
Packit |
67cb25 |
size_t nzmax;
|
|
Packit |
67cb25 |
size_t nz;
|
|
Packit |
67cb25 |
gsl_spmatrix_tree *tree_data;
|
|
Packit |
67cb25 |
void *work;
|
|
Packit |
67cb25 |
size_t sptype;
|
|
Packit |
67cb25 |
} gsl_spmatrix;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This defines a :data:`size1`-by-:data:`size2` sparse matrix. The number of non-zero
|
|
Packit |
67cb25 |
elements currently in the matrix is given by :data:`nz`. For the triplet
|
|
Packit |
67cb25 |
representation, :data:`i`, :data:`p`, and :data:`data` are arrays of size :data:`nz`
|
|
Packit |
67cb25 |
which contain the row indices, column indices, and element value, respectively.
|
|
Packit |
67cb25 |
So if :math:`data[k] = A(i,j)`, then :math:`i = i[k]` and :math:`j = p[k]`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
For compressed column storage, :data:`i` and :data:`data` are arrays of size
|
|
Packit |
67cb25 |
:data:`nz` containing the row indices and element values, identical to the triplet
|
|
Packit |
67cb25 |
case. :data:`p` is an array of size :data:`size2` + 1 where :code:`p[j]` points
|
|
Packit |
67cb25 |
to the index in :data:`data` of the start of column :data:`j`. Thus, if
|
|
Packit |
67cb25 |
:math:`data[k] = A(i,j)`, then :math:`i = i[k]` and :math:`p[j] <= k < p[j+1]`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
For compressed row storage, :data:`i` and :data:`data` are arrays of size
|
|
Packit |
67cb25 |
:data:`nz` containing the column indices and element values, identical to the triplet
|
|
Packit |
67cb25 |
case. :data:`p` is an array of size :data:`size1` + 1 where :code:`p[i]` points
|
|
Packit |
67cb25 |
to the index in :data:`data` of the start of row :data:`i`. Thus, if
|
|
Packit |
67cb25 |
:math:`data[k] = A(i,j)`, then :math:`j = i[k]` and :math:`p[i] <= k < p[i+1]`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The parameter :data:`tree_data` is a binary tree structure used in the triplet
|
|
Packit |
67cb25 |
representation, specifically a balanced AVL tree. This speeds up element
|
|
Packit |
67cb25 |
searches and duplicate detection during the matrix assembly process.
|
|
Packit |
67cb25 |
The parameter :data:`work` is additional workspace needed for various operations like
|
|
Packit |
67cb25 |
converting from triplet to compressed storage. :data:`sptype` indicates
|
|
Packit |
67cb25 |
the type of storage format being used (triplet, CCS or CRS).
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The compressed storage format defined above makes it very simple
|
|
Packit |
67cb25 |
to interface with sophisticated external linear solver libraries
|
|
Packit |
67cb25 |
which accept compressed storage input. The user can simply
|
|
Packit |
67cb25 |
pass the arrays :data:`i`, :data:`p`, and :data:`data` as the
|
|
Packit |
67cb25 |
inputs to external libraries.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, allocation
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Allocation
|
|
Packit |
67cb25 |
==========
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The functions for allocating memory for a sparse matrix follow the style of
|
|
Packit |
67cb25 |
:func:`malloc` and :func:`free`. They also perform their own error checking. If
|
|
Packit |
67cb25 |
there is insufficient memory available to allocate a matrix then the functions
|
|
Packit |
67cb25 |
call the GSL error handler with an error code of :macro:`GSL_ENOMEM` in addition
|
|
Packit |
67cb25 |
to returning a null pointer.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: gsl_spmatrix * gsl_spmatrix_alloc (const size_t n1, const size_t n2)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function allocates a sparse matrix of size :data:`n1`-by-:data:`n2` and
|
|
Packit |
67cb25 |
initializes it to all zeros. If the size of the matrix is not known at allocation
|
|
Packit |
67cb25 |
time, both :data:`n1` and :data:`n2` may be set to 1, and they will automatically
|
|
Packit |
67cb25 |
grow as elements are added to the matrix. This function sets the
|
|
Packit |
67cb25 |
matrix to the triplet representation, which is the easiest for adding
|
|
Packit |
67cb25 |
and accessing matrix elements. This function tries to make a reasonable guess
|
|
Packit |
67cb25 |
for the number of non-zero elements (:data:`nzmax`) which will be added to the matrix by
|
|
Packit |
67cb25 |
assuming a sparse density of :math:`10\%`. The function
|
|
Packit |
67cb25 |
:func:`gsl_spmatrix_alloc_nzmax` can be used if this number is known more
|
|
Packit |
67cb25 |
accurately. The workspace is of size :math:`O(nzmax)`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: gsl_spmatrix * gsl_spmatrix_alloc_nzmax (const size_t n1, const size_t n2, const size_t nzmax, const size_t sptype)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function allocates a sparse matrix of size :data:`n1`-by-:data:`n2` and
|
|
Packit |
67cb25 |
initializes it to all zeros. If the size of the matrix is not known at allocation
|
|
Packit |
67cb25 |
time, both :data:`n1` and :data:`n2` may be set to 1, and they will automatically
|
|
Packit |
67cb25 |
grow as elements are added to the matrix. The parameter :data:`nzmax` specifies
|
|
Packit |
67cb25 |
the maximum number of non-zero elements which will be added to the matrix.
|
|
Packit |
67cb25 |
It does not need to be precisely known in advance, since storage space will
|
|
Packit |
67cb25 |
automatically grow using :func:`gsl_spmatrix_realloc` if :data:`nzmax` is not
|
|
Packit |
67cb25 |
large enough. Accurate knowledge of this parameter reduces the number of
|
|
Packit |
67cb25 |
reallocation calls required. The parameter :data:`sptype` specifies the
|
|
Packit |
67cb25 |
storage format of the sparse matrix. Possible values are
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. macro:: GSL_SPMATRIX_TRIPLET
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This flag specifies triplet storage.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. macro:: GSL_SPMATRIX_CCS
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This flag specifies compressed column storage.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. macro:: GSL_SPMATRIX_CRS
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This flag specifies compressed row storage.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The allocated :type:`gsl_spmatrix` structure is of size :math:`O(nzmax)`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_realloc (const size_t nzmax, gsl_spmatrix * m)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function reallocates the storage space for :data:`m` to accomodate
|
|
Packit |
67cb25 |
:data:`nzmax` non-zero elements. It is typically called internally by
|
|
Packit |
67cb25 |
:func:`gsl_spmatrix_set` if the user wants to add more elements to the
|
|
Packit |
67cb25 |
sparse matrix than the previously specified :data:`nzmax`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: void gsl_spmatrix_free (gsl_spmatrix * m)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function frees the memory associated with the sparse matrix :data:`m`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, accessing elements
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Accessing Matrix Elements
|
|
Packit |
67cb25 |
=========================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: double gsl_spmatrix_get (const gsl_spmatrix * m, const size_t i, const size_t j)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns element (:data:`i`, :data:`j`) of the matrix :data:`m`.
|
|
Packit |
67cb25 |
The matrix may be in triplet or compressed format.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_set (gsl_spmatrix * m, const size_t i, const size_t j, const double x)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function sets element (:data:`i`, :data:`j`) of the matrix :data:`m` to
|
|
Packit |
67cb25 |
the value :data:`x`. The matrix must be in triplet representation.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: double * gsl_spmatrix_ptr (gsl_spmatrix * m, const size_t i, const size_t j)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns a pointer to the (:data:`i`, :data:`j`) element of the matrix :data:`m`.
|
|
Packit |
67cb25 |
If the (:data:`i`, :data:`j`) element is not explicitly stored in the matrix,
|
|
Packit |
67cb25 |
a null pointer is returned.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, initializing elements
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Initializing Matrix Elements
|
|
Packit |
67cb25 |
============================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Since the sparse matrix format only stores the non-zero elements, it is automatically
|
|
Packit |
67cb25 |
initialized to zero upon allocation. The function :func:`gsl_spmatrix_set_zero` may
|
|
Packit |
67cb25 |
be used to re-initialize a matrix to zero after elements have been added to it.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_set_zero (gsl_spmatrix * m)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function sets (or resets) all the elements of the matrix :data:`m` to zero.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, reading
|
|
Packit |
67cb25 |
single: sparse matrices, writing
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Reading and Writing Matrices
|
|
Packit |
67cb25 |
============================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_fwrite (FILE * stream, const gsl_spmatrix * m)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function writes the elements of the matrix :data:`m` to the stream
|
|
Packit |
67cb25 |
:data:`stream` in binary format. The return value is 0 for success and
|
|
Packit |
67cb25 |
:macro:`GSL_EFAILED` if there was a problem writing to the file. Since the
|
|
Packit |
67cb25 |
data is written in the native binary format it may not be portable
|
|
Packit |
67cb25 |
between different architectures.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_fread (FILE * stream, gsl_spmatrix * m)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function reads into the matrix :data:`m` from the open stream
|
|
Packit |
67cb25 |
:data:`stream` in binary format. The matrix :data:`m` must be preallocated
|
|
Packit |
67cb25 |
with the correct storage format, dimensions and have a sufficiently large :data:`nzmax`
|
|
Packit |
67cb25 |
in order to read in all matrix elements, otherwise :macro:`GSL_EBADLEN`
|
|
Packit |
67cb25 |
is returned. The return value is 0 for success and
|
|
Packit |
67cb25 |
:macro:`GSL_EFAILED` if there was a problem reading from the file. The
|
|
Packit |
67cb25 |
data is assumed to have been written in the native binary format on the
|
|
Packit |
67cb25 |
same architecture.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_fprintf (FILE * stream, const gsl_spmatrix * m, const char * format)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function writes the elements of the matrix :data:`m` line-by-line to
|
|
Packit |
67cb25 |
the stream :data:`stream` using the format specifier :data:`format`, which
|
|
Packit |
67cb25 |
should be one of the :code:`%g`, :code:`%e` or :code:`%f` formats for
|
|
Packit |
67cb25 |
floating point numbers. The function returns 0 for success and
|
|
Packit |
67cb25 |
:macro:`GSL_EFAILED` if there was a problem writing to the file. The
|
|
Packit |
67cb25 |
input matrix :data:`m` may be in any storage format, and the output file
|
|
Packit |
67cb25 |
will be written in MatrixMarket format.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: gsl_spmatrix * gsl_spmatrix_fscanf (FILE * stream)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function reads sparse matrix data in the MatrixMarket format
|
|
Packit |
67cb25 |
from the stream :data:`stream` and stores it in a newly allocated matrix
|
|
Packit |
67cb25 |
which is returned in triplet format. The function returns 0 for success and
|
|
Packit |
67cb25 |
:macro:`GSL_EFAILED` if there was a problem reading from the file. The
|
|
Packit |
67cb25 |
user should free the returned matrix when it is no longer needed.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, copying
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Copying Matrices
|
|
Packit |
67cb25 |
================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_memcpy (gsl_spmatrix * dest, const gsl_spmatrix * src)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function copies the elements of the sparse matrix :data:`src` into
|
|
Packit |
67cb25 |
:data:`dest`. The two matrices must have the same dimensions and be in the
|
|
Packit |
67cb25 |
same storage format.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, exchanging rows and columns
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Exchanging Rows and Columns
|
|
Packit |
67cb25 |
===========================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_transpose_memcpy (gsl_spmatrix * dest, const gsl_spmatrix * src)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function copies the transpose of the sparse matrix :data:`src` into
|
|
Packit |
67cb25 |
:data:`dest`. The dimensions of :data:`dest` must match the transpose of the
|
|
Packit |
67cb25 |
matrix :data:`src`. Also, both matrices must use the same sparse storage
|
|
Packit |
67cb25 |
format.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_transpose (gsl_spmatrix * m)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function replaces the matrix :data:`m` by its transpose,
|
|
Packit |
67cb25 |
preserving the storage format of the input matrix. Currently,
|
|
Packit |
67cb25 |
only triplet matrix inputs are supported.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_transpose2 (gsl_spmatrix * m)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function replaces the matrix :data:`m` by its transpose, but
|
|
Packit |
67cb25 |
changes the storage format for compressed matrix inputs. Since
|
|
Packit |
67cb25 |
compressed column storage is the transpose of compressed row storage,
|
|
Packit |
67cb25 |
this function simply converts a CCS matrix to CRS and vice versa.
|
|
Packit |
67cb25 |
This is the most efficient way to transpose a compressed storage
|
|
Packit |
67cb25 |
matrix, but the user should note that the storage format of their
|
|
Packit |
67cb25 |
compressed matrix will change on output. For triplet matrices,
|
|
Packit |
67cb25 |
the output matrix is also in triplet storage.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, operations
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Matrix Operations
|
|
Packit |
67cb25 |
=================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_add (gsl_spmatrix * c, const gsl_spmatrix * a, const gsl_spmatrix * b)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function computes the sum :math:`c = a + b`. The three matrices must
|
|
Packit |
67cb25 |
have the same dimensions and be stored in a compressed format.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_scale (gsl_spmatrix * m, const double x)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function scales all elements of the matrix :data:`m` by the constant
|
|
Packit |
67cb25 |
factor :data:`x`. The result :math:`m(i,j) \leftarrow x m(i,j)` is stored in :data:`m`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, properties
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Matrix Properties
|
|
Packit |
67cb25 |
=================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: size_t gsl_spmatrix_nnz (const gsl_spmatrix * m)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns the number of non-zero elements in :data:`m`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_equal (const gsl_spmatrix * a, const gsl_spmatrix * b)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns 1 if the matrices :data:`a` and :data:`b` are equal (by comparison of
|
|
Packit |
67cb25 |
element values) and 0 otherwise. The matrices :data:`a` and :data:`b` must be in the same
|
|
Packit |
67cb25 |
sparse storage format for comparison.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, min/max elements
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Finding Maximum and Minimum Elements
|
|
Packit |
67cb25 |
====================================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_minmax (const gsl_spmatrix * m, double * min_out, double * max_out)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns the minimum and maximum elements of the matrix
|
|
Packit |
67cb25 |
:data:`m`, storing them in :data:`min_out` and :data:`max_out`, and searching
|
|
Packit |
67cb25 |
only the non-zero values.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, compression
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Compressed Format
|
|
Packit |
67cb25 |
=================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
GSL supports compressed column storage (CCS) and compressed row storage (CRS)
|
|
Packit |
67cb25 |
formats.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: gsl_spmatrix * gsl_spmatrix_ccs (const gsl_spmatrix * T)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function creates a sparse matrix in compressed column format
|
|
Packit |
67cb25 |
from the input sparse matrix :data:`T` which must be in triplet format.
|
|
Packit |
67cb25 |
A pointer to a newly allocated matrix is returned. The calling function
|
|
Packit |
67cb25 |
should free the newly allocated matrix when it is no longer needed.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: gsl_spmatrix * gsl_spmatrix_crs (const gsl_spmatrix * T)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function creates a sparse matrix in compressed row format
|
|
Packit |
67cb25 |
from the input sparse matrix :data:`T` which must be in triplet format.
|
|
Packit |
67cb25 |
A pointer to a newly allocated matrix is returned. The calling function
|
|
Packit |
67cb25 |
should free the newly allocated matrix when it is no longer needed.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, conversion
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Conversion Between Sparse and Dense Matrices
|
|
Packit |
67cb25 |
============================================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The :type:`gsl_spmatrix` structure can be converted into the dense :type:`gsl_matrix`
|
|
Packit |
67cb25 |
format and vice versa with the following routines.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_d2sp (gsl_spmatrix * S, const gsl_matrix * A)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function converts the dense matrix :data:`A` into sparse triplet format
|
|
Packit |
67cb25 |
and stores the result in :data:`S`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_spmatrix_sp2d (gsl_matrix * A, const gsl_spmatrix * S)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function converts the sparse matrix :data:`S` into a dense matrix and
|
|
Packit |
67cb25 |
stores the result in :data:`A`. :data:`S` must be in triplet format.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, examples
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Examples
|
|
Packit |
67cb25 |
========
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The following example program builds a 5-by-4 sparse matrix
|
|
Packit |
67cb25 |
and prints it in triplet, compressed column, and compressed
|
|
Packit |
67cb25 |
row format. The matrix which is constructed is
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. only:: not texinfo
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. math::
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
\left(
|
|
Packit |
67cb25 |
\begin{array}{cccc}
|
|
Packit |
67cb25 |
0 & 0 & 3.1 & 4.6 \\
|
|
Packit |
67cb25 |
1 & 0 & 7.2 & 0 \\
|
|
Packit |
67cb25 |
0 & 0 & 0 & 0 \\
|
|
Packit |
67cb25 |
2.1 & 2.9 & 0 & 8.5 \\
|
|
Packit |
67cb25 |
4.1 & 0 & 0 & 0
|
|
Packit |
67cb25 |
\end{array}
|
|
Packit |
67cb25 |
\right)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. only:: texinfo
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
::
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
[ 0 0 3.1 4.6 ]
|
|
Packit |
67cb25 |
[ 1 0 7.2 0 ]
|
|
Packit |
67cb25 |
[ 0 0 0 0 ]
|
|
Packit |
67cb25 |
[ 2.1 2.9 0 8.5 ]
|
|
Packit |
67cb25 |
[ 4.1 0 0 0 ]
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The output of the program is::
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
printing all matrix elements:
|
|
Packit |
67cb25 |
A(0,0) = 0
|
|
Packit |
67cb25 |
A(0,1) = 0
|
|
Packit |
67cb25 |
A(0,2) = 3.1
|
|
Packit |
67cb25 |
A(0,3) = 4.6
|
|
Packit |
67cb25 |
A(1,0) = 1
|
|
Packit |
67cb25 |
.
|
|
Packit |
67cb25 |
.
|
|
Packit |
67cb25 |
.
|
|
Packit |
67cb25 |
A(4,0) = 4.1
|
|
Packit |
67cb25 |
A(4,1) = 0
|
|
Packit |
67cb25 |
A(4,2) = 0
|
|
Packit |
67cb25 |
A(4,3) = 0
|
|
Packit |
67cb25 |
matrix in triplet format (i,j,Aij):
|
|
Packit |
67cb25 |
(0, 2, 3.1)
|
|
Packit |
67cb25 |
(0, 3, 4.6)
|
|
Packit |
67cb25 |
(1, 0, 1.0)
|
|
Packit |
67cb25 |
(1, 2, 7.2)
|
|
Packit |
67cb25 |
(3, 0, 2.1)
|
|
Packit |
67cb25 |
(3, 1, 2.9)
|
|
Packit |
67cb25 |
(3, 3, 8.5)
|
|
Packit |
67cb25 |
(4, 0, 4.1)
|
|
Packit |
67cb25 |
matrix in compressed column format:
|
|
Packit |
67cb25 |
i = [ 1, 3, 4, 3, 0, 1, 0, 3, ]
|
|
Packit |
67cb25 |
p = [ 0, 3, 4, 6, 8, ]
|
|
Packit |
67cb25 |
d = [ 1, 2.1, 4.1, 2.9, 3.1, 7.2, 4.6, 8.5, ]
|
|
Packit |
67cb25 |
matrix in compressed row format:
|
|
Packit |
67cb25 |
i = [ 2, 3, 0, 2, 0, 1, 3, 0, ]
|
|
Packit |
67cb25 |
p = [ 0, 2, 4, 4, 7, 8, ]
|
|
Packit |
67cb25 |
d = [ 3.1, 4.6, 1, 7.2, 2.1, 2.9, 8.5, 4.1, ]
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
We see in the compressed column output, the data array stores
|
|
Packit |
67cb25 |
each column contiguously, the array :math:`i` stores
|
|
Packit |
67cb25 |
the row index of the corresponding data element, and the
|
|
Packit |
67cb25 |
array :math:`p` stores the index of the start of each column in the
|
|
Packit |
67cb25 |
data array. Similarly, for the compressed row output, the
|
|
Packit |
67cb25 |
data array stores each row contiguously, the array :math:`i`
|
|
Packit |
67cb25 |
stores the column index of the corresponding data element, and
|
|
Packit |
67cb25 |
the :math:`p` array stores the index of the start of each row
|
|
Packit |
67cb25 |
in the data array.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. include:: examples/spmatrix.c
|
|
Packit |
67cb25 |
:code:
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: sparse matrices, references
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
References and Further Reading
|
|
Packit |
67cb25 |
==============================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The algorithms used by these functions are described in the
|
|
Packit |
67cb25 |
following sources,
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
* Davis, T. A., Direct Methods for Sparse Linear Systems, SIAM, 2006.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
* CSparse software library, https://www.cise.ufl.edu/research/sparse/CSparse
|