Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation

summary

The gist

Recursive (IIR) filters realized as cascaded second-order sections (biquads) offer both design generality and robustness against coefficient quantization…

In short

This work addresses a limitation in parallelizing recursive filters by reformulating cascaded second-order sections (biquads) as a banded block-Toeplitz linear system. The authors developed two data-parallel algorithms—PH factorization and cyclic reduction—that significantly speed up single-core IIR filter implementations, achieving up to 10x reductions in clock cycles per sample.

Key concepts

Block-Matrix Reformulation
The paper treats the recursive filtering equations not as a sequence of steps, but as a large linear system arranged in blocks. By using a stride-N permutation, they map samples into this structure, which exposes inherent parallelism and allows for systematic development of parallel algorithms for any order filter.
PH Factorization
This is a specific type of partial LU factorization applied to the block system. Unlike standard LU decomposition, PH factorization is designed to maintain the sparse block structure throughout the solving process. This avoids creating dense matrices, making it much more efficient for solving the recursive stages of high-order filters.
Cyclic Reduction
This technique adapts cyclic reduction to a block-tridiagonal structure. It dramatically cuts down on sequential dependency depth from O(N) to O(log2 N). This means that instead of waiting sequentially through every stage, the process can be solved much faster, leading to significant throughput gains.
Block Permutation Amortization
The necessary permutations used to group samples into blocks are not repeated for every section. Because the intermediate permutations between successive biquads cancel out exactly, only a single pair of permutations is needed for the entire cascade. This minimizes overhead in high-order systems.

Terminology used across episodes

This episode discusses

The paper

Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation · Read on arXiv

Haotian Zhai, Bernd-Peter Paris

George Mason University

Recursive (IIR) filters realized as cascaded second-order sections (biquads) offer both design generality and robustness against coefficient quantization. However, their inherent sample-to-sample feedback dependency poses a fundamental obstacle to parallel computation. This paper reformulates the biquad difference equation as a banded block-Toeplitz linear system. It relies on a stride- N permutation that maps a group of NL samples into a block-tridiagonal structure whose entries are scalar multiples of identity and shift matrices. Within this framework, two data-parallel algorithms are developed which, to the best of our knowledge, are the fastest, single-core IIR filter implementations reported to date. A partial LU (PH) factorization preserves the sparse block structure and a cyclic reduction reduces the sequential dependency depth from O(N) to O(2 N). For a cascade of K biquads, the intermediate permutations between successive sections cancel exactly, so that only a single pair of permutations is required for the entire cascade. Exact block-level operation counts are derived for every algorithmic stage and validated against cycle-accurate measurements on three micro-architectures supporting AVX2 SIMD instructions. Experimental results for a 16th-order system show that the proposed multi-block algorithms reduce clock cycles per sample by up to 10 times compared to scalar filtering, with both algorithms scaling favorably on newer architectures. On a single Meteor Lake core, cyclic reduction achieves approximately 616 MS/s---four times the throughput of Intel's vendor-tuned IPP library.

Transcript

Introduction to the show: ident: Electrical Engineering. The day in electrical engineering: signals, systems and the hardware that carries them.

Rosa: I'm Rosa.

Dev: And I'm Dev, here with Taro.

Rosa: We're looking at the paper: "Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation".

Dev: Here's the gist of the paper. Recursive (IIR) filters realized as cascaded second-order sections (biquads) offer both design generality and robustness against coefficient quantization, but their inherent sample-to-sample feedback dependency poses a fundamental obstacle to parallel computation <ref:2607.14054#pg2>.

Rosa: This paper reformulates the biquad difference equation as a banded block-Toeplitz linear system and develops two data-parallel algorithms that achieve the fastest single-core IIR filter implementations reported to date <ref:2607.14054#pg3>.

Dev: Block-Matrix Reformulation The authors reformulate the biquad difference equation as a banded block-Toeplitz linear system, relying on a stride-N permutation to map a group of NL samples into a block-tridiagonal structure whose entries are scalar multiples of identity and shift matrices <ref:2607.14054#pg4>.

Rosa: This formulation provides the systematic algebraic framework in which new classes of filtering algorithms arise naturally <ref:2607.14054#pg4>.

