2.5.1. 简介

(密集)矩阵是:

  • 数学对象
  • 数据结构,用于存储值的二维数组

重要特征:

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

2.5.1.1. Why Sparse Matrices?

  • 内存,以n**2增长

  • 小例子(双精度矩阵):

    >>> 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 Matrix Storage Schemes

  • 稀疏矩阵是几乎为空的矩阵
  • 存储所有的零非常浪费 -> 只存储非零元素
  • 考虑压缩
  • 优点:巨大的内存节省
  • 缺点:取决于实际存储方案,(*)通常不成立

2.5.1.3. 典型应用

  • 偏微分方程(PDEs)
    • 有限元法
    • 机械工程、电子技术、物理学...
  • 图论
    • (i, j)处的非零表示节点i连接到节点j
  • ...

2.5.1.4. 先决条件

最新版本

  • numpy
  • scipy
  • matplotlib(可选)
  • ipython(增强功能很方便)

2.5.1.5. 稀疏结构可视化

  • 来自matplotlibspy()
  • 示例图:
../../_images/graph.png ../../_images/graph_g.png ../../_images/graph_rcm.png