⚡ electrical engineering

Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation

本文引入了一种级联二阶IIR滤波器的块矩阵重构方法，该方法通过部分LU分解和循环约减实现了高度并行化处理，通过将顺序依赖深度从 $\mathcal{O}(N)$ 降低至 $\mathcal{O}(\log_2 N)$ ，实现了相比传统标量方法高达10倍的加速。

原作者： Haotian Zhai, Bernd-Peter Paris

发布于 2026-07-16

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Haotian Zhai, Bernd-Peter Paris

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在一台非常陈旧、略有故障的收音机上听你最喜欢的歌曲。有时声音会变得模糊，或者会出现奇怪的嗡嗡声。为了修复这个问题，工程师们使用了一种被称为“滤波器”的特殊数学工具。你可以把滤波器想象成一个声音的筛子：它能让清晰悦耳的音符通过，同时拦截掉那些多余的静电噪声和杂音。构建这种筛子主要有两种方式。一种方式像是堆叠大量的简单漏斗（称为 FIR 滤波器）；这种方式非常可靠，但移动水流需要耗费大量的工作。而另一种方式——这也是本文关注的重点——则是使用一种聪明的、具有自我修正能力的循环（称为 IIR 或递归滤波器）。这种循环极其高效，只需要很少的部件就能获得同样纯净的声音。

然而，这种高效循环也有一个弊端：它是一个“串行”过程。想象一下，有一排人正在传递一桶水。A 个人必须填满水桶后，才能传给 B 个人；B 个人必须填满后，才能传给 C 个人。你不能通过增加人数来提高速度，因为每个人都必须等待前一个人。在计算机的世界里，这种“等待”产生了一个瓶颈，会拖慢一切速度，尤其是当我们想要处理海量数据时，比如实时视频或高速互联网。核心问题一直在于：我们如何让这种高效的、自我修正的循环在不破坏因果链条的前提下，实现并行处理，从而跑得更快？

这篇题为《通过块矩阵重构实现快速级联递归滤波》（Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation）的论文正是解决了这个问题。作者 Haotian Zhai 和 Bernd-Peter Paris 意识到，虽然我们无法逐个加速传递水桶的人，但我们可以改变游戏规则。他们不再将数据视为一长串独立的样本，而是决定一次抓取一整块样本，并将其视为一个复杂的单一谜题。

他们发现了一种巧妙的重新排列数据的方法，就像将一副扑克牌按特定模式重新洗牌一样，这能将混乱的等待队列变成一个整齐有序的结构。一旦数据进入这种新形状，他们就应用了两种不同的“超速”策略来解决这个谜题：

“部分 LU”策略（PH 分解法）： 这种方法像是一条智能装配线，让谜题碎片保持在它们整齐、稀疏的格子里。它将问题分解为一个“特定”部分（输入的形式）和一个“一般”部分（系统的反应），并以一种避免了通常会拖慢速度的繁重、杂乱数学运算的方式进行求解。
“循环约减”策略： 这是真正的重头戏。想象有一排 1,000 个人在传递水桶。与其等待整排人完成，不如将他们两两分组，先解决每对组合的问题，然后再将结果进行分组，通过不断倍增解决速度，直到整条线完成，而整个过程只需寥寥数步。这就像反复将一张巨大的纸对折，直到它变得很小。这种技术是作者首次将其应用于此类滤波器的，它将“等待时间”从与样本数量成正比缩减到了与样本数量的对数成正比。用通俗的话说，如果你将数据量增加一倍，你花费的时间并不会增加一倍，而是几乎不增加多少时间。

论文还解决了“级联”滤波器的一个棘手问题。通常，当你把多个滤波器堆叠在一起时（就像堆叠几个筛子），你必须在每个滤波器之间来回搬运数据，这非常浪费时间。作者展示了，利用他们的新方法，滤波器之间所需的这种搬运过程会完美地相互抵消。这就像如果你每次进门都要换鞋，但后来发现门的设计让你可以完全不需要停下来换鞋一样。

为了证明这不仅仅是纸面上的酷想法，作者在真实的计算机芯片（具体是 Intel 处理器）上测试了它。他们发现，对于一个复杂的 16 阶滤波器，他们的新型“循环约减”方法比目前主流的软件工具（如 scipy.signal.sosfilt）快了约 8 倍，并且比传统的逐个样本处理方式快了高达 10 倍。在现代计算机芯片上，这种新方法每秒可以处理超过 6.18 亿个样本。

作者对这些结果非常有信心，因为他们测量的是硬件上实际的机器时钟周期，而不仅仅是模拟数据。他们证明了虽然“部分 LU”方法在处理少量数据时表现出色，但“循环约减”方法在处理海量数据时更具优势，这使其成为实时视频处理或先进通信系统等高速应用领域的游戏规则改变者。他们甚至开源了代码供他人使用，这标志着在使这些强大的滤波器既快速又适用于日常技术方面迈出了重要一步。

