2.5.1. 简介

(dense) matrix is:

  • mathematical object
  • data structure for storing a 2D array of values

important features:

  • 为所有元素一次分配所有内存
    • 通常是一个连续的块,想象一下NumPy ndarray
  • 快速访问单个元素(*)

2.5.1.1. Why Sparse Matrices?

  • 内存,以n**2增长

  • small example (double precision matrix):

    >>> import numpy as np
    
    >>> import matplotlib.pyplot as plt
    >>> x = np.linspace(0, 1e6, 10)
    >>> plt.plot(x, 8.0 * (x**2) / 1e6, lw=5)
    [<matplotlib.lines.Line2D object at ...>]
    >>> plt.xlabel('size n')
    <matplotlib.text.Text object at ...>
    >>> plt.ylabel('memory [MB]')
    <matplotlib.text.Text object at ...>

2.5.1.2. Sparse Matrices vs. Sparse Matrix Storage Schemes

  • sparse matrix is a matrix, which is almost empty
  • 存储所有的零非常浪费 -> 只存储非零元素
  • 考虑压缩
  • pros: huge memory savings
  • cons: depends on actual storage scheme, (*) usually does not hold

2.5.1.3. 典型应用

  • solution of partial differential equations (PDEs)
    • the finite element method
    • 机械工程、电子技术、物理学...
  • graph theory
    • (i, j)处的非零表示节点i连接到节点j
  • ...

2.5.1.4. 先决条件

recent versions of

  • numpy
  • scipy
  • matplotlib (optional)
  • ipython (the enhancements come handy)

2.5.1.5. 稀疏结构可视化

  • spy() from matplotlib
  • example plots:
../../_images/graph.png ../../_images/graph_g.png ../../_images/graph_rcm.png