2.5. SciPy中稀疏矩阵.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.5.1 介绍\n",
    "\n",
    "(密集) 矩阵是:\n",
    "- 数据对象\n",
    "- 存储二维值数组的数据结构\n",
    "\n",
    "重要特征:\n",
    "- 一次分配所有项目的内存\n",
    "    - 通常是一个连续组块，想一想Numpy数组\n",
    "- *快速*访问个项目(*)\n",
    "\n",
    "### 2.5.1.1 为什么有稀疏矩阵？\n",
    "\n",
    "- 内存，增长是n**2\n",
    "- 小例子（双精度矩阵）:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.text.Text at 0x105b08dd0>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAbEAAAEPCAYAAADMEPq0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xu81VWd//HXGxBSUxCdQAUVExtxalJS1MyOoyKmoZkX\nNJVRppmyRrvoeJlGoaxEMy9T4qM0QUvANPESKqScXxcvaGiSSqDGJIdAA4+Wt7h8fn+sdWB7zj6H\nA559O/v9fDz243z3Wt+1vmt/4ZzPXuu7vuuriMDMzKwW9ah0A8zMzDaVg5iZmdUsBzEzM6tZDmJm\nZlazHMTMzKxmOYiZmVnNKmkQk3SBpKclzZd0i6Q+kvpLmi1poaRZkvq12n+RpAWSRhakD891LJJ0\ndUF6H0nTc/ojknYuyBubj7FQ0mkF6UMkPZrLTJO0WSnPgZmZlU7JgpikXYDPAntHxAeBnsAY4Hxg\ndkTsDjyQ3yNpGHAiMAwYBVwrSbm6ScC4iBgKDJU0KqePA1bk9CuBibmu/sBFwL75dbGkvrnMROCK\nXOaVXIeZmdWgUvbEXgNWAVtI6gVsASwFRgNT8j5TgGPy9tHA1IhYFRGLgeeAEZK2B7aKiLl5v5sK\nyhTWdTtwSN4+HJgVEc0R0QzMBo7IQfFg4LYixzczsxpTsiAWESuBK4A/kYJXc0TMBgZExPK823Jg\nQN7eAVhSUMUSYMci6U05nfzzxXy81cCrkrbtoK7+uR1ri9RlZmY1ppTDie8HvgTsQgoq75V0SuE+\nkda8Kte6V15fy8ysm+lVwro/AjwUESsAJP0M2B9YJmlgRCzLQ4Uv5f2bgMEF5QeRelBNebt1ekuZ\nnYCleciyb0SskNQENBSUGQw8CKwE+knqkXtjg3IdbUhy0DMz20gRoQ3v1XVKeU1sAbCfpM3ztahD\ngWeAu4GxeZ+xwIy8fRcwRlJvSUOAocDciFgGvCZpRK7nVODOgjItdR1HmigCMAsYKamfpG2Aw4D7\nc89vDnB8keO3ERF+RXDxxRdXvA3V8vK58LnweUive+8N0nf9wlf5lawnFhG/k3QT8DiwFpgH/ADY\nCrhV0jhgMXBC3v8ZSbeSAt1q4MyIaDkrZwKTgc2BmRFxX06/AbhZ0iJgBWn2IxGxUtI3gMfyfhMi\nTfAAOA+YJumS3KYbSvDxzcy6rRdegJNPhqiC8apSDicSEZcBl7VKXknqlRXb/1vAt4qk/xb4YJH0\nt8lBsEjejcCNRdL/CIzYUNvNzKyt11+HT30KXnml0i1JvGKHbVBDQ0Olm1A1fC7W87lI6uk8RMC/\n/Rs89VTbvEOLdk1KT1EN/cEqJCl8bszM1vvud+GrX22bvssu8PjjsN12Iso8scNBrB0OYmZm6z34\nIIwcCWvWvDP9Pe+Bhx6CvfYCqfxBzMOJZmbWoT/9CU48sW0AA/jhD1MAqxQHMTMza9ebb8Kxx8Jf\n/tI27+yz4ZRT2qaXk4OYmZkVFQFnngm//W3bvI9/HC6/vPxtas1BzMzMipo0CSZPbps+aBBMnw6b\nVcGDrDyxox2e2GFm9ezXv4aDD4bVq9+Z3rs3/OpXsO++bct4YoeZmVXc0qVw/PFtAxjAtdcWD2CV\n4iBmZmbrvP02HHccLFvWNu9zn4NxVfYYYQcxMzNb5+yz4eGH26bvvz9cfXX527MhvibWDl8TM7N6\nc8MNaVmp1gYOTDMUd9ih4/KVuCbmINYOBzEzqydz58LHPgZ///s703v1gjlz4MADN1yHJ3aYmVnZ\nLV+ebmhuHcAgDSF2JoBVioOYmVkdW7UKTjgBmoo84/5f/xU+//myN2mjOIiZmdWxc8+FX/6ybfrw\n4elmZ5V1cHDj+ZpYO3xNzMy6ux//GE49tW36dtuliRw77bRx9XliRxVxEDOz7uyJJ+CAA+Ctt96Z\n3rMnzJ6dVuvYWJ7YYWZmJbdiRZrI0TqAAVx22aYFsEopaRCT9AFJTxS8XpV0lqT+kmZLWihplqR+\nBWUukLRI0gJJIwvSh0uan/OuLkjvI2l6Tn9E0s4FeWPzMRZKOq0gfYikR3OZaZKqYBlLM7PSW7MG\nTjoJFi9umzdmDHz5y2Vv0rtS0iAWEX+IiL0iYi9gOPAGcAdwPjA7InYHHsjvkTQMOBEYBowCrpXW\nXVacBIyLiKHAUEmjcvo4YEVOvxKYmOvqD1wE7JtfF0vqm8tMBK7IZV7JdZiZdXv//d9puLC1D30I\nrr+++idytFbO4cRDgeci4kVgNDAlp08BjsnbRwNTI2JVRCwGngNGSNoe2Coi5ub9biooU1jX7cAh\neftwYFZENEdEMzAbOCIHxYOB24oc38ys2/rpT2HixLbp22wDd9wBW25Z/ja9W+UMYmOAqXl7QEQs\nz9vLgQF5ewdgSUGZJcCORdKbcjr554sAEbEaeFXSth3U1R9ojoi1ReoyM+uWfv97OP30tukS3HIL\n7Lpr+dvUFcoSxCT1Bj4J/LR1Xp4CWK5pgJ5uaGZ1p7kZPvUpeP31tnnf/CaMGtU2vVb0KtNxjgB+\nGxEv5/fLJQ2MiGV5qPClnN4EDC4oN4jUg2rK263TW8rsBCyV1AvoGxErJDUBDQVlBgMPAiuBfpJ6\n5N7YoFxHG+PHj1+33dDQQENDQ7HdzMyq1tq18JnPwHPPtc079lg4//xNr7uxsZHGxsZNr6ALlOU+\nMUnTgHsjYkp+fxlpMsZESecD/SLi/Dyx4xbSRIwdgV8Au0VESHoUOAuYC/wcuCYi7pN0JvDBiPi8\npDHAMRExJk/seBzYGxDwW2DviGiWdCtwe0RMl3Qd8GREXNeqzb5PzMxq3sUXw9e/3jZ9jz3g0Udh\nq6267ljd8mZnSVsC/wcMiYi/5rT+wK2kHtRi4IQ8+QJJFwJnAKuBsyPi/pw+HJgMbA7MjIizcnof\n4GZgL2AFMCZPCkHS6cCFuSmXFATRIcA00vWxecApEbGqVbsdxMyspt11Fxx9dNv0rbdOq9Z/4ANd\ne7xuGcRqlYOYmdWyP/wB9t0XXnutbd6dd8Lo0V1/TK/YYWZm79pf/5omchQLYBddVJoAVinuibXD\nPTEzq0URcNxx8LOftc078sg0xNijRN0X98TMzOxdufTS4gFst93SqvWlCmCV4p5YO9wTM7Nac999\n8IlPpN5YoS23TDMR99yztMd3T8zMzDbJCy/AySe3DWAAN95Y+gBWKQ5iZmY17vXX00SOV15pm3fe\neXD88eVvU7l4OLEdHk40s1oQkVbkmDq1bd5hh8G996YHXZaDhxPNzGyjXHll8QC2yy4pvVwBrFLc\nE2uHe2JmVu3mzEm9rTVr3pm++ebw0EPw4Q+Xtz3uiZmZWaf86U9wwgltAxjAD39Y/gBWKQ5iZmY1\n5s030wr0f/lL27yzz07XyOqFg5iZWQ2JgDPPhN/+tm3exz8Ol19e/jZVkoOYmVkNmTQJJk9umz5o\nEEyfDpttVvYmVZQndrTDEzvMrNrccw8cc0zb62C9e8OvfpVWra8kT+wwM7OiHn64/Ykc115b+QBW\nKQ5iZmZVbsECOOqoNKGjtc99DsaNK3+bqoWHE9vh4UQzqwZNTXDAAWlKfWuHHgo//3kaTqwGHk40\nM7N1mpvhiCOKB7C9906PXKmWAFYpDmJmZlXorbfSJI7589vm7borzJwJW21V/nZVm5IHMUn9JN0m\n6VlJz0gaIam/pNmSFkqaJalfwf4XSFokaYGkkQXpwyXNz3lXF6T3kTQ9pz8iaeeCvLH5GAslnVaQ\nPkTSo7nMNEl1NinVzKrZmjVwyinw//5f27z3vQ/uvx8GDCh/u6pROXpiVwMzI2IP4EPAAuB8YHZE\n7A48kN8jaRhwIjAMGAVcK6llfHUSMC4ihgJDJY3K6eOAFTn9SmBirqs/cBGwb35dLKlvLjMRuCKX\neSXXYWZWcRFp1Y3bb2+bt+WWqQe2227lb1e1KmkQy0HjYxHxI4CIWB0RrwKjgSl5tynAMXn7aGBq\nRKyKiMXAc8AISdsDW0XE3LzfTQVlCuu6HTgkbx8OzIqI5ohoBmYDR+SgeDBwW5Hjm5lV1Le+Bd//\nftv0Xr3SNbDhw8vfpmpW6p7YEOBlSTdKmifph5K2BAZExPK8z3KgpWO8A7CkoPwSYMci6U05nfzz\nRUhBEnhV0rYd1NUfaI6ItUXqMjOrmB/9CL72teJ5kyfDyJHF8+pZrzLUvzfwxYh4TNJV5KHDFhER\nkso1l32jjjN+/Ph12w0NDTQ0NHRxc8zMknvugX//9+J53/lOdS7q29jYSGNjY0XbUOogtgRYEhGP\n5fe3ARcAyyQNjIhleajwpZzfBAwuKD8o19GUt1unt5TZCVgqqRfQNyJWSGoCGgrKDAYeBFYC/ST1\nyL2xQbmONgqDmJlZqXS0GsdXvgJf/Wr529QZrb/cT5gwoextKOlwYkQsA16UtHtOOhR4GrgbGJvT\nxgIz8vZdwBhJvSUNAYYCc3M9r+WZjQJOBe4sKNNS13GkiSIAs4CReXbkNsBhwP35DuY5wPFFjm9m\nVlYdrcZx8sn1tyr9xir5ih2S/hm4HugNPA+cDvQEbiX1oBYDJ+TJF0i6EDgDWA2cHRH35/ThwGRg\nc9Jsx7Nyeh/gZmAvYAUwJk8KQdLpwIW5KZdExJScPgSYRro+Ng84JSJWtWq3V+wws5KqpdU4OqMS\nK3Z42al2OIiZWSk1N8NBBxW/mXnvvaGxsfZuZvayU2ZmdcCrcXQdBzEzszLyahxdy0HMzKxMvBpH\n13MQMzMrE6/G0fUcxMzMysCrcZSGg5iZWYnV4moctcJT7NvhKfZm1hUefhgOOaT4zcxf+QpccUX5\n21Qqvk+sijiImdm7tWABfPSjsHJl27yTT4abb4Ye3Wg8zEGsijiImdm70dFqHIcdloYYa2k1js7w\nzc5mZt1AczMccUTxALb33mmKfXcLYJXiIGZm1oW8Gkd5OYiZmXURr8ZRfg5iZmZdwKtxVIaDmJlZ\nF/BqHJXhIGZm9i55NY7KcRAzM3sXvBpHZfk+sXb4PjEz25B6Wo2jM3yzcxVxEDOzjtTbahydUVVB\nTFL/TpRfGxHNXduk6uAgZmbtqcfVODqj2lbs+DPw2w28itzO906SFkt6StITkubmtP6SZktaKGmW\npH4F+18gaZGkBZJGFqQPlzQ/511dkN5H0vSc/oiknQvyxuZjLJR0WkH6EEmP5jLTJG224VNlZubV\nOKpNR0Hs2YgY0tELWNGJYwTQEBF7RcS+Oe18YHZE7A48kN8jaRhwIjAMGAVcK6klqk8CxkXEUGCo\npFE5fRywIqdfCUzMdfUHLgL2za+LJfXNZSYCV+Qyr+Q6zMw65NU4qk9HQWz/TpTfr5PHad29HA1M\nydtTgGPy9tHA1IhYFRGLgeeAEZK2B7aKiLl5v5sKyhTWdTtwSN4+HJgVEc15yHM2cEQOigcDtxU5\nvplZUV6Nozq1G8Qi4h3zbSRtKekjkv6hYJ+3OnGMAH4h6XFJn81pAyJied5eDrT80+8ALCkouwTY\nsUh6U04n/3wxt2c18KqkbTuoqz/QHBFri9RlZtaGV+OoXr3ay5A0GrgGWAl8Dfg+KeAMkXReREzu\n5DE+GhF/zsFvtqQFhZkREZLKNYNio44zfvz4ddsNDQ00NDR0cXPMrBZ4NY7iGhsbaWxsrGgb2g1i\nwCXASKAv0Ah8MCJekPQ+4EFgcmcOEBF/zj9flnQH6frUckkDI2JZHip8Ke/eBAwuKD6I1INqytut\n01vK7AQsldQL6BsRKyQ1AQ0FZQbndq8E+knqkXtjg3IdbRQGMTOrT16No32tv9xPmDCh7G3o6JrY\nmohYGBGPAS9ExAsAEfESsKozlUvaQtJWeXtLUlCcD9wFjM27jQVm5O27gDGSeksaAgwF5kbEMuA1\nSSPyNa1TgTsLyrTUdRxpogjALGCkpH6StgEOA+7P8+bnAMcXOb6Z2TpejaP6ddQT65ln+AmIgvvG\nBPTsZP0DgDvyBMNewE8iYpakx4FbJY0DFgMnAETEM5JuBZ4BVgNnFtysdSap97c5MDMi7svpNwA3\nS1pEmi05Jte1UtI3gMfyfhMK7mk7D5gm6RJgXq7DzGyd++6D449PEzpa+8pX4KtfLX+brK2ObnZe\nzPprSKLV9aQ8xb7b8s3OZvVrxgw44QRYVWTMqV5X4+iMqlqxo945iJnVp+nT0zBhsR5YPa/G0RmV\nCGIdzU7cu6OCETGv65tjZlY5U6bAGWfA2rVt8/bd16txVKOOhhPXAr+nnVU5IuLgErar4twTM6sv\n110Hn/988bwDD4Sf/xy23rq8bao1VdUTA75CmsH3BjAduCMi/lqWVpmZldFVV8GXv1w875BD4M47\n003NVn02eE1M0vtJ6xkeA/wf8M2IeLIMbaso98TM6sO3vgX//d/F8448Em67Dd7znvK2qVZV2yr2\nAETE86R7smYB+wAfKHWjzMxKLSLdxNxeAPv0p9NqHA5g1a2ja2LvJ91zdTTwJ9KQ4j2t11TsrtwT\nM+u+IuCcc+C73y2ef/LJaZJHr44uuFgbVTXFPk/smE9azeK1nBzke8Yiop1//u7BQcyse1q7Fr74\nRZg0qXj+GWfAD34APTu7pIOtU20TO77O+huc31uGtpiZldSaNfDZz8KNNxbP/8IX4JprfCNzLfHN\nzu1wT8yse1m1Ck47DaZNK55/zjlw2WWgsvYjupeqmtghqZ1lLzduHzOzSnv7bTjxxPYD2EUXOYDV\nqo6uib0AnEPbpzLD+mtj34iIYaVrXuW4J2bWPbz5ZpppeO+9xfO//W04//zytqm7qrZrYr8EPrmB\n8rO6sC1mZl3qb3+D0aNhzpzi+VdfDWedVd42WdfyNbF2uCdmVttefTXdrPyb37TNk9IyU+09K8w2\nTbX1xMzMatLKlTBqFDz2WNu8Hj3S7MTTTit/u6zrOYiZWbfy0kvpkSlPPdU2r1cvuOWW9LBL6x42\nGMQk9YyIIk/WMTOrLkuXwqGHwrPPts3r3Rt++tN0jcy6j87c0rdI0uWSuuUsRDPrHv7v/+Cgg4oH\nsM03h7vvdgDrjjoTxD4MLAKul/SopP+Q5KfqmFnVeP75FMCef75t3pZbpun1I0eWv11Wep1Zxf61\niPhBRBwAnAdcBCyTNEXSbhsqL6mnpCck3Z3f95c0W9JCSbMk9SvY9wJJiyQtkDSyIH24pPk57+qC\n9D6Spuf0RyTtXJA3Nh9joaTTCtKH5GC8SNI0SZt14jyZWZVasAA+9jH405/a5m29NcyeDR//ePnb\nZeWxwSAmqZekoyXNAK4CrgB2Be4GZnbiGGcDz7B+HcbzgdkRsTvwQH5PHq48ERgGjAKuldbdPz8J\nGBcRQ4Ghkkbl9HHAipx+JTAx19WfFGz3za+LJfXNZSYCV+Qyr+Q6zKwGPfVU6oH9+c9t8/r3hwcf\nhP33L3+7rHw6M5y4kPQ4lssi4sMR8d2IWBYRtwH3d1RQ0iDgE8D1rF/5YzQwJW9PIT1sk3yMqRGx\nKiIWA88BIyRtD2wVEXPzfjcVlCms63bgkLx9ODArIpojohmYDRyRg+LBwG1Fjm9mNeTxx+Hgg+Hl\nl9vmve990NgIw4eXvVlWZh3OTpTUE5gcEV8vlh8R/7mB+q8EzgUKr6ENiIjleXs5MCBv7wA8UrDf\nEmBHYFXebtGU08k/X8xtWS3pVUnb5rqWFKmrP9AcEWuL1GVmNeKhh+CII+C119rm7bgjPPAAfMCP\n760LHQaxiFgj6ZOkx7JsFElHAS9FxBOSGtqpPySVa1mMjT7O+PHj1203NDTQ0NDQhc0xs00xZw58\n8pPw+utt83bZJQWwXXcte7PqUmNjI42NjRVtQ2dudv61pO+Rnuy87r9NRMzbQLkDgNGSPgG8B9ha\n0s3AckkDI2JZHip8Ke/fBAwuKD+I1INqytut01vK7AQsldQL6BsRKyQ1AQ0FZQYDDwIrgX6SeuTe\n2KBcR1GFQczMKu++++BTn4K33mqbt9tu6RrY4MFt86w0Wn+5nzBhQtnb0JlrYnsBe5J6Y1cUvDoU\nERdGxOCIGAKMAR6MiFOBu4CxebexpCdHk9PHSOotaQgwFJgbEcuA1ySNyNe0TgXuLCjTUtdxpIki\nkBYmHimpn6RtgMOA+/NiiHOAlvv1C49vZlVsxox0n1exADZsGPzylw5g9WiDPbGIaOiiY7UM510K\n3CppHLAYOCEf5xlJt5JmMq4GzixYgfdMYDKwOTAzIu7L6TcAN0taBKwgBUsiYqWkbwAtK6dNyBM8\nIN0mME3SJcC8XIeZVbHp0+Ezn0lPZm7twx+GWbPgH/6h/O2yytvgKvb5Pq6LgYNyUiPw9Yh4tbRN\nqyyvYm9WHaZMgTPOgLVr2+btu28aYtxmm/K3y9qqqic7F/gR8BppCO4E4K/AjaVslJkZpMel/Ou/\nFg9gBx6YbmR2AKtvnemJ/S4i/nlDad2Ne2JmlXXVVfDlLxfPO+QQuPPOtKSUVY9q7Ym9KeljLW8k\nHQi8UbommVm9+9a32g9gRx4J99zjAGZJZ6bYfw64qWDZpldYPyPQzKzLRMD//A9885vF8z/96fQ8\nsN69y9suq14bHE5ct2NeuT4iitwj3/14ONGsvCLgnHPgu98tnn/yyWmSRy8/yrdqVWI4sTMPxdwG\nOA3YBeiV1+SNiDirtE0zs3qxZg3853/CpEnF8884A37wA+jZs7ztsurXme80M4GHgaeAtaSFfN1F\nMbMu0dwMJ52UpsoX84UvwDXXQI/OXMG3utOZ2YnzImLvMrWnang40az0FiyAo4+GhQuL559zDlx2\nGaisA1S2qap1duItkv5d0vb5gZb98/O6zMw22cyZMGJE+wHsooscwGzDOjOc+BZwOfDfpOFESMOJ\nXifazDZaRApOF1yQtluTUv4555S/bVZ7OjOc+Edgn4j4S3maVB08nGjW9d54A/7t32Dq1OL5W2+d\nptAfeWR522VdoypnJwKLgDdL3RAz695efBGOOQbmtfMQp6FD0yoce+xR3nZZbetMEHsDeFLSHODt\nnOYp9mbWab/5DRx7LLz0UvH8UaNS76xfv/K2y2pfZ4LYjPxqGVvzFHsz67Trr4czz4RVq4rnn3su\nfPvbvgfMNk2nVuyQtAWwU0QsKH2TqoOviZm9O6tWpfUPv//94vl9+qQAd8op5W2XlU5VTrGXNBp4\nArgvv99L0l2lbpiZ1a6//AUOP7z9ALbDDvCrXzmA2bvXmfvExgMjSAv/EhFP4On1ZtaO+fNhn31g\nzpzi+fvvD48/nvYxe7c6E8RWRURzq7Qij6gzs3r3s5+lILV4cfH8M85IwW377cvaLOvGOhPEnpb0\nGdLiv0Ml/S/wUInbZWY1ZO1aGD8+PSrl9dfb5vfsCVdfna6B9elT9uZZN9aZIPafwJ6k6fVTgdeA\nL22okKT3SHpU0pOSnpH07ZzeX9JsSQslzZLUr6DMBZIWSVogaWRB+nBJ83Pe1QXpfSRNz+mPSNq5\nIG9sPsZCSacVpA/J7VokaZqkzTpxDsysHX/9Kxx3HEyYUDx/m23g/vvhrLO8hJR1vU4/T2yTKpe2\niIg3JPUCfg2cA4wG/hIRl0k6D9gmIs6XNAy4BdgH2BH4BTA0IkLSXOCLETFX0kzgmoi4T9KZwD9F\nxJmSTgQ+FRFj8tqOjwHDc1N+C+wdEa9KuhW4LSJulTQJ+F1EXFek7Z6daLYBL7yQFvD9/e+L5++5\nZ7qB+f3vL2+7rDKqdXbiPpLukPRE7g3Nl/RUZyqPiDfyZm+gJ2lyyGhgSk6fAhyTt48GpkbEqohY\nDDwHjJC0PbBVRMzN+91UUKawrtuBQ/L24cCsiGjO1/NmA0coPQztYOC2Isc3s43w4INpckZ7AeyY\nY+Dhhx3ArLQ6c7PzT0g9qN+zkRM6JPUA5gHvByZFxNOSBkTE8rzLcmBA3t4BeKSg+BJSj2xV3m7R\nlNPJP18EiIjVkl6VtG2ua0mRuvoDzRGxtkhdZtYJEfC976V7wNasKb7PRRfBxRf7GWBWep0JYi9H\nxCbdF5aDxYcl9QXul3Rwq/yQVK4xu40+zvjx49dtNzQ00NDQ0IXNMas9b7+dHlJ5ww3F87fYAm66\nKU3wsO6vsbGRxsbGirahM0FsgqQbSNeo/p7TIiJ+1tmD5GtRPyddo1ouaWBELMtDhS2rqTUBgwuK\nDSL1oJryduv0ljI7AUvzdbe+EbFCUhPQUFBmMPAgsBLoJ6lHDrCDch1FFQYxs3q3bFla//Dhh4vn\n77JLuv71oQ+VtVlWQa2/3E9ob3ZPCXWmsz8W+GdgFHBUfn1yQ4Ukbdcy81DS5sBhpJU/7sp1ttQ9\nI2/fBYyR1FvSEGAoMDcilgGvSRqRr2mdCtxZUKalruOAB/L2LGCkpH6StsnHvj/P1JgDHF/k+GbW\njscfh498pP0A1tAAjz3mAGbl15nnif0B+MeNnaon6YOkiRM98uvmiLg8zxy8ldSDWgyc0HIztaQL\ngTOA1cDZEXF/Th8OTAY2B2a2rKAvqQ9wM7AXsAIYkyeFIOl04MLcnEsiYkpOHwJMI10fmwecEhFt\nlib17ESz5Cc/Sc8Ae+ut4vlf/CJ897uwmW9WqXuVmJ3YmSB2I/CdiHi6PE2qDg5iVu/WrElPX778\n8uL5m22W1kb87GfL2y6rXtUaxBaQZhf+kXc+T6xbDxw4iFk9a26Gk0+Ge+8tnv++98Htt8OBB5a3\nXVbdqvXJzqNK3gozqxp/+AOMHg0LFxbP33tvuOMO2Gmn8rbLrJiSrthRy9wTs3o0cyacdBK89lrx\n/JNOSusfbrFFedtltaEqV+wws+4vAiZOhKOOKh7AJLj00jTJwwHMqklnhhPNrBt74400+3Dq1OL5\nW28Nt9wCRx5Z3naZdYaDmFkde/HFtMbhvHnF83ffPd3A/I//WN52mXWWhxPN6tRvfpMW8G0vgI0a\nBY8+6gBm1c1BzKzORKTJGQcfDMuXF9/n3HPhnnugX7/i+WbVwsOJZnXkpZfgzDPTPV7FvOc9KcB9\n5jPlbZfZpnIQM6sDEXDrrWkF+hUriu+z444wY0ZaI9GsVng40aybe+klOP54GDOm/QC2//5pAV8H\nMKs1DmLL1Qx8AAAQ10lEQVRm3VQETJ8Ow4a1P3wIcPrpMGcObL99+dpm1lU8nGjWDW3o2hfAttum\nBXxPOCHdzGxWixzEzLqRzlz7gvRwy2uvhQEDytc2s1JwEDPrJtz7snrkIGZW49z7snrmIGZWw9z7\nsnrnIGZWg9z7MkscxMxqjHtfZuuV9D4xSYMlzZH0tKTfSzorp/eXNFvSQkmzJPUrKHOBpEWSFkga\nWZA+XNL8nHd1QXofSdNz+iOSdi7IG5uPsVDSaQXpQyQ9mstMk7RZKc+DWVfo7H1fxx4LTz8NJ57o\nAGbdX6lvdl4FfDki9gT2A74gaQ/gfGB2ROwOPJDfI2kYcCIwDBgFXCut+zWcBIyLiKHAUEmjcvo4\nYEVOvxKYmOvqD1wE7JtfF0vqm8tMBK7IZV7JdZhVrc6surHttjBtGtx2m4cPrX6UNIhFxLKIeDJv\n/w14FtgRGA1MybtNAY7J20cDUyNiVUQsBp4DRkjaHtgqIubm/W4qKFNY1+3AIXn7cGBWRDRHRDMw\nGzgiB8WDgduKHN+sqrj3Zdaxsi07JWkXYC/gUWBARLQ8BGI50PK9cQdgSUGxJaSg1zq9KaeTf74I\nEBGrgVclbdtBXf2B5ohYW6Qus6rh3pfZhpVlYoek95J6SWdHxF9V8FUxIkJSlKMdwEYdZ/z48eu2\nGxoaaGho6OLmmLXlmYdWKxobG2lsbKxoG0oexPKkiduBmyNiRk5eLmlgRCzLQ4Uv5fQmYHBB8UGk\nHlRT3m6d3lJmJ2CppF5A34hYIakJaCgoMxh4EFgJ9JPUI/fGBuU62igMYmbl4JmHVktaf7mfMGFC\n2dtQ6tmJAm4AnomIqwqy7gLG5u2xwIyC9DGSeksaAgwF5kbEMuA1SSNynacCdxap6zjSRBGAWcBI\nSf0kbQMcBtwfEQHMAY4vcnyzivC1L7NNo/Q3vUSVSwcCvwSeYv1Q3gXAXOBWUg9qMXBCnnyBpAuB\nM4DVpOHH+3P6cGAysDkwMyJapuv3AW4mXW9bAYzJk0KQdDpwYT7uJRExJacPAaaRro/NA06JiFWt\n2h6lPDdmLdz7su5CEhFR1v+hJQ1itcxBzErN176su6lEEPOKHWYV4N6XWddwEDMrI/e+zLqWg5hZ\nmbj3Zdb1HMTMSsy9L7PSKduKHWb16I9/9KobZqXknphZCSxdCpdcAtdfD6tWtb+fe19m746DmFkX\nevlluPTSFJjeeqv9/Xzty6xrOIiZdYHmZrjiCrjqKvjb3zre170vs67jIGb2Lvztb3DNNXD55SmQ\ndWS77eB733Pvy6wrOYiZbYK33oLrroNvfztNne/I1lvDV78KX/pS2jazruMgZrYRVq2CH/0IvvEN\naCr67IP1Nt8czjoLzj03XQMzs67nIGbWCWvWwC23wPjx8MILHe/buzd87nNwwQUwcGBZmmdWtxzE\nzDqwdi387Gdw0UXw7LMd79uzJ5x+OvzP/8BOO5WnfWb1zkHMrIgIuPde+NrX4IknOt5XgpNPTr20\n3XYrS/PMLHMQM2tlzpwUvB56aMP7HnssTJgA//RPpW+XmbXlIGaWPfJICl4PPLDhfUeNSityDB9e\n+naZWfscxKzu/e53KXjdc8+G9z3ooBS8Pvax0rfLzDbMQczq1oIFcPHFaYX5DdlnH/jmN+HQQ32j\nslk1cRCzuvPHP8LXvw433ZRmH3bkgx9M94SNHu3gZVaNSvooFkk/krRc0vyCtP6SZktaKGmWpH4F\neRdIWiRpgaSRBenDJc3PeVcXpPeRND2nPyJp54K8sfkYCyWdVpA+RNKjucw0SZuV8hxY9Vi6ND2U\n8gMfgMmTOw5gQ4fC1Knw5JNw9NEOYGbVqtTPE7sRGNUq7XxgdkTsDjyQ3yNpGHAiMCyXuVZa96dj\nEjAuIoYCQyW11DkOWJHTrwQm5rr6AxcB++bXxZL65jITgStymVdyHdaNvfwynHMOvP/9MGlSx49G\n2WknuOEGeOaZ9AywHn7inllVK+mvaET8ihQoCo0GpuTtKcAxeftoYGpErIqIxcBzwAhJ2wNbRcTc\nvN9NBWUK67odOCRvHw7MiojmiGgGZgNH5KB4MHBbkeNbN9PcnG483nXXtMJ8R49GGTgwLc67cCGc\ncQb08kC7WU2oxK/qgIhYnreXAy0PpNgBeKRgvyXAjsCqvN2iKaeTf74IEBGrJb0qadtc15IidfUH\nmiNibZG6rJvYmJXlt90Wzj8/DTNusUV52mdmXaei3zcjIiRFuQ63sQXGjx+/bruhoYGGhoYubI51\ntVdfTYvzXnqpV5Y3K4fGxkYaGxsr2oZKBLHlkgZGxLI8VNjy56YJGFyw3yBSD6opb7dObymzE7BU\nUi+gb0SskNQENBSUGQw8CKwE+knqkXtjg3IdRRUGMatOq1fD7NkwZQrceWfHQ4bgleXNulLrL/cT\nJkwoexsqcdn6LmBs3h4LzChIHyOpt6QhwFBgbkQsA16TNCJf0zoVuLNIXceRJooAzAJGSuonaRvg\nMOD+iAhgDnB8keNbDZk/PwWiwYPhE5+A6dM7DmC9e6fg9cILqafmAGbWPSj9XS9R5dJU4OPAdqTr\nXxeRAtCtpB7UYuCEPPkCSRcCZwCrgbMj4v6cPhyYDGwOzIyIs3J6H+BmYC9gBTAmTwpB0unAhbkp\nl0TElJw+BJhGuj42DzglItrMV5MUpTw3tvFefjk9DmXKlA0vytuiZ880UeNrX/PK8malJomIKOsN\nKSUNYrXMQaw6vP02/PznKXDNnJmGDzvDK8ublV8lgpgnElvViYDHHkuBa9o0WLmy82W32y4Fr//4\nDxg2rHRtNLPq4CBmVWPJEvjxj1PwWrCg8+U22wyOOgrGjoUjjkjXv8ysPjiIWUW9/jrccUcKXA88\nkHphnbXPPilwjRnjiRpm9cpBzMpu7Vr45S/TArw//Wm6ObmzdtwRTjklBa899ihdG82sNjiIWdk8\n91wKXDffDIsXd77c5punJyiPHQv/8i9pxqGZGTiIWYk1N6fe1pQp8JvfbFzZgw5Kgeu447yqhpkV\n5yBmXa5wFY0ZM9I0+c7addcUuE49FYYMKV0bzax7cBCzLjN/fhou/PGPYdmyzpfbems48UQ47TT4\n6Ef97C4z6zwHMXtXNmUVDUjP6Ro5MvW6jj46XfcyM9tYDmK2Ud5+G+bNg4cfhjlz4L77Or+KBsCe\ne6bA9ZnPwA47lK6dZlYfHMSsQ0uWpIDV8po3D/7+942ro2UVjbFjYa+9PFxoZl3HQczWKexltbya\n2n1QTce8ioaZlYODWB3ril5Wa15Fw8zKyUGsTnRlL6s1r6JhZpXiINZNlaKX1WLgQNh///Q64ADY\nbz+vomFmleEg1g0U9rIeeST9XLKka+ru1StNxthvv/WBa+edPTnDzKqDg1gNKlcva//9Yfhw38Nl\nZtXLQazKrF2b1htcseKdr2XL4PHH3csyMytUt0FM0ijgKqAncH1ETOzqY7z5ZgpAK1e2DUrtvV55\nJQWyUnAvy8y6G8XGPIWwm5DUE/gDcCjQBDwGnBQRzxbsEy3npr3e0YZeb75ZiU+XdGUvq7GxkYaG\nhi5vYy3yuVjP5yLxeVhPEhFR1rGceu2J7Qs8FxGLASRNA44Gni3c6QMfKH3vqKuUspflX9L1fC7W\n87lIfB4qq16D2I7AiwXvlwAjWu+0cGHZ2rNRfC3LzCyp1yBW1WOoW22VVrvo3z/9bHntsksKXL6W\nZWaW1Os1sf2A8RExKr+/AFhbOLlDUv2dGDOzd6nc18TqNYj1Ik3sOARYCsyl1cQOMzOrfnU5nBgR\nqyV9EbifNMX+BgcwM7PaU5c9MTMz6x56VLoB1UbSKEkLJC2SdF6l27OpJA2WNEfS05J+L+msnN5f\n0mxJCyXNktSvoMwF+XMvkDSyIH24pPk57+qC9D6Spuf0RyTtXJA3Nh9joaTTyvW5OyKpp6QnJN2d\n39fluZDUT9Jtkp6V9IykEXV8Li7IvyPzJd2S214X50LSjyQtlzS/IK2in13SEEmP5jLTJG22wQ8S\nEX7lF2lo8TlgF2Az4Elgj0q3axM/y0Dgw3n7vaRrgHsAlwH/ldPPAy7N28Py590sf/7nWN9Tnwvs\nm7dnAqPy9pnAtXn7RGBa3u4PPA/0y6/ngX5VcE6+AvwEuCu/r8tzAUwBzsjbvYC+9Xgu8ud5AeiT\n308HxtbLuQA+BuwFzC9Iq9Rn75vzbgVOyNuTgM9t8HNU8pep2l7A/sB9Be/PB86vdLu66LPNIK1Q\nsgAYkNMGAgvy9gXAeQX73wfsB2wPPFuQPga4rmCfEXm7F/By3j4JmFRQ5jpgTIU//yDgF8DBwN05\nre7OBSlgvVAkvR7PRX/Sl7ttcjvvBg6rp3NBCkiFQaxinx0Q8DLQI6fvR8Hf4/ZeHk58p2I3Qe9Y\nobZ0GUm7kL5xPUr6D7o8Zy0HBuTtHUift0XLZ2+d3sT6c7LufEXEauBVSdt2UFclXQmcCxSuvVKP\n52II8LKkGyXNk/RDSVtSh+ciIlYCVwB/Is1Sbo6I2dThuShQyc/en/RvsLZIXe1yEHunbjfLRdJ7\ngduBsyPir4V5kb7udLvP3Jqko4CXIuIJ0re9NurlXJC+Ee9NGubZG3idNOKwTr2cC0nvB75E6o3s\nALxX0imF+9TLuSimzJ99k4/jIPZOTcDggveDeec3hpqSL4reDtwcETNy8nJJA3P+9sBLOb31Zx9E\n+uxNebt1ekuZnXJdvUjj2iuK1FXp83gAMFrSH4GpwL9Iupn6PBdLgCUR8Vh+fxspqC2rw3PxEeCh\niFiRewo/I11SqMdz0aJSvxNNwEqgn6QeBXU1bbDFlRqPrsYX6Vvq86RvZr2p7YkdAm4CrmyVfhl5\nbJv0Dbz1hdvepCGn51l/4fZR0tqSou2F20l5ewzvvHD7Aumi7TYt25U+J7ltH2f9NbG6PBfAL4Hd\n8/b4fB7q7lwA/wz8Htg8f4YpwBfq6VzQ9ppYRT87aWLHiXn7OjyxY5P+UY8gXex9Drig0u15F5/j\nQNL1nyeBJ/JrVP4P9AtgITCr8BcHuDB/7gXA4QXpw4H5Oe+agvQ++T/dIuARYJeCvNNz+iJgbKXP\nR0G7Ps762Yl1eS5If7wfA35H6n30reNz8V/A0/lzTCHNvquLc0EalVgK/J107er0Sn92UoB8NKdP\nBzbb0Ofwzc5mZlazfE3MzMxqloOYmZnVLAcxMzOrWQ5iZmZWsxzEzMysZjmImZlZzXIQM6syeT3D\nPSrdDrNa4PvEzMysZrknZlYhkraU9HNJT+aHCh6f0xvzgwY/qfQQzyck/UHSCzl/eN7ncUn3tax1\n16ruyZKulvQbSc9L+nS5P59ZOfSqdAPM6tgooCkijgSQtHVOD9Ii4neTnnGFpOlAY15I9X+BT0bE\nCkknAt8ExrWqO4CBEfHRPDR5F2kxaLNuxUHMrHKeAr4j6VLgnoj4dbGdJP0X8EZETJL0T8CewC8k\nQXoa+dJ26p8BEBHPShrQzj5mNc1BzKxCImKRpL2AI4FLJD0QEd8o3EfSocCngYNakoCnI+KAThzi\n74VVdUWbzaqNr4mZVUh+XtNbEfET4Dukp28X5u8MfB84ISLezsl/AP5B0n55n80kDStjs82qinti\nZpXzQeBySWuBVcDnCvIEjCU9GmNGHjpsioijJB0HXCOpL+l3+ErgmSL1RzvbZt2Gp9ibmVnN8nCi\nmZnVLAcxMzOrWQ5iZmZWsxzEzMysZjmImZlZzXIQMzOzmuUgZmZmNctBzMzMatb/BxEsuh7sM/C3\nAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x105a27610>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "x = np.linspace(0, 1e6, 10)\n",
    "plt.plot(x, 8.0 * (x**2) / 1e6, lw=5)   \n",
    "plt.xlabel('size n')\n",
    "plt.ylabel('memory [MB]')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5.1.2 稀疏矩阵 vs. 稀疏矩阵存储方案\n",
    "\n",
    "- 稀疏矩阵是一个矩阵，巨大多数是空的\n",
    "- 存储所有的0是浪费 -> 只存储非0项目\n",
    "- 想一下**压缩**\n",
    "- 有利: 巨大的内存节省\n",
    "- 不利: 依赖实际的存储方案, (\\*) 通常并不能满足\n",
    "\n",
    "### 2.5.1.3 典型应用\n",
    "- 偏微分方程（PDES）的解\n",
    "    - 有限元素法\n",
    "    - 机械工程、电子、物理...\n",
    "- 图论\n",
    "    - （i，j）不是0表示节点i与节点j是联接的\n",
    "- ...\n",
    "\n",
    "### 2.5.1.4 先决条件\n",
    "\n",
    "最新版本的\n",
    "- `numpy`\n",
    "- `scipy`\n",
    "- `matplotlib` (可选)\n",
    "- `ipython` (那些增强很方便)\n",
    "\n",
    "### 2.5.1.5 稀疏结构可视化\n",
    "\n",
    "- matplotlib中的`spy()`\n",
    "- 样例绘图:\n",
    "\n",
    "![](http://scipy-lectures.github.io/_images/graph.png)\n",
    "![](http://scipy-lectures.github.io/_images/graph_g.png)\n",
    "![](http://scipy-lectures.github.io/_images/graph_rcm.png)\n",
    "\n",
    "## 2.5.2 存储机制\n",
    "\n",
    "- scipy.sparse中有七类稀疏矩阵:\n",
    "    1. csc_matrix: 压缩列格式\n",
    "    2. csr_matrix: 压缩行格式\n",
    "    3. bsr_matrix: 块压缩行格式\n",
    "    4. lil_matrix: 列表的列表格式\n",
    "    5. dok_matrix: 值的字典格式\n",
    "    6. coo_matrix: 座标格式 (即 IJV, 三维格式)\n",
    "    7. dia_matrix: 对角线格式\n",
    "- 每一个类型适用于一些任务\n",
    "- 许多都利用了由Nathan Bell提供的稀疏工具 C ++ 模块\n",
    "- 假设导入了下列模块:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import scipy.sparse as sparse\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 给Numpy用户的**warning**:\n",
    "    - 使用'\\*'的乘是*矩阵相乘* (点积)\n",
    "    - 并不是Numpy的一部分!\n",
    "        - 向Numpy函数传递一个稀疏矩阵希望一个ndarray/矩阵是没用的\n",
    "\n",
    "### 2.5.2.1 通用方法\n",
    "\n",
    "- 所有scipy.sparse类都是spmatrix的子类\n",
    "    - 算术操作的默认实现\n",
    "        - 通常转化为CSR\n",
    "        - 为了效率而子类覆盖\n",
    "    - 形状、数据类型设置/获取\n",
    "    - 非0索引\n",
    "    - 格式转化、与Numpy交互(toarray(), todense())\n",
    "    - ...\n",
    "\n",
    "- 属性:\n",
    "    - mtx.A - 与mtx.toarray()相同\n",
    "    - mtx.T - 转置 (与mtx.transpose()相同)\n",
    "    - mtx.H - Hermitian (列举) 转置\n",
    "    - mtx.real - 复矩阵的真部\n",
    "    - mtx.imag - 复矩阵的虚部\n",
    "    - mtx.size - 非零数 (与self.getnnz()相同)\n",
    "    - mtx.shape - 行数和列数 (元组)\n",
    "\n",
    "- 数据通常储存在Numpy数组中\n",
    "\n",
    "### 2.5.2.2 稀疏矩阵类\n",
    "#### 2.5.2.2.1 对角线格式 (DIA)\n",
    "- 非常简单的格式\n",
    "- 形状 (n_diag, length) 的密集Numpy数组的对角线\n",
    "    - 固定长度 -> 当离主对角线比较远时会浪费空间\n",
    "    - \\_data_matrix的子类 (带数据属性的稀疏矩阵类)\n",
    "- 每个对角线的偏移\n",
    "    - 0 是主对角线\n",
    "    - 负偏移 = 下面\n",
    "    - 正偏移 = 上面\n",
    "- 快速矩阵 * 向量 (sparsetools)\n",
    "- 快速方便的关于项目的操作\n",
    "    - 直接操作数据数组 (快速的NumPy机件)\n",
    "- 构建器接受 :\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空矩阵)\n",
    "    - (数据, 偏移) 元组\n",
    "- 没有切片、没有单个项目访问\n",
    "- 用法 :\n",
    "    - 非常专业\n",
    "    - 通过有限微分解偏微分方程\n",
    "    - 有一个迭代求解器\n",
    "##### 2.5.2.2.1.1 示例\n",
    "- 创建一些DIA矩阵 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 2, 3, 4],\n",
       "       [1, 2, 3, 4],\n",
       "       [1, 2, 3, 4]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = np.array([[1, 2, 3, 4]]).repeat(3, axis=0)\n",
    "data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<4x4 sparse matrix of type '<type 'numpy.int64'>'\n",
       "\twith 9 stored elements (3 diagonals) in DIAgonal format>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "offsets = np.array([0, -1, 2])\n",
    "mtx = sparse.dia_matrix((data, offsets), shape=(4, 4))\n",
    "mtx "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 3, 0],\n",
       "        [1, 2, 0, 4],\n",
       "        [0, 2, 3, 0],\n",
       "        [0, 0, 3, 4]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1,  2,  3,  4],\n",
       "       [ 5,  6,  7,  8],\n",
       "       [ 9, 10, 11, 12]])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = np.arange(12).reshape((3, 4)) + 1\n",
    "data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1,  2,  3,  4],\n",
       "       [ 5,  6,  7,  8],\n",
       "       [ 9, 10, 11, 12]])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.dia_matrix((data, offsets), shape=(4, 4))\n",
    "mtx.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0, -1,  2], dtype=int32)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.offsets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (0, 0)\t1\n",
      "  (1, 1)\t2\n",
      "  (2, 2)\t3\n",
      "  (3, 3)\t4\n",
      "  (1, 0)\t5\n",
      "  (2, 1)\t6\n",
      "  (3, 2)\t7\n",
      "  (0, 2)\t11\n",
      "  (1, 3)\t12\n"
     ]
    }
   ],
   "source": [
    "print mtx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 1,  0, 11,  0],\n",
       "        [ 5,  2,  0, 12],\n",
       "        [ 0,  6,  3,  0],\n",
       "        [ 0,  0,  7,  4]])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 机制的解释 :\n",
    "\n",
    "偏移: 行\n",
    "\n",
    "     2:  9\n",
    "     1:  --10------\n",
    "     0:  1  . 11  .\n",
    "    -1:  5  2  . 12\n",
    "    -2:  .  6  3  .\n",
    "    -3:  .  .  7  4\n",
    "         ---------8\n",
    "         \n",
    "- 矩阵-向量相乘"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 1.,  1.,  1.,  1.])"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vec = np.ones((4, ))\n",
    "vec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 12.,  19.,   9.,  11.])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx * vec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  1.,   0.,  11.,   0.],\n",
       "       [  5.,   2.,   0.,  12.],\n",
       "       [  0.,   6.,   3.,   0.],\n",
       "       [  0.,   0.,   7.,   4.]])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.toarray() * vec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.2 列表的列表格式 (LIL)\n",
    "- 基于行的联接列表\n",
    "    - 每一行是一个Python列表（排序的）非零元素的列索引\n",
    "    - 行存储在Numpy数组中 (dtype=np.object)\n",
    "    - 非零值也近似存储\n",
    "- 高效增量构建稀疏矩阵\n",
    "- 构建器接受 :\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建一个空矩阵)\n",
    "- 灵活切片、高效改变稀疏结构\n",
    "- 由于是基于行的，算术和行切片慢\n",
    "- 用途 :\n",
    "    - 当稀疏模式并不是已知的逻辑或改变\n",
    "    - 例子：从一个文本文件读取稀疏矩阵\n",
    "##### 2.5.2.2.2.1 示例\n",
    "- 创建一个空的LIL矩阵 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "mtx = sparse.lil_matrix((4, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 准备随机数据:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.,  0.,  0.],\n",
       "       [ 1.,  0.,  0.]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from numpy.random import rand\n",
    "data = np.round(rand(2, 3))\n",
    "data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 使用象征所以分配数据:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<4x5 sparse matrix of type '<type 'numpy.float64'>'\n",
       "\twith 3 stored elements in LInked List format>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[:2, [1, 2, 3]] = data\n",
    "mtx  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (0, 1)\t1.0\n",
      "  (0, 3)\t1.0\n",
      "  (1, 2)\t1.0\n"
     ]
    }
   ],
   "source": [
    "print mtx   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 0.,  1.,  0.,  1.,  0.],\n",
       "        [ 0.,  0.,  1.,  0.,  0.],\n",
       "        [ 0.,  0.,  0.,  0.,  0.],\n",
       "        [ 0.,  0.,  0.,  0.,  0.]])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.,  1.,  0.,  1.,  0.],\n",
       "       [ 0.,  0.,  1.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.]])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.toarray()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "更多的切片和索引:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 1, 2, 0],\n",
       "        [3, 0, 1, 0],\n",
       "        [1, 0, 0, 1]])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.lil_matrix([[0, 1, 2, 0], [3, 0, 1, 0], [1, 0, 0, 1]])\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  (0, 1)\t1\n",
      "  (0, 2)\t2\n",
      "  (1, 0)\t3\n",
      "  (1, 2)\t1\n",
      "  (2, 0)\t1\n",
      "  (2, 3)\t1\n"
     ]
    }
   ],
   "source": [
    "print mtx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<2x4 sparse matrix of type '<type 'numpy.int64'>'\n",
       "\twith 4 stored elements in LInked List format>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[:2, :] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 1, 2, 0],\n",
       "        [3, 0, 1, 0]])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[:2, :].todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[3, 1]])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[1:2, [0,2]].todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 1, 2, 0],\n",
       "        [3, 0, 1, 0],\n",
       "        [1, 0, 0, 1]])"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.3 值的字典格式 (DOK)\n",
    "\n",
    "- Python字典的子类\n",
    "    - 键是 (行, 列) 索引元组 (不允许重复的条目)\n",
    "    - 值是对应的非零值\n",
    "- 高效增量构建稀疏矩阵\n",
    "- 构建器支持:\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空矩阵)\n",
    "- 高效 O(1) 对单个元素的访问\n",
    "- 灵活索引，改变稀疏结构是高效\n",
    "- 一旦创建完成后可以被高效转换为coo_matrix\n",
    "- 算术很慢 (循环用`dict.iteritems()`)\n",
    "- 用法:\n",
    "    - 当稀疏模式是未知的假设或改变时\n",
    "    \n",
    "##### 2.5.2.2.3.1 示例\n",
    "\n",
    "- 逐个元素创建一个DOK矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<5x5 sparse matrix of type '<type 'numpy.float64'>'\n",
       "\twith 0 stored elements in Dictionary Of Keys format>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.dok_matrix((5, 5), dtype=np.float64)\n",
    "mtx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<5x5 sparse matrix of type '<type 'numpy.float64'>'\n",
       "\twith 20 stored elements in Dictionary Of Keys format>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for ir in range(5):\n",
    "    for ic in range(5):\n",
    "        mtx[ir, ic] = 1.0 * (ir != ic)\n",
    "mtx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 0.,  1.,  1.,  1.,  1.],\n",
       "        [ 1.,  0.,  1.,  1.,  1.],\n",
       "        [ 1.,  1.,  0.,  1.,  1.],\n",
       "        [ 1.,  1.,  1.,  0.,  1.],\n",
       "        [ 1.,  1.,  1.,  1.,  0.]])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 切片与索引:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[1, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<1x2 sparse matrix of type '<type 'numpy.float64'>'\n",
       "\twith 1 stored elements in Dictionary Of Keys format>"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[1, 1:3]     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 0.,  1.]])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[1, 1:3].todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 1.,  0.],\n",
       "        [ 0.,  1.]])"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx[[2,1], 1:3].todense() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.4 座标格式 (COO)\n",
    "\n",
    "- 也被称为 ‘ijv’ 或 ‘triplet’ 格式\n",
    "    - 三个NumPy数组: row, col, data\n",
    "    - `data[i]`是在 (row[i], col[i]) 位置的值\n",
    "    - 允许重复值\n",
    "- `\\_data\\_matrix`的子类 (带有`data`属性的稀疏矩阵类)\n",
    "- 构建稀疏矩阵的高速模式\n",
    "- 构建器接受:\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空数组)\n",
    "    - `(data, ij)`元组\n",
    "- 与CSR/CSC格式非常快的互相转换\n",
    "- 快速的矩阵 * 向量 (sparsetools)\n",
    "- 快速而简便的逐项操作\n",
    "    - 直接操作数据数组 (快速NumPy机制)\n",
    "- 没有切片，没有算术 (直接)\n",
    "- 使用:\n",
    "    - 在各种稀疏格式间的灵活转换\n",
    "    - 当转化到其他形式 (通常是 CSR 或 CSC), 重复的条目被加总到一起\n",
    "        - 有限元素矩阵的快速高效创建\n",
    "        \n",
    "##### 2.5.2.2.4.1 示例\n",
    "\n",
    "- 创建空的COO矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 0, 0, 0],\n",
       "        [0, 0, 0, 0],\n",
       "        [0, 0, 0, 0]], dtype=int8)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.coo_matrix((3, 4), dtype=np.int8)\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 用 (data, ij) 元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<4x4 sparse matrix of type '<type 'numpy.int64'>'\n",
       "\twith 4 stored elements in COOrdinate format>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "row = np.array([0, 3, 1, 0])\n",
    "col = np.array([0, 3, 1, 2])\n",
    "data = np.array([4, 5, 7, 9])\n",
    "mtx = sparse.coo_matrix((data, (row, col)), shape=(4, 4))\n",
    "mtx     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[4, 0, 9, 0],\n",
       "        [0, 7, 0, 0],\n",
       "        [0, 0, 0, 0],\n",
       "        [0, 0, 0, 5]])"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.5 压缩稀疏行格式 (CSR)\n",
    "- 面向行\n",
    "    - 三个Numpy数组: `indices`, `indptr`, `data`\n",
    "        - `indices`是列索引的数组\n",
    "        - `data`是对应的非零值数组\n",
    "        - `indptr`指向行开始的所以和数据\n",
    "        - 长度是`n_row + 1`, 最后一个项目 = 值数量 = `indices`和`data`的长度\n",
    "        - i-th行的非零值是列索引为`indices[indptr[i]:indptr[i+1]]`的`data[indptr[i]:indptr[i+1]]`\n",
    "        - 项目 (i, j) 可以通过`data[indptr[i]+k]`, k是j在`indices[indptr[i]:indptr[i+1]]`的位置来访问\n",
    "    - `_cs_matrix` (常规 CSR/CSC 功能) 的子类\n",
    "    - `_data_matrix` (带有`data`属性的稀疏矩阵类) 的子类\n",
    "- 快速矩阵向量相乘和其他算术 (sparsetools)\n",
    "- 构建器接受:\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空矩阵)\n",
    "    - `(data, ij)` 元组\n",
    "    - `(data, indices, indptr)` 元组\n",
    "- 高效行切片，面向行的操作\n",
    "- 较慢的列切片，改变稀疏结构代价昂贵\n",
    "- 用途:\n",
    "    - 实际计算 (大多数线性求解器都支持这个格式)\n",
    "\n",
    "##### 2.5.2.2.5.1 示例\n",
    "\n",
    "- 创建空的CSR矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 0, 0, 0],\n",
       "        [0, 0, 0, 0],\n",
       "        [0, 0, 0, 0]], dtype=int8)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.csr_matrix((3, 4), dtype=np.int8)\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 用`(data, ij)`元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<3x3 sparse matrix of type '<type 'numpy.int64'>'\n",
       "\twith 6 stored elements in Compressed Sparse Row format>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "row = np.array([0, 0, 1, 2, 2, 2])\n",
    "col = np.array([0, 2, 2, 0, 1, 2])\n",
    "data = np.array([1, 2, 3, 4, 5, 6])\n",
    "mtx = sparse.csr_matrix((data, (row, col)), shape=(3, 3))\n",
    "mtx     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 2],\n",
       "        [0, 0, 3],\n",
       "        [4, 5, 6]])"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 2, 3, 4, 5, 6])"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 2, 0, 1, 2], dtype=int32)"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 3, 6], dtype=int32)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indptr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用`(data, indices, indptr)`元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 2],\n",
       "        [0, 0, 3],\n",
       "        [4, 5, 6]])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = np.array([1, 2, 3, 4, 5, 6])\n",
    "indices = np.array([0, 2, 2, 0, 1, 2])\n",
    "indptr = np.array([0, 2, 3, 6])\n",
    "mtx = sparse.csr_matrix((data, indices, indptr), shape=(3, 3))\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.6 压缩稀疏列格式 (CSC)\n",
    "\n",
    "- 面向列\n",
    "    - 三个Numpy数组: `indices`、`indptr`、`data`\n",
    "    - `indices`是行索引的数组\n",
    "    - `data`是对应的非零值\n",
    "    - `indptr`指向`indices`和`data`开始的列\n",
    "    - 长度是`n_col + 1`, 最后一个条目 = 值数量 = `indices`和`data`的长度\n",
    "    - 第i列的非零值是行索引为`indices[indptr[i]:indptr[i+1]]`的`data[indptr[i]:indptr[i+1]]`\n",
    "    - 项目 (i, j) 可以作为`data[indptr[j]+k]`访问, k是i在`indices[indptr[j]:indptr[j+1]]`的位置\n",
    "    - `_cs_matrix`的子类 (通用的 CSR/CSC 功能性)\n",
    "        - `_data_matrix`的子类 (带有`data`属性的稀疏矩阵类)\n",
    "- 快速的矩阵和向量相乘及其他数学 (sparsetools)\n",
    "- 构建器接受：\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空矩阵)\n",
    "    - `(data, ij)`元组\n",
    "    - `(data, indices, indptr)`元组\n",
    "- 高效列切片、面向列的操作\n",
    "- 较慢的行切片、改变稀疏结构代价昂贵\n",
    "- 用途:\n",
    "    - 实际计算 (巨大多数线性求解器支持这个格式)\n",
    "    \n",
    "##### 2.5.2.2.6.1 示例\n",
    "\n",
    "- 创建空CSC矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 0, 0, 0],\n",
       "        [0, 0, 0, 0],\n",
       "        [0, 0, 0, 0]], dtype=int8)"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.csc_matrix((3, 4), dtype=np.int8)\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 用`(data, ij)`元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<3x3 sparse matrix of type '<type 'numpy.int64'>'\n",
       "\twith 6 stored elements in Compressed Sparse Column format>"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "row = np.array([0, 0, 1, 2, 2, 2])\n",
    "col = np.array([0, 2, 2, 0, 1, 2])\n",
    "data = np.array([1, 2, 3, 4, 5, 6])\n",
    "mtx = sparse.csc_matrix((data, (row, col)), shape=(3, 3))\n",
    "mtx     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 2],\n",
       "        [0, 0, 3],\n",
       "        [4, 5, 6]])"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 4, 5, 2, 3, 6])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 2, 0, 1, 2], dtype=int32)"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 3, 6], dtype=int32)"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indptr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 用`(data, indices, indptr)`元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 2],\n",
       "        [0, 0, 3],\n",
       "        [4, 5, 6]])"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = np.array([1, 4, 5, 2, 3, 6])\n",
    "indices = np.array([0, 2, 2, 0, 1, 2])\n",
    "indptr = np.array([0, 2, 3, 6])\n",
    "mtx = sparse.csc_matrix((data, indices, indptr), shape=(3, 3))\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.5.2.2.7 块压缩行格式 (BSR)\n",
    "- 本质上，CSR带有密集的固定形状的子矩阵而不是纯量的项目\n",
    "    - 块大小`(R, C)`必须可以整除矩阵的形状`(M, N)`\n",
    "    - 三个Numpy数组: `indices`、`indptr`、`data`\n",
    "        - `indices`是每个块列索引的数组\n",
    "        - `data`是形状为(nnz, R, C)对应的非零值\n",
    "        - ...\n",
    "    - `_cs_matrix`的子类 (通用的CSR/CSC功能性)\n",
    "    - `_data_matrix`的子类 (带有`data`属性的稀疏矩阵类)\n",
    "- 快速矩阵向量相乘和其他的算术 (sparsetools)\n",
    "- 构建器接受:\n",
    "    - 密集矩阵 (数组)\n",
    "    - 稀疏矩阵\n",
    "    - 形状元组 (创建空的矩阵)\n",
    "    - `(data, ij)`元组\n",
    "    - `(data, indices, indptr)`元组 \n",
    "- 许多对于带有密集子矩阵的稀疏矩阵算术操作比CSR更高效很多\n",
    "- 用途:\n",
    "    - 类似CSR\n",
    "    - 有限元素向量值离散化\n",
    "##### 2.5.2.2.7.1 示例\n",
    "\n",
    "- 创建空的`(1, 1)`块大小的（类似CSR...）的BSR矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<3x4 sparse matrix of type '<type 'numpy.int8'>'\n",
       "\twith 0 stored elements (blocksize = 1x1) in Block Sparse Row format>"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.bsr_matrix((3, 4), dtype=np.int8)\n",
    "mtx "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 0, 0, 0],\n",
       "        [0, 0, 0, 0],\n",
       "        [0, 0, 0, 0]], dtype=int8)"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 创建块大小`(3, 2)`的空BSR矩阵:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<3x4 sparse matrix of type '<type 'numpy.int8'>'\n",
       "\twith 0 stored elements (blocksize = 3x2) in Block Sparse Row format>"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx = sparse.bsr_matrix((3, 4), blocksize=(3, 2), dtype=np.int8)\n",
    "mtx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    - 一个bug?\n",
    "- 用`(1, 1)`块大小 (类似 CSR...)`(data, ij)`的元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<3x3 sparse matrix of type '<type 'numpy.int64'>'\n",
       "\twith 6 stored elements (blocksize = 1x1) in Block Sparse Row format>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "row = np.array([0, 0, 1, 2, 2, 2])\n",
    "col = np.array([0, 2, 2, 0, 1, 2])\n",
    "data = np.array([1, 2, 3, 4, 5, 6])\n",
    "mtx = sparse.bsr_matrix((data, (row, col)), shape=(3, 3))\n",
    "mtx "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 0, 2],\n",
       "        [0, 0, 3],\n",
       "        [4, 5, 6]])"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 2, 0, 1, 2], dtype=int32)"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 3, 6], dtype=int32)"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mtx.indptr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 用`(2, 1)`块大小`(data, indices, indptr)`的元组创建:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 1, 0, 0, 2, 2],\n",
       "        [1, 1, 0, 0, 2, 2],\n",
       "        [0, 0, 0, 0, 3, 3],\n",
       "        [0, 0, 0, 0, 3, 3],\n",
       "        [4, 4, 5, 5, 6, 6],\n",
       "        [4, 4, 5, 5, 6, 6]])"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "indptr = np.array([0, 2, 3, 6])\n",
    "indices = np.array([0, 2, 2, 0, 1, 2])\n",
    "data = np.array([1, 2, 3, 4, 5, 6]).repeat(4).reshape(6, 2, 2)\n",
    "mtx = sparse.bsr_matrix((data, indices, indptr), shape=(6, 6))\n",
    "mtx.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[[1, 1],\n",
       "        [1, 1]],\n",
       "\n",
       "       [[2, 2],\n",
       "        [2, 2]],\n",
       "\n",
       "       [[3, 3],\n",
       "        [3, 3]],\n",
       "\n",
       "       [[4, 4],\n",
       "        [4, 4]],\n",
       "\n",
       "       [[5, 5],\n",
       "        [5, 5]],\n",
       "\n",
       "       [[6, 6],\n",
       "        [6, 6]]])"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5.2.3 总结\n",
    "\n",
    "存储机制的总结\n",
    "\n",
    "\n",
    "|格式|矩阵 * 向量|提取项目|灵活提取|设置项目|灵活设置|求解器|备注|\n",
    "|------|---------------|--------|---------|--------|---------|-------|----|\n",
    "|DIA|sparsetools|.|.|.|.|迭代|有数据数组，专门化|\n",
    "|LIL|通过 CSR|是|是|是|是|迭代|通过CSR的算术, 增量构建|\n",
    "|DOK|python|是|只有一个轴|是|是|迭代|`O(1)`条目访问, 增量构建|\n",
    "|COO|sparsetools|.|.|.|.|迭代|有数据数组, 便利的快速转换|\n",
    "|CSR|sparsetools|是|是|慢|.|任何|有数据数组, 快速以行为主的操作|\n",
    "|CSC|sparsetools|是|是|慢|.|任何|有数据数组, 快速以列为主的操作|\n",
    "|BSR|sparsetools|.|.|.|.|专门化|有数据数组，专门化|"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}