面向二元矩阵与向量乘法的运算次数最小化算法设计

基础定义 #

• 设D是定义了加减运算的对象（具体为固定维度的大型实数矩阵）：
  • 加法满足结合律与交换律，运算结果仍为D类型；
  • 减法返回D类型对象，定义为：

    x = y-z   <=>  y = x + z
    

• 设A为(n,m)规模的二元矩阵，b为m维D类型向量，y=Ab为矩阵与向量的乘积。

示例说明 #

给定矩阵A #

A = [ 1 1 0 1 0 0 0
      1 1 1 0 0 0 0
      1 1 1 1 0 0 0
      0 0 1 1 0 0 0
      1 1 1 1 1 1 0
      1 1 1 1 1 1 1
    ]

暴力计算方案 #

采用暴力法（跳过零元素）计算y=Ab的表达式如下：

y0 = b0 + b1 + b3
y1 = b0 + b1 + b2
y2 = b0 + b1 + b2 + b3
y3 = b2 + b3
y4 = b0 + b1 + b2 + b3 + b4 + b5
y5 = b0 + b1 + b2 + b3 + b4 + b5 + b6

所需加法次数为矩阵A中1的个数减去行数，本例中为 25-6=19 次。

优化后的计算方案 #

通过引入临时变量zi，可将计算转换为如下形式，大幅减少加法次数：

z0 = b0 + b1
z1 = b2 + b3
z2 = z0 + z1
z3 = z2 + b4 + b5
y0 = z0 + b3
y1 = z0 + b2
y2 = z2
y3 = z1
y4 = z3
y5 = z3 + b6

此时加法次数降至8次。

核心需求 #

设计一种算法，通过灵活引入临时变量（允许使用减法，其成本与加法相同）生成计算方案，以最小化加法运算次数。

内容的提问来源于stack exchange，提问作者Fabio