Title and authors: Rosa: So we’re focusing on how they reformulate things and what kind of speedup they claim. This paper, 'Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation', is about taking the standard way of looking at these recursive filters and turning it into a system that computers can actually process in parallel.

Dev: Right. The authors introduce this block matrix formulation, which involves using a stride N permutation to map those NL samples into a block tridiagonal structure. They say this systematic algebraic framework opens up new ways to think about these filtering algorithms, not just the standard sequential way of doing things.

Taro: So it’s moving beyond just the direct-form realizations that we usually see, which is interesting because it suggests a more structured path for parallelization.

Rosa: And they then introduce two specific algorithms within this new structure. The first is something called a partial LU factorization, or PH factorization, and the second is a cyclic reduction technique adapted for this block tridiagonal setup.

Dev: The PH factorization is important because it’s designed to preserve that sparse block structure all the way through the solution process. They say it avoids creating dense matrices that would usually happen with a standard LU decomposition, which makes solving things much more efficient.

The paper's summary: Rosa: So what does the actual summary of this paper tell us about what they achieved? Basically, they’ve developed two specific algorithms to solve the problem of parallelization for these filters. They show that by using this block matrix view, you can get solutions that are faster than the previous best single-core implementations reported in their work.

Dev: The key result here is about how they tackle the sequential dependency depth. They adapted a technique called cyclic reduction to this block structure, which cuts the sequential dependency from O of N down to O of log2 N.

Taro: O of log2 N compared to O of N is a big deal when you’re dealing with long filter cascades, especially if you want real-time performance. That means the dependency doesn't grow as fast as it used to.

Rosa: Right. They also mention that the intermediate permutations needed to map those NL samples into the block tridiagonal structure cancel out exactly between successive sections in a cascade of biquads, so you only need one pair of permutations for the whole thing, which cuts down on overhead significantly.

Dev: So, to summarize what they did: they used a block matrix formulation to create a systematic way to expose parallelism, then used PH factorization to keep the structure sparse during solving and cyclic reduction to reduce the dependency depth from linear time complexity down toward logarithmic time complexity for the whole process.

The paper's improvements: Rosa: When we look at what they actually improved, it’s not just one thing. They have four main contributions they highlight. First, they present the block matrix problem formulation itself as a way to see parallelism at multiple levels of computation for general Mth order recursive filters.

Dev: Second is the PH factorization which, as I said earlier, avoids dense matrices while preserving sparsity during solving, which is a big improvement over standard LU decomposition methods.

Taro: And what about the cyclic reduction part? That’s where they really show the practical speedup in terms of dependency depth reduction to O of log2 N.

Rosa: Exactly. They also detail how this cyclic reduction adapts to the block tridiagonal structure and employs a division-free split when a certain parameter, called a1, is small, which helps avoid ill-conditioning issues that can pop up near poles at ninety degrees.

Dev: And they’ve got the performance numbers to back it up. They show that these multi-block algorithms reduce clock cycles per sample by up to ten times compared to just using scalar filtering methods on a single core, and they scale well on newer architectures.

Conclusion: Rosa: So wrapping things up, the implication is that this work presents what they claim are the fastest single-core IIR filter implementations reported so far. They show that block filtering and cyclic reduction give significant throughput improvements over standard sequential methods on commodity hardware, which is where most of us deal with.

Dev: The main point for anyone running real-time loops is that this means a massive boost to processing capabilities, translating directly into higher real-time performance for things like digital filtering in communication receivers or audio processing.

Taro: I just want to push on the practical side—the paper mentions that they maintained numerical accuracy, showing lower mean square error for most pole locations when using block filtering compared to scalar methods. That's important because speed is nothing if you get garbage results.

Rosa: True, accuracy matters too. So overall, this paper 'Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation' shows that by changing the mathematical view—from a simple difference equation to a banded block Toeplitz system—you can create algorithms that are both faster and more structured for parallel computation.

Dev: It’s about showing how to exploit the structure of these recursive filters better than before, using PH factorization and cyclic reduction to control complexity and dependency depth.

Taro: The work is available as an open-source C++ library, which means we can test this stuff outside of a pure academic setting, looking at how it behaves when the world misbehaves in a real deployment scenario.

Rosa: That's right. It’s not just theory; they’ve given us tools to try out this kind of speedup on actual hardware and see if these improvements translate to usable gains for our applications.

More episodes

← Home