Toeplitz矩阵向量相乘，用快速傅里叶变换进行加速 MATLAB

可以使用 MATLAB 中的 `fft` 函数进行 Toeplitz 矩阵向量相乘的加速。具体步骤如下：

1. 首先，将 Toeplitz 矩阵 $A$ 和列向量 $x$ 分别进行零填充，使得它们的长度均为 $2N-1$，其中 $N$ 是矩阵的维度。

2. 然后，将 $A$ 和 $x$ 分别进行一维离散傅里叶变换（DFT），得到 $A_{DFT}$ 和 $x_{DFT}$。

3. 对 $A_{DFT}$ 和 $x_{DFT}$ 进行点乘，得到 $y_{DFT} = A_{DFT} \cdot x_{DFT}$。

4. 将 $y_{DFT}$ 进行一维逆离散傅里叶变换（IDFT），得到最终结果 $y$。

MATLAB 代码如下：

function y = toeplitz_mult(A, x)
    % get dimensions
    n = size(A, 1);
    m = size(x, 1);
    
    % zero padding
    A = [A zeros(n, m-n)];
    x = [x; zeros(n-m, 1)];
    
    % DFT
    A_dft = fft(A);
    x_dft = fft(x);
    
    % pointwise multiplication
    y_dft = A_dft .* x_dft;
    
    % IDFT
    y = ifft(y_dft);
    
    % take real part (due to numerical errors)
    y = real(y);
end

这个函数输入为 Toeplitz 矩阵 $A$ 和列向量 $x$，输出为向量 $y = Ax$。