{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Sparse Matrices in CSR Format"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In addition to `numpy`, we need a module to handle sparse matrics. [`scipy.sparse`](http://docs.scipy.org/doc/scipy/reference/sparse.html) has all of what we need."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 30,
      "metadata": {
        "collapsed": true
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import scipy.sparse\n",
        "\n",
        "from random import randrange"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 31,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([[ 0.  ,  0.  ,  0.23,  0.  ,  0.  ,  0.13,  0.91, -1.29,  0.  ],\n",
              "       [ 0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  , -1.24,  1.46],\n",
              "       [ 0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ],\n",
              "       [ 0.32,  0.  ,  0.  ,  0.  , -0.67,  0.  ,  0.  ,  0.  , -0.26],\n",
              "       [ 0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ],\n",
              "       [ 0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.61,  0.  ,  1.2 ],\n",
              "       [-0.01,  0.84,  0.  ,  0.  ,  0.23,  0.  ,  0.  ,  0.  ,  1.02],\n",
              "       [ 0.  , -1.09,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  , -1.43],\n",
              "       [ 0.  , -0.27,  0.  ,  0.  ,  0.  ,  0.  , -1.65,  1.39,  0.  ]])"
            ]
          },
          "execution_count": 31,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "n = 9\n",
        "A = np.zeros((n, n))\n",
        "\n",
        "for i in range((int(n**2*0.3))):\n",
        "    A[randrange(n), randrange(n)] = np.random.randn()\n",
        "A.round(2)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now convert this to a CSR matrix:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 32,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<9x9 sparse matrix of type '<class 'numpy.float64'>'\n",
              "\twith 20 stored elements in Compressed Sparse Row format>"
            ]
          },
          "execution_count": 32,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Acsr = scipy.sparse.csr_matrix(A)\n",
        "Acsr"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 33,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([ 0,  4,  6,  6,  9,  9, 11, 15, 17, 20], dtype=int32)"
            ]
          },
          "execution_count": 33,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Acsr.indptr"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 34,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([2, 5, 6, 7, 7, 8, 0, 4, 8, 6, 8, 0, 1, 4, 8, 1, 8, 1, 6, 7], dtype=int32)"
            ]
          },
          "execution_count": 34,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Acsr.indices"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 35,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([ 0.23,  0.13,  0.91, -1.29, -1.24,  1.46,  0.32, -0.67, -0.26,\n",
              "        0.61,  1.2 , -0.01,  0.84,  0.23,  1.02, -1.09, -1.43, -0.27,\n",
              "       -1.65,  1.39])"
            ]
          },
          "execution_count": 35,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Acsr.data.round(2)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "* How much memory does a dense matrix of double precision numbers of size $10^6 \\times 10^6$ occupy?"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "8000.0"
            ]
          },
          "execution_count": 3,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "\n",
        "# in gigabytes:\n",
        "10**6 * 10**6 * 8 / 1e9\n",
        "\n",
        "# i.e. 8 Terabytes"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "* How much memory does a sparse identity matrix of the same size occupy?"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "0.016"
            ]
          },
          "execution_count": 6,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "occupied = (\n",
        "    10**6 * 4 # (32-bit integers to store row indices)\n",
        "    + 10**6 * 4 # (one 32-bit integer per row to store column index)\n",
        "    + 10**6 * 8 # (one 64-bit double precision number per row to store value)\n",
        "    )\n",
        "# in gigabytes\n",
        "occupied / 1e9\n",
        "# I.e. 16 Megabytes"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": true
      },
      "outputs": [],
      "source": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.5.2+"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 1
}