技术摘要：通过分块矩阵重构实现快速级联递归滤波

问题陈述
以级联二阶节（biquads）实现的递归（IIR）滤波器是数字信号处理中的标准方法，因其设计具有通用性且对系数量化具有鲁棒性。然而，固有的样本间反馈依赖性产生了顺序瓶颈，阻碍了高效的并行计算。虽然之前的研究探索了并行化直接型滤波器或使用基于 FFT 的近似方法，但这些方法要么无法保证稳定性，要么未能解决级联多个 biquad 引入的特定复杂性。现有的并行算法很大程度上忽略了级联结构，将滤波器视为单一的直接型实体，这导致级联带来的计算开销未得到解决。

方法论
作者提出了一种级联二阶 IIR 滤波器的分块矩阵重构方法，旨在暴露块内（intra-block）和块间（inter-block）层面的并行性。核心方法包括：

矩阵重构： 将 biquad 差分方程表示为一个带状分块 Toeplitz 线性系统。通过对一组 $NL $个样本进行步长为$ N $的置换，将该系统转化为分块三对角结构。该矩阵的条目是单位矩阵 ($ I $) 和下移位 ($ R$) 矩阵的标量倍数。
并行求解器： 开发了两种并行算法来求解生成的递归阶段：
- PH 分解（部分 LU 分解）： 该方法通过避免标准 LU 分解中产生的稠密矩阵，保留了系统的稀疏分块结构。它利用一种特定的特解/齐次分解（particular-homogeneous decomposition），其中特解通过前向替换计算，而齐次修正项通过终端块应用。终端块使用块级递归倍增（Sklansky 构造）进行求解，以降低顺序深度。
- 循环约减（Cyclic Reduction）： 首次将其应用于递归滤波。该技术通过系统地消除交替块来使系统规模减半。这使得顺序依赖深度从 $O(N)$ 降低到 $O(\log_2 N)$ 。
级联优化： 对于 $K$ 个 biquad 的级联，作者证明了一个 biquad 节输出所需的步长- $N$ 置换与下一个节输入所需的逆置换完全抵消。因此，整个级联仅需在开始时进行一次置换，并在结束时进行一次去置换，从而消除了 $2(K-1)$ 个冗余阶段。

核心贡献

分块矩阵问题表述： 提供了一个系统的代数框架，将二阶递归滤波器转化为带状分块 Toeplitz 系统，从而能够应用多块滤波算法。
PH 分解： 对二阶节的特解/齐次分解进行了扩展，利用递归倍增来求解终端块，同时保持稀疏分块结构。
用于 IIR 的循环约减： 首次将循环约减应用于递归滤波，实现了与标准因子分解法相比 $O(\log_2 N)$ 的顺序依赖深度。
级联成本摊销： 证明了级联 biquad 中的中间置换会相互抵消，随着滤波器阶数的增加，显著降低了每个 biquad 的开销。
এটি
复杂度分析与验证： 推导了精确的块级操作计数（FMA 和 shuffle 操作），并在三种 Intel 微架构（Haswell、Skylake、Meteor Lake）上通过周期精确测量进行了验证。

实验结果
所提算法使用 C++ 及 SIMD 指令集（AVX2）实现，并在一个 16 阶级联 IIR 滤波器系统中进行了评估。

性能提升： 在单个 Meteor Lake 核心上，循环约减算法实现了约 618 MS/s（百万样本每秒）的吞吐量。这比标准的 scipy.signal.sosfilt 实现（运行速度约为 77 MS/s）实现了 8 倍的吞吐量提升，并且相比标量滤波实现了高达 10 倍的每样本时钟周期减少。
可扩展性： 两种算法在较新的架构上表现出良好的扩展性。PH 分解在较小的样本量下具有较低的延迟，而循环约减由于其更低的顺序深度，在较大的样本量下具有更高的吞吐量。
效率： 多块算法成功将每个样本的时钟周期降低了高达 10 倍（与标量滤波相比），其中循环约减法在大型块大小（$NL = 512$）时表现出最佳性能。

意义与声明
本文声称填补了文献中的关键空白，提供了一种专门针对 级联二阶实现 的并行算法，而这正是 IIR 滤波器在实践中的主流实现方式。通过将问题重构为分块三对角系统，作者暴露了此前因顺序依赖而无法实现的并行性。

作者强调，这项工作是两部分研究的第一部分，重点在于算法理论和单核 SIMD 验证。他们声称发布了第一个提供级联二阶形式并行 IIR 滤波的开源库，结合了数值准确性与商用硬件上的高吞吐量。该工作范围适中，作者指出，虽然实现了显著的单核加速，但配套论文将讨论用于高吞吐量批处理和低延迟实时场景的多核及 GPU 实现。结果证实，所提方法在不损害级联形式的稳定性或设计灵活性前提下，有效地缓解了递归滤波固有的顺序瓶颈。

技术摘要：通过分块矩阵重构实现快速级联递归滤波

类似论文