When does the real part of butterfly factorizations preserve structure?

Why the real part of a butterfly product was unclear

Fast transforms such as the Discrete Cosine Transform are often written as the real part of a product of complex-valued structured sparse matrices called Kronecker-sparse factors. The same kind of product underlies square dyadic butterfly and monarch matrices, which are known to represent many fast transforms efficiently. What had not been settled is whether taking the real or the imaginary part of such a product still yields a product of Kronecker-sparse factors, and with real-valued entries.

The practical stake is numerical format. Low-precision float formats on GPUs are not currently available for complex numbers, so a transform whose implementation relies on complex-valued Kronecker-sparse factors cannot use them. If the real part of the factorization were itself Kronecker-sparse and real-valued, those transforms could be implemented in low precision. The paper states that this question had not been addressed in the literature.

Kronecker-sparse factors and the architecture that chains them

A Kronecker-sparse factor of pattern (a, b, c, d) is a matrix whose support is contained in the support of I_a ⊗ 1_{b×c} ⊗ I_d, where 1_{b×c} is the b×c matrix of all ones and I denotes an identity matrix. The pattern fixes where nonzeros may sit; the entries themselves are free. A butterfly factorization is a product K_1 ··· K_L in which each K_ℓ is Kronecker-sparse with its own pattern, and the tuple of patterns is called the architecture of the factorization.

Two families illustrate why this matters. Square dyadic butterflies, the n×n matrices with n = 2^L behind transforms such as the FFT and the Fast Walsh-Hadamard Transform, factor as K_1 ··· K_L with K_ℓ of pattern (2^{ℓ−1}, 2, 2, 2^{L−ℓ}). Monarch factorizations used for weight matrices in transformers express an m×n matrix as a product of two Kronecker-sparse factors with patterns (1, p, q, m/p) and (q, m/p, n/q, 1), assuming p and q divide m and n respectively.

Taking the real part first breaks the sparse pattern

For a single factor (L = 1), the real and imaginary parts inherit the same pattern, because being Kronecker-sparse depends only on the support. The difficulty appears from L ≥ 2. Simple linear algebra rewrites Re(K_1 ··· K_L) as a product of L matrices, but those matrices are built from the real and imaginary parts of the original factors and are no longer Kronecker-sparse. The paper illustrates this with the support of the last factor when the pattern is (2, 2, 2, 3).

So the real part of a butterfly product is always expressible as some product of L matrices, but not automatically as a product of Kronecker-sparse ones. The gap is exactly what the paper closes.

Permutations recover a Kronecker-sparse factorization

The fix is to insert permutation matrices between the factors. For any permutation matrices P_2, …, P_L, the product K_1 ··· K_L equals a product of permuted factors: the first becomes K_1 P_2ᵀ, the middle ones become P_ℓ K_ℓ P_{ℓ+1}ᵀ, and the last becomes P_L K_L. The question then becomes whether permutations and maximally sparse patterns can be chosen so that each permuted factor is Kronecker-sparse.

The paper targets specific patterns for the permuted factors, guided by counting nonzeros per row and column. For example, the first factor has twice as many columns as the original while the sparsity of each column is unchanged. The targeted patterns are (a_1, b_1, 2c_1, d_1) for the first factor, (a_L, 2b_L, c_L, d_L) for the last, and (a_ℓ, 2b_ℓ, 2c_ℓ, d_ℓ) in between.

A chainability condition decides when structure survives

Under a choice of permutation matrices, the paper gives a necessary and sufficient condition on the factors for the real or imaginary part of a product of Kronecker-sparse factors to remain a product of Kronecker-sparse factors. When the architecture satisfies this chainability condition, the real part admits a Kronecker-sparse factorization with the new architecture (π′_1, …, π′_L) defined by the targeted patterns.

The same argument covers the imaginary part, since Im(K_1 ··· K_L) equals Re((−j K_1) ··· K_L) and j K_1 is Kronecker-sparse with the same pattern as K_1. More generally it holds for Re(z K_1 ··· K_L) for any complex z. The paper also notes that the chainability condition yields error guarantees on the Kronecker-sparse factorizations performed by the earlier factorization algorithms, which it describes as a significant practical advantage.

DCT, DST and DHT become fully real-valued factorizations

The concrete payoff is a fully real-valued Kronecker-sparse implementation of the DCT, DST and DHT when the dimension is a power of two. The square dyadic butterfly factors appearing in the FFT, and the monarch factors, form a chainable architecture. The DCT and DST matrices can be written as L Re(D F) R, where L and R are real-valued, D is diagonal, and F is a DFT matrix.

Writing F = B P, with B a complex matrix having a square dyadic butterfly factorization and P the bit-reversal permutation, the DCT and DST take the form L Re(D B) P R, and D B still has a square dyadic butterfly factorization. Because the DHT is a sum of the DCT and the DST, it similarly writes as L Re((D_C + D_S) B) P R and admits a Kronecker-sparse factorization for the same reasons. The paper states that this real-valued factorization of the three transforms is, to its knowledge, new in the literature.

What the timing experiment does and does not show

The paper reports an experiment measuring inference time for the DCT applied to a vector x in R^{n×b}, where b is the batch size, using the real-valued Kronecker-sparse factorization. The batch setting is the relevant one in practice: the DCT is rarely applied to a single vector but to large batches, as in image compression standards such as JPEG, which apply it to every 8×8 block of an image, and in audio coders, which apply it to every frame of a signal. The reported plot spans n from 10^2 to 10^4 with time in seconds on a logarithmic scale.

The experiment is a timing measurement of one transform under one implementation, not a comparison against alternative factorizations, and the packet does not report the numerical values behind the curve. The code is available in the supplementary material, and the result has been implemented in the Python library lazylinop for designing efficient algorithms for these transforms.

Where the guarantee applies and where it stops

The guarantee is conditional, not universal. It requires the architecture to be chainable, and it is stated under a specific choice of permutation matrices; the paper describes the condition as necessary and sufficient in that setting. The real-valued representation of the DCT, DST and DHT is established for dimensions that are powers of two, which is the regime where the square dyadic butterfly architecture applies.

The low-precision GPU motivation is an opening rather than a demonstrated outcome: the paper presents the real-valued factorization as opening new avenues for efficient GPU implementations using low-precision numerical format, and separately notes that irregular sparsity patterns are not well-suited to GPUs and make theoretical speed-ups hard to realize in practice, while recent block-structured or dedicated-kernel work is starting to close that gap. The timing experiment measures the DCT alone, so it does not by itself establish a low-precision speed-up.

The condition, not the transform, is the reusable result

The most transferable output of this paper is the chainability condition on the architecture, because it tells you in advance whether taking the real or imaginary part of a Kronecker-sparse product will preserve the structure, rather than requiring a case-by-case check. The DCT, DST and DHT are the worked examples that satisfy it, and they are the cases where the payoff is concrete: a real-valued Kronecker-sparse factorization at power-of-two dimensions, which is what makes the low-precision format question relevant at all.

For a reader deciding whether this result applies to a given transform, the operative test is therefore the architecture, not the transform name. If the factorization chains in the required sense, the real part stays Kronecker-sparse and the real-valued implementation follows; if it does not, the pre-factorization still exists but the sparse structure is lost, and the low-precision route is not available on these grounds.

Sources used in this answer