高效计算Toeplitz/Hankel矩阵列和的方法探究

N×N的Toeplitz矩阵存在大量重复值，其镜像结构Hankel矩阵亦是如此。我们的目标是找到以最少加减操作数为标准的高效列和计算方法。

现有一份针对Hankel矩阵的Python实现（仅作为可运行伪代码，不关注CPU执行速度，只统计加减操作次数），经统计需要3N-4次加法。以下是翻译后的代码及注释：

import numpy as np
import scipy

# N×N矩阵的维度
N = 8

# 定义N×N Hankel矩阵的最后一行和第一列
# 注：Hankel矩阵要求第一列的最后一个元素与最后一行的第一个元素相等
r = np.random.randint(1, 100, N)                              # 最后一行
c = np.concatenate((np.random.randint(1, 100, N-1), [r[0]]))  # 第一列

# 计算累积和
cumsum_r = np.cumsum(r[1:])  # 最后一行从第2个元素开始的累积和
cumsum_c = np.cumsum(np.flip(c))  # 第一列翻转后的累积和

# 计算各列的和
sums = np.zeros(N)
for i in range(N):
    if i == 0:
        sums[i] = cumsum_c[N-1]  # 第一列的和等于翻转后第一列的总累积和
    else:
        sums[i] = cumsum_c[N-1-i] + cumsum_r[i-1]

# 显式构造Hankel矩阵并验证列和正确性
A = scipy.linalg.hankel(c, r)
mismatch = np.sum(A, axis=0) - sums

print(f"Mismatch: {mismatch}")

现有方案的操作数统计 #

现有方案的加法操作次数拆解：

1. 计算cumsum_r：对r[1:]（共N-1个元素）求累积和，需要N-2次加法
2. 计算cumsum_c：对翻转后的c（共N个元素）求累积和，需要N-1次加法
3. 计算列和：第0列直接取用累积和结果，无加法；剩余N-1列每列需1次加法，共N-1次加法
   总加法次数：(N-2)+(N-1)+(N-1) = 3N-4，与描述一致。

是否存在更优方案？ #

经过分析，3N-4次加法已是当前能达到的最优操作数，原因如下：

1. 从Hankel矩阵的结构特性出发，所有列和的计算必然依赖于对第一列后缀和、最后一行前缀和的推导，这两部分的计算至少需要(N-1)+(N-2) = 2N-3次加法
2. 将后缀和与前缀和组合得到每一列的和，至少需要N-1次加法
3. 尝试递推式计算（如S_i = S_{i-1} + r[i] - c[i-1]）会引入减法操作，且总操作数为3N-3，比现有方案多1次操作；其他构造拼接数组再求前缀和的方式，总操作数更高（3N-2次）

对于任意N≥2，现有方案的操作数已无法进一步减少。

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