
.. _libdoc_sparse:

=========================================
:mod:`sparse` -- Symbolic Sparse Matrices
=========================================

In the tutorial section, you can find a :ref:`sparse tutorial
<tutsparse>`.

The sparse submodule is not loaded when we import Theano. You must
import ``theano.sparse`` to enable it.

The sparse module provide the same functionalities as the tensor
module. The difference lies under the cover because sparse matrices
does not store data in a contiguous array. Note that there are no GPU
implementations for sparse matrices implemented in Theano. The sparse
module has been used in:

- NLP: Dense linear transformations of sparse vectors.
- Audio: Filterbank in Fourier domain.

Compressed Sparse Format
========================

This section tries to explain how information is store for the two
sparse formats of SciPy supported by Theano. There is more formats
that can be used with SciPy and some documentation about them may be
found `here
<http://deeplearning.net/software/theano/sandbox/sparse.html>`_.

.. Changes to this section should also result in changes to tutorial/sparse.txt.

Theano supports two *compressed sparse formats* ``csc`` and ``csr``,
respectively based on columns and rows. They have both the same
attributes: ``data``, ``indices``, ``indptr`` and ``shape``.

  * The ``data`` attribute is a one-dimentionnal ``ndarray`` which
    contains all the non-zero elements of the sparse matrix.

  * The ``indices`` and ``indptr`` attributes are used to store the
    position of the data in the sparse matrix.

  * The ``shape`` attribute is exactly the same as the ``shape``
    attribute of a dense (i.e. generic) matrix. It can be explicitly
    specified at the creation of a sparse matrix if it cannot be
    infered from the first three attributes.


CSC Matrix
----------

In the *Compressed Sparse Column* format, ``indices`` stands for index
inside the column vectors of the matrix and ``indptr`` tells where the
column starts in the ``data`` and in the ``indices``
attributes. ``indptr`` can be tought as giving the slice which must be
applied to the other attribute in order to get each column of the
matrix. In other words, ``slice(indptr[i], indptr[i+1])`` correspond
to the slice needed to find the i-th column of the matrix in the
``data`` and in the ``indices`` fields.

The following example builds a matrix and returns its columns. It
prints the i-th column, i.e. a list of indices in the column and their
corresponding value in the second list.

>>> data = np.asarray([7, 8, 9])
>>> indices = np.asarray([0, 1, 2])
>>> indptr = np.asarray([0, 2, 3, 3])
>>> m = sp.csc_matrix((data, indices, indptr), shape=(3, 3))
>>> print m.toarray()
[[7 0 0]
 [8 0 0]
 [0 9 0]]
>>> i = 0
>>> print m.indices[m.indptr[i]:m.indptr[i+1]], m.data[m.indptr[i]:m.indptr[i+1]]
[0, 1] [7, 8]
>>> i = 1
>>> print m.indices[m.indptr[i]:m.indptr[i+1]], m.data[m.indptr[i]:m.indptr[i+1]]
[2] [9]
>>> i = 2
>>> print m.indices[m.indptr[i]:m.indptr[i+1]], m.data[m.indptr[i]:m.indptr[i+1]]
[] []

CSR Matrix
----------

In the *Compressed Sparse Row* format, ``indices`` stands for index
inside the row vectors of the matrix and ``indptr`` tells where the
row starts in the ``data`` and in the ``indices``
attributes. ``indptr`` can be tought as giving the slice which must be
applied to the other attribute in order to get each row of the
matrix. In other words, ``slice(indptr[i], indptr[i+1])`` correspond
to the slice needed to find the i-th row of the matrix in the ``data``
and in the ``indices`` fields.

The following example builds a matrix and returns its rows. It prints
the i-th row, i.e. a list of indices in the row and their corresponding value
in the second list.

>>> data = np.asarray([7, 8, 9])
>>> indices = np.asarray([0, 1, 2])
>>> indptr = np.asarray([0, 2, 3, 3])
>>> m = sp.csr_matrix((data, indices, indptr), shape=(3, 3))
>>> print m.toarray()
[[7 8 0]
 [0 0 9]
 [0 0 0]]
