对 Toeplitz/Hankel 矩阵的列求和的有效方法

Question

(N × N) Toeplitz 矩阵 中有许多重复值。示例：

其镜像汉克尔矩阵也是如此。

我正在尝试找到对此类矩阵的列求和的最有效方法，其中我定义“最有效”是指加/减运算的最小数量。

我在下面包含了我对 Hankel 矩阵的 Python 尝试。如果我没数错的话，这需要 3N-4 添加。可以做得更好吗？

import numpy as np
import scipy

# NxN matrix dimension
N = 8

# Define the last row and first column of the NxN Hankel matrix
r = np.random.randint(1, 100, N)                              # Last row
c = np.concatenate((np.random.randint(1, 100, N-1), [r[0]]))  # First column

# Cumulative sums
cumsum_r = np.cumsum(r[1:])
cumsum_c = np.cumsum(np.flip(c))

# Compute column sums
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]

# Explicitly construct the Hankel matrix and check the sums
A = scipy.linalg.hankel(c, r)
mismatch = np.sum(A, axis=0) - sums

print(f"Mismatch: {mismatch}")

Answer 1

看起来合理，但不要循环，并断言你的不匹配而不是打印它：

import numpy as np
import scipy

# NxN matrix dimension
N = 8

# Define the last row and first column of the NxN Hankel matrix
rand = np.random.default_rng(seed=0)
r = rand.integers(low=1, high=100, size=N)  # Last row
c = np.concatenate((  # First column
    rand.integers(low=1, high=100, size=N-1),
    r[:1],
))

# Cumulative sums
cumsum_r = np.cumsum(r[1:])
cumsum_c = np.cumsum(c[::-1])

# Compute column sums
sums = np.empty(N)
sums[0] = cumsum_c[N-1]
sums[1:] = cumsum_c[-2::-1] + cumsum_r

# Explicitly construct the Hankel matrix and check the sums
A = scipy.linalg.hankel(c, r)
assert np.array_equal(sums, np.sum(A, axis=0))