稀疏矩阵与矩阵块乘法

Sparse Matrix

A matrix with lots of zeros is called sparse (the opposite of sparse is dense). For sparse matrices, you can save a lot of memory by only storing the non-zero values.

Another example of a large, sparse matrix:

Source

There are the most common sparse storage formats:
(参考)

• coordinate-wise (scipy calls COO)
• compressed sparse row (CSR)
• compressed sparse column (CSC)

1. COO

按坐标存储 non-zero value：

2. CSR

RowPtr 的 index=1 处的value为3，代表 Row1 starts with val 的 index=3 处的值22。

就是一种按行存储的规则，类似数组里面计算某个element的addr的方式。

这样做的好处就是access data by row 的时候比较方便，比如想取 index=3 的row，一check，它starts with 9，stops before 12，就去访问 index=[9,11] 的value。

3. CSC
类似CSR。

Block Matrix Multiplication

Ordinary Matrix Multiplication

Q: What is the computational complexity (big $\mathcal{O}$) of matrix multiplication for multiplying two n×n$n\times n$ matrices A×B=C$A\times B=C$?

What this looks like:

for i=1 to n
    {read row i of A into fast memory}
    for j=1 to n
        {read col j of B into fast memory}
        for k=1 to n
            C[i,j] += C[i,j] + A[i,k] x B[k,j]
        {write C[i,j] back to slow memory}

Question: How many reads and writes are made?

B的每个Column j 会read n2$n^2$次，而每个column又有n个element，所以一共read n3次$n^3次$，远多于 A$A$。

所以矩阵乘法的顺序会影响读写速度（数据库也说过）。

Block Matix Multiplication

Divide A,B,C$A,B,C$ into N×N$N\times N$ blocks of size nN×nN$\frac{n}{N}\times \frac{n}{N}$
(Source)

What this looks like:

for i=1 to N
    for j=1 to N
        for k=1 to N
            {read block (i,k) of A}
            {read block (k,j) of B}
            block (i,j) of C += block of A times block of B
        {write block (i,j) of C back to slow memory}

Question 1: What is the big-$\mathcal{O}$ of this?

仍然是 O(n3)$O(n^3)$

Question 2: How many reads and writes are made?

Block Matrix 是 (nN)2$(\frac{n}{N}{)}^2$ 大小的，三层的for loop有 (nN)2⋅N3=N⋅n2$(\frac{n}{N}{)}^2\cdot N^3=N\cdot n^2$ ，前面还要乘上一个2：2(nN)2⋅N3=2N⋅n2$2(\frac{n}{N}{)}^2\cdot N^3=2N\cdot n^2$，因此对 A$A$、B$B$两个矩阵都要read这么多次。