Fast Direct High-Frequency MoM Solver Using Butterfly Algebra

Butterfly decomposition is a powerful method for compressing the Method of Moments impedance matrix at arbitrarily high frequency. It has been used to accelerate iterative solvers, achieving <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> log<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>, or “pseudo-linear” complexity per iteration. For direct solvers, pseudo-linear complexity has remained elusive. Presently, the lowest complexity achieved for high frequency impedance matrix factorization appears to be <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3/2</sup> log<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>, with an algorithm based on Butterfly decomposition. Further improvement requires an efficient Butterfly algebra, itself of pseudo-linear complexity. This paper introduces such an algebra, including summation, multiplication, concatenation and splitting of Butterfly decompositions. It is applied to matrix factorization, which is demonstrated both theoretically and through numerical examples to yield <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> log<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> complexity.