REVIEW 2 major objections 5 minor 1 cited by
Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation
T0 review · 2 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash
Pith's one-line read Cascaded IIR filtering can be made parallel by solving a block-tridiagonal reformulation with cyclic reduction, cutting dependency depth from O(N) to O(log2 N).
desk verdict A serious SIMD IIR filtering paper with real contributions, but the new cyclic-reduction algorithm divides by coefficients that vanish for common biquads, so the central speedup claim needs qualification and a fix. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the banded block-Toeplitz system A y = v; after a stride-N permutation it becomes block-tridiagonal, with entries that are scalar multiples of the L×L identity I and the lower-shift matrix R, turning the sample-level feedback into a nearest-neighbour block problem. Cyclic reduction eliminates alternating block rows at each of log2 N levels, updating coefficients e(i+1)=2f(i)-e(i)^2 and f(i+1)=f(i)^2 until a single banded block remains, then recovers eliminated blocks by back-substitution. The alternative PH factorization is a partial LU that preserves the sparse I/R form and solves the final 2L×2L terminal-block system with a Sklansky recursive-doubling scan of a 2×2 ma
What would settle it
Use a second-order section with a1=0, e.g., y[n]=x[n]+b1 x[n-1]+b2 x[n-2]-a2 y[n-2], and run cyclic reduction for N=4 blocks at any L. The first elimination in Eq. (41) divides by e(0)=a1=0; the outcome to look for is Inf/NaN output or a hang compared with the exact recurrence. More broadly, scan stable biquads for intermediate e(i) values near zero and check whether the output diverges; if no such case fails, the missing pivoting analysis is only a documentation gap.
Extended reading notes
Core claim
The recursive stage of a biquad filter is written as A y = v with A banded block-Toeplitz; a stride-N permutation makes A block-tridiagonal with off-diagonal blocks that are scalar multiples of identity and lower-shift matrices. Cyclic reduction halves the active block rows at each of log2 N levels, cutting sequential dependency depth from O(N) to O(log2 N). A partial LU (PH) factorization keeps the sparse structure and solves the two terminal blocks by recursive doubling. In a K-biquad cascade, the permutation after one section and the inverse before the next cancel exactly, so only one permutation/de-permutation pair is needed. Measurements validate the counts; a 16th-order filter reaches
Load-bearing premise
The cyclic-reduction coefficient update divides by e(i), which starts as a1 and evolves as e(i+1)=2f(i)-e(i)^2; if a1=0 or any intermediate e(i) becomes zero or very small, the elimination is undefined or numerically unstable, and the paper provides no pivoting or fallback for that case.
Editorial extensions
If this is right
- Sequential dependency depth for a block group of N blocks drops from O(N) to O(log2 N) under cyclic reduction, so larger groups become progressively more pipeline-friendly instead of progressively more serial.
- For a K-biquad cascade, only one permutation/de-permutation pair is required, so per-biquad permutation overhead falls as 1/K and high-order cascades become nearly as efficient per section as a single biquad.
- Per-sample block-FMA cost approaches 6/L plus small correction terms for both PH and cyclic reduction, so wider SIMD registers translate almost directly into higher throughput at large block sizes.
- Cyclic reduction outperforms scalar, block, and PH filtering at large N in the measurements, while PH remains competitive at small N, giving a regime-dependent choice between the two algorithms.
- Exact block-level operation counts for every stage are derived and validated by cycle-accurate measurements on three CPU micro-architectures, making the comparative claims reproducible.
Reading between the lines
- Because the cyclic-reduction update divides by e(i) starting from e(0)=a1, an immediate extension is a pivoted or hybrid variant that falls back to PH factorization when a1 is zero or an intermediate e(i) is near zero; without such a variant the 8x claim applies only to biquads with nonzero e(i).
- The same stride-permutation-plus-cyclic-reduction recipe may extend to higher-order one-step recurrences, state-space IIR filters, or IIR filter banks, with the permutation-cancellation argument reapplied wherever sections are cascaded.
- The reported throughput is for batched single-core SIMD processing; real-world low-latency audio or control use depends on how the block-group delay of NL samples trades against the reduced dependency depth, a trade-off the paper does not quantify.
- A testable extension is to verify the exact permutation cancellation in floating point for a long cascade (K≥8): algebraic cancellation is exact, but rounding may break it, and if it does, the promised amortization would need error analysis.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper presents a block-matrix reformulation of cascaded second-order IIR (biquad) filters. The authors permute a group of NL samples with a stride-N permutation to obtain a block-tridiagonal system whose blocks are scalar multiples of identity and shift matrices. They propose two solvers: a partial LU (PH) factorization that preserves sparsity and uses Sklansky recursive doubling for the terminal blocks, and a cyclic reduction solver that halves the system at each level, reducing the sequential dependency depth from O(N) to O(log2 N). They also show that in a cascade of K biquads the intermediate permutation/de-permutation pairs cancel, leaving only one pair for the whole cascade. Exact block-FMA and shuffle counts are derived and compared with cycle-accurate measurements on Haswell, Skylake, and Meteor Lake, with reported speedups of up to 10x over scalar filtering and about 8x over scipy.signal.sosfilt for a 16th-order filter.
Significance. The contribution is potentially significant for high-throughput DSP on commodity SIMD CPUs. The paper provides explicit block-level operation counts, a derivation of the block-tridiagonal structure, a new application of cyclic reduction to recursive filtering, and an open-source implementation with raw measurement data. The cascade permutation cancellation is a useful practical insight. If the cyclic reduction algorithm were generally applicable and numerically stable, the reported O(log N) dependency depth and the measured throughput improvement would be a valuable result. However, the algebraic breakdown for a subset of valid biquads and the absence of numerical error analysis currently limit the strength of the central claim.
major comments (2)
- [Section VI-C, Eq. (41)] The cyclic-reduction coefficient updates divide by e(i): d(i) = -f(i)^2/e(i), c(i) = e(i) - f(i)/e(i), with e(0)=a1 and e(i+1)=2f(i)-e(i)^2. For a valid stable biquad with a1=0 (e.g., y[n]=x[n]-a2 y[n-2], |a2|<1), e(0)=0 and c(0), d(0) are undefined. For a biquad with poles at 45 degrees (r<1), a1^2=2a2, so e(1)=0 and the level-1 recovery fails. The paper gives no pivoting strategy, alternative recovery formula, or fallback, and does not restrict the coefficient set. Thus the general statement that cyclic reduction achieves O(log2 N) dependency depth for cascaded biquads is unsupported; the algorithm is exact only when all intermediate e(i) are nonzero. This should be fixed or qualified.
- [Section VIII / Conclusion] The final section claims the library combines 'numerical accuracy with high throughput,' but the paper reports no numerical error measurements or stability analysis. The division by e(i) in Eq. (41) can magnify rounding errors when e(i) is nonzero but small (e.g., near the 45-degree pole locus), and the coefficient recurrence e(i+1)=2f(i)-e(i)^2 may produce large intermediate values. Without an error analysis or at least a comparison against a double-precision direct-form reference on representative biquads, the accuracy claim is unsupported. For a filtering paper, this is a substantive gap that should be addressed before publication.
minor comments (5)
- [Section V] Typo: 'separates nturally' should be 'separates naturally'.
- [Abstract] 'A VX2' should be 'AVX2'.
- [Section VI-C and Section VII-A] The cyclic reduction description assumes N is a power of two (log2 N levels), and the permutation procedure assumes N is a multiple of L. These constraints should be stated explicitly, along with the behavior for non-power-of-two N (e.g., padding).
- [Section VIII] Figures 4-8 are not included in the manuscript text provided for review, so the measured curves and the claimed 10x/8x speedups cannot be inspected. Please include the actual figures and, ideally, error bars or standard deviations for the timing measurements.
- [Section V-A and Table I] Equation (16) says the non-recursive stage costs 2N block FMAs plus 3 scalar FMAs, while Table I lists it as 2N+3 block FMAs. The aggregation of scalar FMAs into block FMAs should be clarified.
Circularity Check
No significant circularity: the O(log N) derivation follows from block elimination and measured speedups are independent.
full rationale
The paper's central derivation is self-contained algebra on the block-tridiagonal system Ay=v. Cyclic reduction eliminates alternating blocks using the arithmetic shown in Eqs. (34)-(38), yielding the coefficient recurrences in Eq. (41); the O(log2 N) sequential depth follows directly from halving the block count at each reduction level and is counted in Table III, not fitted or imported from the conclusion. The PH factorization similarly derives its terminal 2x2 scan recurrence (28)-(31) from the same system and then applies a standard Sklansky scan. Operation counts in Tables I and III are closed-form sums of per-stage block FMAs and shuffles, and the experimental section validates those predictions against cycle-accurate hardware counters rather than using measurements to infer the complexity. The scipy.signal.sosfilt comparison is an external benchmark. Self-citations are contextual: [21] provides the first-order particular/homogeneous decomposition that the paper explicitly extends to second-order sections, and [23] is one of several related SIMD/cascade studies cited in the introduction; no load-bearing claim rests solely on a self-citation or on an imported uniqueness theorem. The division by e(i) in Eq. (41) is a genuine numerical robustness gap (e.g., a1=0 or an intermediate e(i)=0 is not pivoted or handled), but that is an algorithmic failure mode, not circularity: the derivation does not assume the result it claims to establish. No step reduces a predicted quantity to a fitted input by construction, and no known empirical pattern is merely renamed as a derivation.
Assumptions & free parameters
free parameters (2)
- Block size L =
4 or 8 in experiments
- Number of blocks N =
varies; optimum near N=64 at NL=512 in experiments
assumptions (4)
- standard math The matrices A and B in (5)/(10) are invertible under the recurrence formulation.
- ad hoc to paper Cyclic reduction requires e(i) != 0 for the divisions in Eq. (41).
- domain assumption The SIMD execution model maps one block FMA to one packed instruction over L samples and treats shuffles as unit-cost operations.
- domain assumption In a cascade, each biquad preserves the stride-N permuted layout exactly, so intermediate permutations cancel.
Cite this review
Pith. "Pith review of Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation." pith.science (2026). https://pith.science/paper/A3P6NY6M
@misc{pith2026260714054,
author = {Pith},
title = {Pith review of: Fast Cascaded Recursive Filtering via a Block-Matrix Reformulation},
year = {2026},
howpublished = {\url{https://pith.science/paper/A3P6NY6M}},
note = {Machine review of arXiv:2607.14054}
}
abstract
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 and introduces 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 parallel algorithms are developed for the recursive solution: a partial LU (PH) factorization that preserves the sparse block structure and a cyclic reduction that is applied to recursive filtering, to the best of our knowledge, for the first time. It reduces the sequential dependency depth from $\mathcal{O}(N)$ to $\mathcal{O}(\log_2 N)$. For a cascade of $K$ biquads, the intermediate permutations between successive sections cancel exactly, so that only a single permutation/de-permutation pair is required for the entire cascade, eliminating $2(K{-}1)$ redundant stages. Exact block-level operation counts are derived for every algorithmic stage and validated against cycle-accurate measurements on three Intel 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 618 MS/s -- an $8\times$ throughput improvement over scipy.signal.sosfilt.
Figures
Figures from the paper (3 more)
Forward citations
Cited by 1 Pith paper
-
Parallel Cascaded Recursive Filtering on Multi-Core CPUs and GPUs
Superposition plus divide-and-conquer cyclic reduction remove inter-group IIR state serialization, yielding ~2.4 GS/s multi-core streaming and up to 38.2 GS/s GPU batched throughput near the memory roof.
Reference graph
Works this paper leans on
-
[1]
Advanced methods for I/Q imbalance compensation in communication receivers,
M. Valkama, M. Renfors, and V . Koivunen, “Advanced methods for I/Q imbalance compensation in communication receivers,”IEEE Transactions on Signal Processing, vol. 49, no. 10, pp. 2335–2344, 2001
2001
-
[2]
Multi-channel IIR filtering of audio signals using a GPU,
J. A. Belloch, B. Bank, L. Savioja, A. Gonzalez, and V . V ¨alim¨aki, “Multi-channel IIR filtering of audio signals using a GPU,” in2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2014, pp. 6692–6696
2014
-
[3]
GPU-efficient recursive filtering and summed-area tables,
D. Nehab, A. Maximo, R. S. Lima, and H. Hoppe, “GPU-efficient recursive filtering and summed-area tables,”ACM Trans. Graph., vol. 30, no. 6, p. 1–12, Dec. 2011
2011
-
[4]
An exploration on competent video processing architectures,
P. R. P. Tammana and B. Penumutchi, “An exploration on competent video processing architectures,” in2023 International Conference for Advancement in Technology (ICONAT), 2023, pp. 1–6
2023
-
[5]
Fast fourier transform method of computing difference equations and simulating filters,
H. Helms, “Fast fourier transform method of computing difference equations and simulating filters,”IEEE Transactions on Audio and Electroacoustics, vol. 15, no. 2, pp. 85–90, 1967
1967
-
[6]
A note on digital filter synthesis,
B. Gold and K. Jordan, “A note on digital filter synthesis,”Proceedings of the IEEE, vol. 56, no. 10, pp. 1717–1718, 1968
1968
-
[7]
Digital filtering via block recursion,
H. V oelcker and E. Hartquist, “Digital filtering via block recursion,” IEEE Transactions on Audio and Electroacoustics, vol. 18, no. 2, pp. 169–176, 1970
1970
-
[8]
Digital filters with poles via the FFT,
R. Read and J. Meek, “Digital filters with poles via the FFT,”IEEE Transactions on Audio and Electroacoustics, vol. 19, no. 4, pp. 322–323, 1971
1971
Show all 34 references
-
[9]
Fast convolution for recursive digital filters,
J. Meek and A. Veletsos, “Fast convolution for recursive digital filters,” IEEE Transactions on Audio and Electroacoustics, vol. 20, no. 1, pp. 93–94, 1972
1972
-
[10]
Block implementation of digital filters,
C. Burrus, “Block implementation of digital filters,”IEEE Transactions on Circuit Theory, vol. 18, no. 6, pp. 697–701, 1971
1971
-
[11]
Block realization of digital filters,
——, “Block realization of digital filters,”IEEE Transactions on Audio and Electroacoustics, vol. 20, no. 4, pp. 230–235, 1972
1972
-
[12]
High speed recursive digital filter realization,
H. H. J. LOOMIS and B. SINHA, “High speed recursive digital filter realization,”Circuits, systems, and signal processing, vol. 3, no. 3, pp. 267–294, 1984
1984
-
[13]
Fast recursive filtering with multiple slow processing elements,
H.-H. Lu, E. Lee, and D. Messerschmitt, “Fast recursive filtering with multiple slow processing elements,”IEEE Transactions on Circuits and Systems, vol. 32, no. 11, pp. 1119–1129, 1985
1985
-
[14]
Efficient multi-processor implementation of recursive digital filters,
W. Sung and S. Mitra, “Efficient multi-processor implementation of recursive digital filters,” inICASSP ’86. IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 11, 1986, pp. 257–260
1986
-
[15]
Multiprocessor implementation of digital filtering algorithms using a parallel block processing method,
W. Sung, S. Mitra, and B. Jeren, “Multiprocessor implementation of digital filtering algorithms using a parallel block processing method,” IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 1, pp. 110–120, 1992
1992
-
[16]
Recursive filtering on SIMD architectures,
R. Schaffer, M. Hosemann, R. Merker, and G. Fettweis, “Recursive filtering on SIMD architectures,” in2003 IEEE Workshop on Signal Processing Systems (IEEE Cat. No.03TH8682), 2003, pp. 263–268
2003
-
[17]
Implementation of recursive digital filters into vector SIMD DSP architectures,
J. Robelly, G. Cichon, H. Seidel, and G. Fettweis, “Implementation of recursive digital filters into vector SIMD DSP architectures,” in 2004 IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 5, 2004, pp. V–165
2004
-
[18]
On Enhancing SIMD-Controlled DSPs for Performing Recursive Filtering,
M. Hosemann, G. Fettweis, S. Vassiliadis, A. Pimentel, A. D. Pimentel, and S. Vassiliadis, “On Enhancing SIMD-Controlled DSPs for Performing Recursive Filtering,” inComputer Systems: Architectures, Modeling, and Simulation, ser. Lecture Notes in Computer Science. Germany: Spri...
2004
-
[19]
Recursive filtering on a vector DSP with linear speedup,
M. van der Horst, K. van Berkel, J. Lukkien, and R. Mak, “Recursive filtering on a vector DSP with linear speedup,” in2005 IEEE International Conference on Application-Specific Systems, Architecture Processors (ASAP’05), 2005, pp. 379–386
2005
-
[20]
Parallelization of IIR filters using SIMD extensions,
R. Kutil, “Parallelization of IIR filters using SIMD extensions,” in2008 15th International Conference on Systems, Signals and Image Processing, 2008, pp. 65–68
2008
-
[21]
SIMD processor based implementation of recursive filtering equations,
J. Ahn, H. Chang, J. Cho, and W. Sung, “SIMD processor based implementation of recursive filtering equations,” in2009 IEEE Workshop on Signal Processing Systems, 2009, pp. 087–092
2009
-
[22]
Multi-core and SIMD architecture based implementation of recursive digital filtering algorithms,
D.-h. Lee and W. Sung, “Multi-core and SIMD architecture based implementation of recursive digital filtering algorithms,” in2010 IEEE International Conference on Acoustics, Speech and Signal Processing, 2010, pp. 1550–1553
2010
-
[23]
Accurate and efficient implementations of recursive filtering based on SIMD and cascaded form,
H. Zhai and B.-P. Paris, “Accurate and efficient implementations of recursive filtering based on SIMD and cascaded form,” in2024 IEEE 14th Annual Computing and Communication Workshop and Conference (CCWC), 2024, pp. 0001–0007
2024
-
[24]
A. V . Oppenheim and R. W. Schafer,Discrete-time signal processing, 3rd ed. Upper Saddle River, NJ: Prentice Hall, 2010
2010
-
[25]
Cyclic reduction – history and applications,
W. Gander and G. H. Golub, “Cyclic reduction – history and applications,” inProceedings of the Workshop on Scientific Computing, 1997, pp. 1–15
1997
-
[26]
A parallel algorithm for the efficient solution of a general class of recurrence equations,
P. M. Kogge and H. S. Stone, “A parallel algorithm for the efficient solution of a general class of recurrence equations,”IEEE Transactions on Computers, vol. C-22, no. 8, pp. 786–793, 1973
1973
-
[27]
Single-pass parallel prefix scan with decoupled look-back,
D. Merrill and M. Garland, “Single-pass parallel prefix scan with decoupled look-back,” NVIDIA Corporation, Tech. Rep. NVR-2016- 002, Mar. 2016
2016
-
[28]
Conditional-sum addition logic,
J. Sklansky, “Conditional-sum addition logic,”IRE Trans. Electron. Comput., vol. EC-9, no. 2, pp. 226–231, 1960
1960
-
[29]
A regular layout for parallel adders,
Brent and Kung, “A regular layout for parallel adders,”IEEE Transactions on Computers, vol. C-31, no. 3, pp. 260–264, 1982
1982
-
[30]
Fast scan algorithms on graphics processors,
Y . Dotsenko, N. K. Govindaraju, P.-P. Sloan, C. Boyd, and J. Manferdelli, “Fast scan algorithms on graphics processors,” inProceedings of the 22nd Annual International Conference on Supercomputing, New York, NY , USA, 2008, pp. 205–213
2008
-
[31]
Vector class library,
A. Fog, “Vector class library,” https://github.com/vectorclass/version2.git, 2004
2004
-
[32]
Software optimization resources,
——, “Software optimization resources,” https://www.agner.org/optimize, 2025
2025
-
[33]
sosfilt documentation,
SciPy, “ sosfilt documentation,” https://docs.scipy.org/doc/scipy/ reference/generated/scipy.signal.sosfilt.html
-
[34]
SciPy 1.0: Fundamental algorithms for scientific computing in Python,
P. Virtanenet al., “SciPy 1.0: Fundamental algorithms for scientific computing in Python,”Nature Methods, vol. 17, no. 3, pp. 261–272, 2020
2020
Reviewed August 2, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.