⚡ electrical engineering

Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation

This paper introduces a block-matrix reformulation of cascaded second-order IIR filters that enables highly parallel processing via partial LU factorization and cyclic reduction, achieving up to a 10-fold speedup over traditional scalar methods by reducing sequential dependency depth from $\mathcal{O}(N)$ to $\mathcal{O}(\log_2 N)$ .

Original authors: Haotian Zhai, Bernd-Peter Paris

Published 2026-07-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Haotian Zhai, Bernd-Peter Paris

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to listen to a favorite song on a very old, slightly broken radio. Sometimes the sound is fuzzy, or there's a weird hum. To fix this, engineers use special mathematical tools called filters. Think of a filter like a sieve for sound: it lets the good, clear notes pass through while catching the unwanted static and noise. There are two main ways to build these sieves. One way is like stacking a huge number of simple strainers (called FIR filters); it's very reliable but requires a lot of work to move the water through. The other way, which this paper focuses on, is like using a clever, self-correcting loop (called an IIR or recursive filter). This loop is incredibly efficient, needing far fewer parts to get the same clean sound.

However, there's a catch with the efficient loop: it's a "serial" process. Imagine a line of people passing a bucket of water down the line. Person A can't pass the bucket to Person B until they have filled it, and Person B can't pass it to Person C until they have filled theirs. You can't speed this up by just adding more people because everyone has to wait for the person before them. In the world of computers, this "waiting" creates a bottleneck that slows everything down, especially when we want to process massive amounts of data, like in real-time video or high-speed internet. The big question has always been: How do we make this efficient, self-correcting loop run faster by doing many things at once, without breaking the chain of cause-and-effect?

This paper, titled "Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation," tackles that exact problem. The authors, Haotian Zhai and Bernd-Peter Paris, realized that while we can't speed up the bucket line one person at a time, we can change the rules of the game entirely. Instead of looking at the data as a long line of individual samples, they decided to grab a whole block of samples at once and treat them like a single, complex puzzle.

They discovered a clever way to rearrange the data, like shuffling a deck of cards into a specific pattern, which turns the messy, waiting line into a neat, organized structure. Once the data is in this new shape, they applied two different "super-speed" strategies to solve the puzzle:

The "Partial LU" Strategy (PH Factorization): This method is like a smart assembly line that keeps the puzzle pieces in their neat, sparse boxes. It breaks the problem down into a "specific" part (what the input looks like) and a "general" part (how the system reacts), solving them in a way that avoids the heavy, messy math that usually slows things down.
The "Cyclic Reduction" Strategy: This is the real showstopper. Imagine you have a line of 1,000 people passing buckets. Instead of waiting for the whole line, this method pairs them up, solves the problem for the pairs, then pairs up the results, and keeps doubling the speed of the solution until the whole line is done in just a few steps. It's like folding a giant piece of paper in half over and over until it's tiny. This technique, which the authors applied to this type of filtering for the first time, shrinks the "waiting time" from being proportional to the number of samples to being proportional to the logarithm of the number of samples. In plain English, if you double the amount of data, you don't double the time it takes; you barely add any time at all.

The paper also solved a tricky problem with "cascaded" filters. Usually, when you stack multiple filters together (like stacking several sieves), you have to shuffle the data back and forth between each one, which wastes time. The authors showed that with their new method, the shuffling required between the filters cancels itself out perfectly. It's like if you had to change your shoes every time you walked through a door, but then realized the doors were arranged so that you never actually had to stop to change shoes at all.

To prove this wasn't just a cool idea on paper, the authors tested it on real computer chips (specifically Intel processors). They found that for a complex 16th-order filter, their new "Cyclic Reduction" method was about 8 times faster than the standard software people use today (like the scipy.signal.sosfilt tool) and up to 10 times faster than the old, slow way of processing data one sample at a time. On a modern computer chip, this new method could process over 618 million samples per second.

The authors are very confident in these results because they measured the actual clock cycles on the hardware, not just simulated them. They showed that while the "Partial LU" method is great for smaller amounts of data, the "Cyclic Reduction" method shines when you have huge amounts of data to process, making it a game-changer for high-speed applications like real-time video processing or advanced communication systems. They even made their code open-source so others can use it, marking a significant step forward in making these powerful filters both fast and practical for everyday technology.

Technical Summary: Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation

