CRS格式矩阵-向量乘积

使用CRS格式计算矩阵-向量乘积 y=Ax 可以按常规方式表示：

y_i=\sum_j a_{i,j}x_j,

因为这会遍历矩阵 A 的行。对于一个 n \times n 的矩阵 A，矩阵-向量乘法由以下公式给出：

   for i = 1, n
       y(i)  = 0
       for j = row_ptr(i), row_ptr(i+1) - 1
           y(i) = y(i) + val(j) * x(col_ind(j))
       end;
   end;

由于这种方法仅乘以非零矩阵元素，运算次数是 A 中非零元素数量的两倍，与密集运算所需的 2n^2 相比，这是一个显著的节省。

对于转置乘积 y=A^Tx，我们不能使用以下公式

y_i=\sum_j (A^T)_{i,j}x_j=\sum_j a_{j,i}x_j,

因为这暗示着遍历矩阵的列，对于以CRS格式存储的矩阵来说，这是一个极其低效的操作。因此，我们切换索引为

\hbox{对于所有 j，执行对于所有 i：}\qquad y_i\leftarrow y_i + a_{j,i}x_j.

涉及 A^T 的矩阵-向量乘法随后由以下公式给出：

   for i = 1, n
       y(i) =  0
   end;
   for j = 1, n
       for i = row_ptr(j), row_ptr(j+1)-1
           y(col_ind(i)) = y(col_ind(i)) + val(i) * x(j)
       end;
   end;

上述两种矩阵-向量乘积在结构上大致相同，并且都使用间接寻址。因此，它们在任何给定计算机上的向量化特性是相同的。然而，第一个乘积 (y=Ax) 在内存访问模式上更为有利，因为它（每次外循环迭代）读取两个数据向量（矩阵 A 的一行和输入向量 x）并写入一个标量。转置乘积 (y=A^Tx) 则相反，读取输入向量的一个元素和矩阵 A 的一行，并且同时读取和写入结果向量 y。除非实现这些方法的机器具有三条独立的内存路径（例如，Cray的向量计算机），否则内存流量将限制性能。这对于基于RISC的架构是一个重要的考虑因素。