>>> i = 0
>>> print m.indices[m.indptr[i]:m.indptr[i+1]], m.data[m.indptr[i]:m.indptr[i+1]]
[0, 1] [7, 8]
>>> i = 1
>>> print m.indices[m.indptr[i]:m.indptr[i+1]], m.data[m.indptr[i]:m.indptr[i+1]]
[2] [9]
>>> i = 2
>>> print m.indices[m.indptr[i]:m.indptr[i+1]], m.data[m.indptr[i]:m.indptr[i+1]]
[] []

List of Implemented Operations
==============================

- Moving from and to sparse
    - :class:`DenseFromSparse <theano.sparse.basic.DenseFromSparse>` and ``dense_from_sparse``.
      Both grad are implemented. Structured by default.
    - :class:`SparseFromDense <theano.sparse.basic.SparseFromDense>` and ``csr_from_dense``, ``csc_from_dense``.
      The grad implemented is structured.
    - Theano SparseVariable object have a method ``toarray()`` that is the same as ``dense_from_sparse``.

- Construction of Sparses and their Properties
    - :class:`CSM <theano.sparse.basic.CSM>` and ``CSC``, ``CSR`` to construct a matrix.
      The grad implemented is regular.
    - :class:`CSMProperties <theano.sparse.basic.CSMProperties>` and ``csm_properties(x)``
      to get the properties of a sparse matrix.
      The grad implemented is regular.
    - csm_indices(x), csm_indptr(x), csm_data(x) and csm_shape(x) or x.shape.
    - :func:`sp_ones_like <theano.sparse.basic.sp_ones_like>`.
      The grad implemented is regular.
    - :func:`sp_zeros_like <theano.sparse.basic.sp_zeros_like>`.
      The grad implemented is regular.
    - :class:`SquareDiagonal <theano.sparse.basic.SquareDiagonal>` and ``square_diagonal``.
      The grad implemented is regular.
    - :class:`ConstructSparseFromList <theano.sparse.basic.ConstructSparseFromList>` and ``construct_sparse_from_list``.
      The grad implemented is regular.

- Cast
    - :class:`Cast <theano.sparse.basic.Cast>` with ``bcast``, ``wcast``, ``icast``, ``lcast``,
      ``fcast``, ``dcast``, ``ccast``, and ``zcast``.
      The grad implemented is regular.

- Transpose
    - :class:`Transpose <theano.sparse.basic.Transpose>` and ``transpose``.
      The grad implemented is regular.

- Basic Arithmetic
    - :class:`Neg <theano.sparse.basic.Neg>`.
      The grad implemented is regular.
    - :func:`add <theano.sparse.basic.add>`.
      The grad implemented is regular.
    - :func:`sub <theano.sparse.basic.sub>`.
      The grad implemented is regular.
    - :func:`mul <theano.sparse.basic.mul>`.
      The grad implemented is regular.
    - :func:`col_scale <theano.sparse.basic.col_scale>` to multiply by a vector along the columns.
      The grad implemented is structured.
    - :func:`row_slace <theano.sparse.basic.row_scale>` to multiply by a vector along the rows.
      The grad implemented is structured.

- Monoid (Element-wise operation with only one sparse input).
    `They all have a structured grad.`

    - ``structured_sigmoid``
    - ``structured_exp``
    - ``structured_log``
    - ``structured_pow``
    - ``structured_minimum``
    - ``structured_maximum``
    - ``structured_add``
    - ``sin``
    - ``arcsin``
    - ``tan``
    - ``arctan``
    - ``sinh``
    - ``arcsinh``
    - ``tanh``
    - ``arctanh``
    - ``rad2deg``
    - ``deg2rad``
    - ``rint``
    - ``ceil``
    - ``floor``
    - ``trunc``
    - ``sgn``
    - ``log1p``
    - ``expm1``
    - ``sqr``
    - ``sqrt``