Problem Statement
Recursive (IIR) filters implemented as cascaded second-order sections (biquads) are the standard for digital signal processing due to their design generality and robustness against coefficient quantization. However, the inherent sample-to-sample feedback dependency creates a sequential bottleneck that prevents efficient parallel computation. While previous research has explored parallelizing direct-form filters or using FFT-based approximations, these approaches either fail to guarantee stability or do not address the specific complexities introduced by cascading multiple biquads. Existing parallel algorithms largely ignore the cascade structure, treating filters as single direct-form entities, which leaves the computational overhead of cascading unaddressed.

Methodology
The authors propose a block-matrix reformulation of the cascaded second-order IIR filter to expose parallelism at both intra-block and inter-block levels. The core methodology involves:

Matrix Reformulation: The biquad difference equation is cast as a banded block-Toeplitz linear system. A stride- $N$ permutation is applied to a group of $NL$ samples, transforming the system into a block-tridiagonal structure. The entries of this matrix are scalar multiples of identity ( $I$ ) and lower shift ( $R$ ) matrices.
Parallel Solvers: Two parallel algorithms are developed to solve the resulting recursive stage:
- PH Factorization (Partial LU): This method preserves the sparse block structure of the system by avoiding the dense matrices typically generated in standard LU decomposition. It utilizes a particular-homogeneous decomposition where the particular solution is computed via forward substitution, and the homogeneous correction is applied using the terminal blocks. The terminal blocks are solved using a block-level recursive doubling (Sklansky construction) to reduce sequential depth.
- Cyclic Reduction: Adapted here for the first time to recursive filtering, this technique systematically eliminates alternating blocks to halve the system size at each level. This reduces the sequential dependency depth from $O(N)$ to $O(\log_2 N)$ .
Cascade Optimization: For a cascade of $K$ biquads, the authors demonstrate that the stride- $N$ permutation required at the output of one section and the inverse permutation at the input of the next cancel exactly. Consequently, only a single permutation at the start and a single de-permutation at the end of the entire cascade are required, eliminating $2(K-1)$ redundant stages.

Key Contributions

Block-Matrix Problem Formulation: A systematic algebraic framework casting the second-order recursive filter as a banded block-Toeplitz system, enabling the application of multi-block filtering algorithms.
PH Factorization: An extension of the particular/homogeneous decomposition to second-order sections, utilizing recursive doubling to solve terminal blocks while maintaining sparse block structures.
Cyclic Reduction for IIR: The first application of cyclic reduction to recursive filtering, achieving a sequential dependency depth of $O(\log_2 N)$ compared to the $O(N)$ depth of standard factorization methods.
Cascade Cost Amortization: A proof that intermediate permutations in cascaded biquads cancel out, significantly reducing the per-biquad overhead as the filter order increases.
Complexity Analysis and Validation: Exact block-level operation counts (FMA and shuffle operations) are derived and validated against cycle-accurate measurements on three Intel micro-architectures (Haswell, Skylake, Meteor Lake).

Experimental Results
The proposed algorithms were implemented in C++ using SIMD vector instructions (AVX2) and evaluated on a 16th-order cascaded IIR filter system.

Performance Gains: On a single Meteor Lake core, the cyclic reduction algorithm achieved a throughput of approximately 618 MS/s (Million Samples per second). This represents an 8× throughput improvement over the standard scipy.signal.sosfilt implementation (which runs at ~77 MS/s) and up to a 10× reduction in clock cycles per sample compared to scalar filtering.
Scalability: Both PH factorization and cyclic reduction scale favorably on newer architectures. PH factorization offers lower latency for smaller sample sizes, while cyclic reduction achieves superior throughput for large sample sizes due to its reduced sequential depth.
Efficiency: The multi-block algorithms successfully reduced the clock cycles per sample by up to 10× compared to scalar filtering, with the cyclic reduction method showing the best performance at large block sizes ($NL = 512$).

Significance and Claims
The paper claims to fill a critical gap in the literature by providing a parallel algorithm specifically designed for the cascaded second-order realization of IIR filters, which is the dominant implementation strategy in practice. By reformulating the problem into a block-tridiagonal system, the authors expose parallelism that was previously inaccessible due to sequential dependencies.

The authors emphasize that this work constitutes the first part of a two-part study, focusing on algorithmic theory and single-core SIMD validation. They claim to have released the first open-source library providing parallel IIR filtering in the cascaded second-order form, combining numerical accuracy with high throughput on commodity hardware. The work is modest in its scope, noting that while it achieves significant single-core speedups, the companion paper will address multi-core and GPU implementations for high-throughput batched processing and low-latency real-time scenarios. The results confirm that the proposed methods effectively mitigate the sequential bottleneck inherent in recursive filtering without compromising the stability or design flexibility of the cascade form.

Technical Summary: Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation

More like this