- Dot Product
    - :class:`Dot <theano.sparse.basic.Dot>` and
      :func:`dot <theano.sparse.basic.dot>`.

        - One of the inputs must be sparse, the other sparse or dense.
        - The grad implemented is regular.
        - No C code for perform and no C code for grad.
        - Return a dense for perform and a dense for grad.
    - :class:`StructuredDot <theano.sparse.basic.StructuredDot>`
      and :func:`structured_dot <theano.sparse.basic.structured_dot>`.

        - The first input is sparse, the second can be sparse or dense.
        - The grad implemented is structured.
        - C code for perform and grad.
        - Return a dense for perforn and a sparse for grad.
    - :class:`TrueDot <theano.sparse.basic.TrueDot>` and
      :func:`true_dot <theano.sparse.basic.true_dot>`.

        - The first input is sparse, the second can be sparse or dense.
        - The grad implemented is regular.
        - No C code for perform and no C code for grad.
        - Return a Sparse for perform and a Sparse for grad.
        - Flags trough constructor can change the output of
          grad to be dense if the second input of the op is dense.
    - :class:`SamplingDot <theano.sparse.basic.SamplingDot>` and
      ``sampling_dot``.

        - Both input must be dense.
        - The grad implemented is structured for `p`.
        - Sample of the dot and sample of the gradient.
        - C code for perform but not for grad.
        - Return sparse for perform and grad.
    - :class:`Usmm <theano.sparse.basic.Usmm>` and ``usmm``.

        - You *shouldn't* insert this op yourself!
           - There is optimization that transform a
             :class:`Dot <theano.sparse.basic.Dot>` to ``Usmm`` when possible.

        - This op is the equivalent of gemm for sparse dot.
        - There is no grad implemented for this op and this is not needed as
          you don't insert it yourself.
        - One of the inputs must be sparse, the other sparse or dense.
        - Return a dense for perform

- Slice Operations
    - sparse_variable[N, N], return a tensor scalar.
      There is no grad implemented for this operation.
    - sparse_variable[M:N, O:P], return a sparse matrix
      There is no grad implemented for this operation.
    - Sparse variable don't support [M, N:O] and [M:N, O] as we don't support sparse vector
      and returning a sparse matrix would break the numpy interface.
      Use [M:M+1, N:O] and [M:N, O:O+1] instead.
    - :class:`Diag <theano.sparse.basic.Diag>` and ``diag``.
      The grad implemented is regular.

- Concatenation
    - :class:`HStack <theano.sparse.basic.HStack>` and ``hstack``.
      The grad implemented is regular.
    - :class:`VStack <theano.sparse.basic.VStack>` and ``vstack``.
      The grad implemented is regular.

- Probability
    `There is no grad implemented for these operations.`

    - :class:`Poisson <theano.sparse.basic.Poisson>` and ``poisson``
    - :class:`Binomial <theano.sparse.basic.Binomial>` and ``csc_fbinomial``, ``csc_dbinomial``
      ``csr_fbinomial``, ``csr_dbinomial``
    - :class:`Multinomial <theano.sparse.basic.Multinomial>` and ``multinomial``

- Internal Representation
    `They all have a regular grad implemented.`

    - :class:`EnsureSortedIndices <theano.sparse.basic.EnsureSortedIndices>` and ``ensure_sorted_indices``
    - :class:`Remove0 <theano.sparse.basic.Remove0>` and ``remove0``
    - :func:`clean <theano.sparse.basic.clean>` to resort indices and remove zeros

- To help testing
    - :func:`theano.sparse.tests.test_basic.sparse_random_inputs`

===================================================================
:mod:`sparse` --  Sparse Op
===================================================================

.. module:: sparse
   :platform: Unix, Windows
   :synopsis: Sparse Op
.. moduleauthor:: LISA

.. automodule:: theano.sparse.basic
    :members:

.. autofunction:: theano.sparse.tests.test_basic.sparse_random_inputs
