WorksMathematics
Solver Performance of Accelerated MoM for Connected Arrays
Abstract
Simulating and developing large rectangularly shaped arrays with equidistant interspacing is challenging as the computational complexity grows quickly with array size. However, the geometrical shape of the array, appropriately meshed, leads to a multilevel Toeplitz structure in the RWG-based Method of Moment impedance matrix representation that can be used to mitigate the increased complexity. This paper develops, presents and compares two different accelerated solvers that both utilize the matrix structure to determine antenna properties. Both methods use a novel mesh-partitioning algorithm and its associated data representation, reducing storage and computational costs. The first solver is an iterative method based on multilevel fast Fourier transform to accelerate matrix multiplications. The second solver approach is based on an extension of a fast direct Toeplitz solver, adapted to a block-matrix structure. This fast direct solver is demonstrated to have close to machine epsilon accuracy. Both accelerated methods are evaluated on two different array element types, for arrays with up to 900 elements. The results are compared with conventional direct and iterative matrix solvers. Improvements are seen in both the time and required storage to solve the problem. The choice of the most efficient method depends on the residual thresholds in the iterative method, geometry of the element and frequency. Two different preconditioners for the iterative method are investigated to evaluate their performance. The two accelerated methods vastly outperform regular matrix inversion methods.
Introduction
METHODS for simulating finite-size periodic structures are used in a range of applications across multiple disciplines. Such structures, composed of a unit cell repeated over a finite grid, include array antennas [1], reconfigurable intelligent surfaces [2], and metasurfaces [3].
This paper focuses on the simulation of array antennas, which are key components in a wide range of applications. These applications include defense [4, 5, 6], communications [7, 8] and radio astronomy [9, 10] systems. A common trend across these areas is the transition to fully or partially digital arrays [6]. In a digital array, each element or sub-array incorporates radio-frequency (RF) amplification, followed by analog-to-digital (A/D) or digital-to-analog (D/A) conversion on receive or transmit, respectively. Time delays and amplitude weights are then applied in the digital domain, enabling flexible pattern control and multiple simultaneous beams [11]. These capabilities are critical for meeting growing demands on performance, adaptability, and multi-functionality [6, 8, 12].
However, simulating large-scale or complex array antennas remains a computational challenge, particularly as system sizes and operational requirements continue to increase. Full-wave solvers, which are commonly used to model such systems, encounter scalability issues as the number of elements increases or the design complexity grows. One option is to use unit cell methods to approximate array performance, but to fully utilize the capabilities of the array antenna requires the correct behavior of each separate element in the array [13, 14, 15, 16].
How to overcome the computational challenge of large problems is a well studied area, with several integral-based methods proposed [13, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]. The multilevel fast multipole algorithm (MLFMA) [17, 18] evaluates weak interactions for a group of elements using a multipole representation. Another method to reduce the complexity is adaptive cross-approximation (ACA) [19, 20] that finds low-rank approximations for the weak interactions in an adaptive manner. Neither MLFMA nor ACA assumes that the impedance matrix contains any structure and therefore works well on general problems. ACA has also been shown to work well for antenna arrays in combination with the characteristics basis function method [21].
An alternative to using ACA is to use hierarchical matrices [22]. In these matrices, the data is arranged in a binary tree structure and allows varying block sizes, with larger blocks away from the matrix diagonal represented by a low-rank approximation due to weaker inter-element interaction. Hierarchical matrix methods have been shown to accelerate the solution of integral equation problems [22, 23], and have also been used with Toeplitz structures [24].
Another approach is to solve the integral equation problem on a uniformly spaced grid, such as the precorrected fast Fourier transform method (pFFT) [25] and adaptive integral method (AIM) [26]. The periodicity of the grid then allows for a efficient solution of the problem via fast Fourier transform (FFT). Similar FFT accelerated methods for unconnected arrays [13, 27, 28] utilize the periodicity of the array, which gives the impedance matrix a multilevel block-Toeplitz structure. This structure allows for a fast matrix-vector multiplication which enables the problem to be solved fast using an iterative solver, while also reducing memory usage.
However, the methods in [13, 27, 28] are only for unconnected arrays, the elements in the array must be separated by air. This excludes e.g. ground planes and most metasurfaces. Brandt-Møller et al [29] recently presented a method that works for connected arrays by using the discontinuous Galerkin method and high order, quadrilateral basis functions. In [29], it is mentioned that their method should work for RWG basis function [30].
In [31] a novel decomposition method for array antennas with connected elements meshed with RWG basis functions is presented. That decomposition method is used in this paper to present a method to decompose and simulate antenna arrays efficiently. The method allows for the edges of array element meshes to overlap, assigning the current over the border to only one element without using a discontinuous Galerkin method. This comes with the feature that the border region of the array can be handled separately. These regions are not part of the Toeplitz structure. The full impedance matrix has the form
where is the multilevel Toeplitz-structured matrix of the array elements, is the impedance matrix of the border and is the interaction between the elements and the border.
In this paper, we describe and compare two different methods that use the structure (1) derived in [31] to accelerate the array simulation. The first approach uses a multilevel FFT (MLFFT) to create a block-diagonal representation of , similar to [13, 27, 28, 29]. This diagonalization allows for an accelerated multiplication in an iterative solver, while storing only the unique block matrices within . For better convergence in the iterative solver, we have implemented the preconditioner of [28] and a preconditioner similar to that of [32]. We also present a block variant of the Rybicki Toeplitz inversion given in [33]. This is a direct solver that can invert a 1-level block-Toeplitz matrix, in contrast to the MLFFT which can utilize all the levels of the multilevel structure of . Other similar methods may put requirements on the blocks in the block Toeplitz structure. For example [34] requires the block to be symmetric around both the primary and secondary diagonal. The Rybicki method presented in this paper works on invertible blocks with arbitrary structure.
The performance of the two presented methods is investigated by simulating two different array types of varying sizes and comparing the presented methods with conventional matrix inversions. The results show a definite performance improvement, both in time and scaling. Memory usage and especially memory scaling are improved by only saving the required blocks in . For an array antenna with columns and rows, the full size of in (1) scales as . As described in [31], for such a 2D array has an inherent multilevel block Toeplitz structure with two levels. On the top level the structure arises from identical interactions between rows of the array, and on the lower level from identical interactions between antenna elements within the rows. By utilizing one level of the structure in the Rybicki method, the required data to store is reduced to scale as . Furthermore, the scaling is reduced even further by utilizing both levels in the structure in the MLFFT method, down to . Both MLFFT and Rybicki are faster and more efficient than the conventional methods. Whether MLFFT or Rybicki is the most efficient choice depends on the simulated structure and the desired relative residual of the MLFFT method.
Both the methods presented are explained explicitly, with code for the MLFFT given in App. A and B and modifications to the Rybicki method in [33] given in Section III-D. We present a thorough analysis of convergence and investigate how array size, different types of antenna elements, meshing and frequency effect the efficiency of the presented solvers. While MLFFT is faster for certain problems, Rybicki has a very stable performance over frequency for a given mesh and array size.
The paper is organized as follows. § 2 describes how a multilevel block-Toeplitz is block diagonalized, enabling a low complexity matrix-vector multiplication. Section III describes the methods used for matrix inversions. Section IV describes how the methods in Section III are used to simulate an antenna array, and the methods used for comparison. In § 5 the results of the performance comparison is presented and discussed. The paper ends with conclusions.
Theory
The MLFFT solver is accelerated by using a fast multiplication described in § 2-B. This type of acceleration is used in several publications like [13, 27, 28, 29], but it is usually described in a rather condensed manner. In this section, we describe how the acceleration is implemented on a multilevel block-Toeplitz structure by starting with a scalar Toeplitz matrix, extend to the block-matrix case, and then introduce the one level and extend to the two level structure to give a thorough explanation of the theory behind the acceleration. This theory is used to derive the codes in Appendices A and B.
Multilevel block-Toeplitz structure
Multilevel block-Toeplitz structures, also called -level block-Toeplitz structures [35], with levels have the following structure. On the highest level , it is a block-Toeplitz structure:
If , each block is a multilevel block-Toeplitz matrix with levels. If , is here an unstructured matrix. The matrix is similar to the recursive block-Toeplitz matrix in [36], though in a recursive block-Toeplitz matrix the lowest level consists of Toeplitz matrices rather than unstructured matrices.
For finite periodic structures where each element has an identical mesh, the interaction between cells give this type of impedance matrix [27, 28, 29, 31]. The number of blocks on each level, , is defined by the problem. For a one dimensional array with antenna elements, which in turn are discretized to mesh cells, the impedance matrix is a 1-level block-Toeplitz matrix with and . Extending to a two dimensional array with elements gives a 2-level block-Toeplitz matrix, with , and , which is the case that is used throughout this paper.
Toeplitz Multiplication using DFT
A key property of a Toeplitz matrix, and by extension a multilevel block-Toeplitz matrix, is the fast multiplication via FFT as shown in [28], [29], [35, 36, 37]. This stems from the fact that a circulant matrix, , is diagonalized by the Discrete Fourier Transform (DFT), :
where is the vector consisting of the first column in . Using , where is the identity matrix, the product can be written as
A Toeplitz matrix is not circulant, but can be padded to create the circulant matrix. Denote the circulant matrix created from by . To show the procedure, consider the following example. Take
The circulant matrix is populated:
where are to be determined. Following the cyclic pattern in a circulant matrix, the missing entries follows as:
The matrix multiplication can now be evaluated by
Note that is here a zero vector of length 2 and a vector of unused values. To form , the first column of , take the first column of . Then, take the elements in first row of , except the first element, invert the order and append the the first column to create
That is, for a Toeplitz matrix of size , we only need to save values to carry out the multiplication. Further, the multiplication is carried out with computational complexity in if the DFT in (4) is replaced by the FFT.
Multiplication of multilevel Toeplitz Matrix using DFT
If the elements in and in § 2-B are replaced by block-matrices, it gives the single-level block matrices and which is defined analogously to (7). The multiplication in (8) is carried out in the same manner using the first block column of analogously to (9). The block column is a block vector, a block matrix with a single column of blocks. However, is not diagonalized by the regular DFT.
the regular DFT. But as shown in, e.g. [28], [38], it is block diagonalizable by a blockwise DFT. For a matrix structure of a 1D array with antenna elements, where each element is meshed with mesh cells, the 1-level block-wise DFT (1LDFT) is defined as
where is the DFT of size , is the Kronecker product, is the identity matrix of size and is an element of . The inverse 1LDFT is defined in the same manner, with replaced by .
With the 1LDFT, the multiplication can be carried out in two steps. First, create the first block column analogously to Section II-B:
where in (7) is replaced by the corresponding submatrix in (2). As each submatrix has dimension , the matrix has dimension .
Second, a block analogue to (4) is required. For a general level , the product can be written as
, where is the dimension of , denotes a block-diagonal matrix with block size and vectors and are padded versions of and . For the one dimensional array, , the vectors are defined as
where the desired product lies in the first elements of . Using (12) and (13) the matrix multiplication for can be carried out by only storing elements of the matrix.
As shown, operating on a 1-level block-Toeplitz structure is largely analogous to the scalar case. For a 2-level block-Toeplitz structure, some more consideration is required. The 2-level block-wise DFT (2LDFT) is defined similarly to the 1LDFT in (10):
where is the number of blocks on level 2. To create from , the blocks need to be rearranged. The Toeplitz matrix of level 2, , is structured as follows:
where are 1-level block-Toeplitz matrices.
This structure can, similar to creating , be used to create the block diagonalizable matrix :
which has a structure similar to (7) with replaced by . The first block column of , with blocks of size , is found as follows. For each , , form a block column as in (11). Construct the complete block column as
which gives the same structure as in [29], Figure 1. From this structure it can also be seen that the zero-padding of and becomes more complicated, also shown in [29]. Take the original vector and divide it into subvectors of length :
Figure 1. Antenna unit cell geometries, feed shown in red. (a) CSA unit cell from the side, mm and mm. The unit cell is mm mm seen from above. (b) bowtie unit cell from above, the bowtie is placed over a ground plane.
To perform the multiplication correctly, the vector needs to be padded as in (13), but first block wise on the first level and then padded on the second level:
where is a zero row-vector of length . The multiplication can now be performed using (12) with . The resulting has a similar structure to (19), but with unwanted data instead of zero vectors. Finally, can be extracted from positions of giving
Method
Method of Moments (MoM) gives a typical linear equation system on the form , where is an impedance matrix, is the unknown current and the excitation voltage. In this paper, an in-house MoM code is used. The code method to partition the matrix into a multilevel block Toeplitz structure is described in [31]. To find the unknown current, two different methods are presented in this work: one using the multiplication from § 2 accelerated by multilevel FFT (MLFFT) in an iterative solver, and one using a block generalization of the Rybicki method [33].
Multilevel FFT
To efficiently implement the ideas in II-C and enable an efficient matrix multiplication, 1LDFT and 2LDFT are replaced with MLFFT. Here, it is implemented in Matlab by performing an FFT over indices in the blocks. For a 1-level block-Toeplitz structure, it can be implemented as in Appendix A. The key observation here is that taking each th row of (10) and multiplying it with each th row of a vector just gives the DFT of those elements in , which can be saved in the corresponding rows of the output. This can be done for all sets of rows, giving the block-wise FFT. The block-wise FFT is applied column-wise and consists of FFTs of length and is applied on a block matrix on the form of (11) with length and width . Each FFT here has a computational complexity of . An FFT is applied for each of the set of rows, once per column over a total of columns, resulting in a total computational complexity of .
In a similar manner to defining a MLFFT for the 1-level block-Toeplitz structure, a MLFFT for a 2-level structure can be implemented considering two block indices instead of one as shown in Appendix B. For each of the columns, first apply FFTs of length , with complexity . Second, apply FFTs of length , complexity . The first operation dominates if and vice versa.
Preconditioner for MLFFT
Consider the array antenna described in § 1. Due to the weakly singular nature of the Green’s function, interactions over short electrical distances become very strong and interactions over long electrical distances become weak, leading to being an ill-conditioned matrix. Strong interactions are largely concentrated to the self interaction of elements and to neighboring elements, though this depends element geometry. The condition number of the problem can be improved by including a preconditioner in the matrix equation. In this paper, we use a left preconditioning strategy with the preconditioner , rewriting the problem as
where the goal is for to be better conditioned compared to .
One approach is to use an incomplete LU-decomposition (ILU) [39] on which gives a decomposition such that . Then, the preconditioner can be applied efficiently using back substitution. However, even if an incomplete LU of is cheaper than a regular LU, both and have the same size as . A way to address this is to use the MATLAB function ilu as it outputs the two matrices in a sparse matrix format to reduce the memory footprint. Even so, this approach yields a preconditioner that, to a large extent, counteracts the memory savings of (12).
A more memory efficient preconditioner has been demonstrated by Kindt et al. [28]. This preconditioner is a block-diagonal matrix, where each block is the self-interaction of one element in the matrix , which has already been computed as it is the block-diagonal part of in (1) on the lowest level. As the matrix is block diagonal, it can be inverted block wise. Further, as each block is identical, one LU-decomposition of is sufficient to apply the inverse of block wise. To cite [39]: ”For example, preconditioners can be derived from knowledge of the original physical problems from which the linear system arises”. With the preconditioner , we use the knowledge that is largely dominated by the strong block diagonal self-interaction. The matrix has elements.
This knowledge of the underlying problem can be extended to another block-diagonal preconditioner , similar to that of Zhai et al. [32]. A natural choice of sub-array in our method is one row of the matrix. Such a preconditioner consists of the block diagonal of , but on one level higher in the multilevel block-Toeplitz structure. Each block is a block-Toeplitz matrix which describes the self interaction of a row of elements in the array. The preconditioner can be applied in the same manner as , though the block is larger with elements.
The preconditioners and are defined for in (1). However, is only one, albeit the largest, part of . To account for the margin parts of , the full preconditioners and are defined as
where the index is either or . As the self interaction matrix of the border is small, its full LU-decomposition is used as a preconditioner for the border. The LU-decomposition of is applied in the same block-wise manner as above.
Iterative Inverse with Multiple Right Hand Sides
Given the fast multiplication procedure from § 2, the MLFFT in Section III-A and the preconditioner in Section III-B, the linear equation system can be solved using an iterative method. Here is an excitation vector corresponding to applying the desired excitation voltage to antenna port . This excitation vector is passed to GMRES in MATLAB together with a function for the multiplication and a function for applying the preconditioner in order to solve for , the excited current. This current can in turn be used to find the excited fields.
In addition to being a computationally complex problem, array antennas are often solved with the goal of the embedded element patterns (EEPs), i.e. to solve the matrix equation for every port excitation . A straightforward way to achieve this is to run the solver once for each element, but that scales with computational complexity of .
Instead of solving each element one by one, consider the problem on matrix form:
The MLFFT based multiplication works for multiplying with a matrix, but standard GMRES only handles vector multiplicands and vector right hand sides. As shown in [40], there are methods to extend the underlying Krylov subspace to represent matrices rather than vectors. But rather than using a rewritten GMRES, the global Krylov subspace may be achieved using vectorization. As shown in [37], (23) is equivalent to
where is the vectorization operator [37]. In MATLAB, the vectorization operator corresponds to reshaping to a matrix with one column, and the inverse by reshaping back to the original dimensions. This takes virtually no computational effort, as this reshaping only changes how MATLAB reads the variable from memory. As (23) and (24) are equivalent, the matrix multiplications can be performed as in (23). There is no need to explicitly form the huge matrix . Then the vectorized right hand side (RHS) of (24) can be passed to GMRES. The Krylov subspace created by GMRES will then consists of the vectorized matrices in the subspace of the global GMRES described in [40].
The Rybicki Method
The Rybicki method for a regular non-symmetric Toeplitz matrix is detailed in [33]. The Rybicki method is a bordering method [41], a recursive procedure that solves through a sequence of solutions that converge in the last step when . In our case is a matrix rather than a scalar as in [33]. We update the algorithm in [33] with respect to matrices. The underlying equations (25) to (30) corresponds to the key equations in [33 Ch. 2.8]`.
First, [33 eq. (2.8.19)] it is rewritten as
Similarly, rewrite [33 eq. (2.8.18)] as
[33 eq. (2.8.24)] as
and [33 eq. (2.8.23)] as
When considering [33 eq. (2.8.27)], the order in the multiplication is changed to take the non-comutability of matrices in to account by
Similarly, the order in [33 eq. (2.8.25)] is changed to
We observe that the obtained equations are almost identical to the scalar version, except for that iterated variable and the generator has exchanged place to respect the non-comutability of the matrices. With these modifications, the subroutine given by [33] can be rewritten to handle matrices with small changes to the code.
This rewritten Rybicki method works for a block-Toeplitz structure, but has not been modified to fully utilize the multilevel structure of . Here, this means that the Rybicki method is implemented on level 2, where there is a block-Toeplitz structure and each block, i.e. each element in , is a full block-Toeplitz matrix. Even so, this reduces the memory usage from the full matrix with elements down to a structure with elements. Note that this method works for any set of invertible , unlike e.g. [34] that has additional requirements on symmetry.
Including non-Toeplitz Blocks
As mentioned in § 1, the impedance matrix given by [31] contains non-Toeplitz structured blocks from the border of the array. Therefore, the two methods described in this section must be modified to include these blocks.
MLFFT: The MLFFT method is based on matrix multiplication, which can be performed blockwise. For a single RHS, partition the current vector and the excitation vector into the values on the array elements (denoted by ) and the values on the border (denoted by ). Then, multiply blockwise:
Multiplying with is accelerated as in § 2, while the smaller margin matrices and are multiplied using matrix multiplication.
Rybicki: The Rybicki method only works on a Toeplitz structure, i.e. the problem must be on the form . Here, Schur decomposition is used to rewrite the matrix equation to only invert , moving the border matrices and the right hand side. Once this matrix equation has been solved efficiently, the solution of the original problem can be found by a relatively small inversion.
Given the first row of blocks in (31), can be written as
Inserting this in the second row of blocks gives
Isolating gives
Let and and solve the problem
for . The currents can then be found using
a relatively small inversion, and
Array Simulation
To evaluate the performance of the different matrix inversion methods in Section III, two different types of array antennas are simulated: the Current Sheet Array (CSA) element of [15] illustrated in Figure 1a, and the bowtie element illustrated in Figure 1b. The CSA element is described in full in [15] including a full geometrical description. Here, the CSA is simulated at a low frequency of 1 GHz and a high frequency of 4 GHz, with 462 unknowns per element. The bowtie element has two variants. A wider, densely meshed element with and 1081 unknowns per element is simulated at 150 MHz and 225 MHz, and a narrower element with and 253 unknowns per element at 150 MHz.
For such that the full matrix can be saved in memory, the methods described in Section III are compared to inversion using mldivide, and using GMRES with a preconditioner. Note that the MLFFT methods in Section III also use GMRES, but with the here proposed more efficient MLFFT matrix multiplication.
Here, a simulation consists of:
read the mesh file of the antenna element,
define simulation parameters, e.g. array size and frequency,
create the unique sub-matrices of in (1) as described in [31],
(conditional) fill in a full matrix variant of (for mldivide or GMRES) or fill in the lowest Toeplitz level of (for the Rybicki method),
solve .
All simulations are run on a computer with an Intel Xeon Gold 5217 processor and 191 GB RAM.
By default in this publication, is a matrix where each column consists of zeros, except for the feeding edge of array element which is set to 1. The corresponding column of then contains the currents of the array from exciting the feeding point of element . By solving one element at a time, arbitrary array excitations can be calculated in post-processing via super-position.
Results
In order to investigate the performance of the presented methods, various array sizes with the different unit cell geometries were tested. The main metrics of interest is how fast the solvers are and how they scale with array size. The time to create the sub-matrices of is given as ”Con.” for construction. The reference solutions solved using mldivide and GMRES are shortened as ”mld” and ”G”, their solution times include filling in the full matrix with the data from the construction step.
The Rybicki solver, here shortened as ”R”, also includes the time to fill in the matrices on level 1, whereas the MLFFT solvers work with no fill-in. The MLFFT solver is investigated using three different configurations: M1, M2 and M3. in Section III-B, two different preconditioners are defined; the smaller and the larger . Configuration M1 uses a preconditioner with a vectorized RHS, M2 a preconditioner with vectorized RHS and M3 a preconditioner that solves the RHS column by column. The vectorization of the RHS is described in Section III-C.
The time to solve the CSA scales differently with regards to the number of array elements depending on the method used. At 1 GHz, all accelerated methods have a scaling of around but better than as seen in Figure 2 and Figure 3, where is the number of array elements. Though the solution time of the iterative solvers also seems to depend on frequency which the array is simulated at, as seen when comparing the CSA results for 1 GHz in Figure 2 and 4 GHz in Figure 4. For the iterative solvers at 1 GHz, Figure 2, the and full RHS variant M1 solves the problem in the least amount of time. The and full RHS variant M2 takes around 1.6 times longer time to solve, and the with split RHS variant M3 is the slowest with around 3.6 times longer time compared to M1. All three MLFFT solvers are faster and scale better compared to regular GMRES. The Rybicki solver has no discernible difference in solution time when comparing 1 GHz and 4 GHz, it scales well and is the fastest solver at 4 GHz. As mld and G need to store the full impedance matrix in memory, they can not be evaluated up to 196 element arrays with the used computer configuration.

Figure 2. Construction and solution time for a CSA at 1 GHz over number of array elements with tolerance for iterative solvers.

Figure 3. Construction and solution time for a CSA at 1 GHz over number of array elements with tolerance for iterative solvers.

Figure 4. Construction and solution time for a CSA array at 4 GHz over number of array elements with tolerance for iterative solvers. M1 and M3 did not fully converge for 196 elements.
If the tolerance is instead set to , the iterative results change as seen in Figure 3. The direct solvers mldivide and Rybicki have no defined tolerance and therefore their times are unaffected. For comparisons sake, these and the construction time are still plotted in Figure 3 together with the iterative solvers with tolerance. The Rybicki method is now the fastest up to 196 elements and scales similarly as the MLFFT solvers.
solvers. M1 is still the fastest MLFFT solver, though M2 is now only takes around 1.3 times longer. Similarly, M3 is also slightly faster and now takes 2.8 times longer compared to M1. Compared to Figure 2, the time for 196 elements has increased by a factor 7.4 for M1, 5.9 for M2, and 6.0 for M3.
If the frequency is varied rather than the tolerance, there is also a shift in the iterative results as seen when comparing Figure 2 and Figure 4. As the Rybicki method scales slightly worse in these cases, it diverges away from the MLFFT solvers in Figure 2 and almost intersects M1 in Figure 3. The direct methods are still largely unaffected. Notably, M2 is faster and clearly scales better compared to M1 as seen in Figure 4. Furthermore, M3 scales in a similar manner as in Figure 2, but did not converge for each RHS for 196 elements. Considering that M1 and M3 only differ by wether the RHS is vectorized (M1) or solved one at a time (M3), vectorization seems to have some positive effect on convergence for large arrays.
A key performance metric of iterative solvers is their convergence, which is plotted at 1 GHz in Figure 5 for the MLFFT solvers. All solvers converge in a similar manner, though the preconditioner used in M2 converges faster during the first iterations. Note that while M2 converges in fewer iterations, it takes longer time to apply and is therefore slower overall compared to M1. M3 converges in a similar manner to M1 and is faster to apply to a single RHS, but overall slower due to solving multiple RHS one at a time. At 4 GHz, we see a similar trend in Figure 5, although a larger number of iterations is required overall.

Figure 5. Convergence of MLFFT solvers, relative residual over iteration number for a 196 element CSA at 1 GHz. For M3, this is the number of iterations to solve one RHS. Results for 1 GHz are drawn with solid lines and 4 GHz with dashed lines.
When the tolerance for the CSA is decreased to in Figure 3, or when the frequency is increased in Figure 4, Rybicki seems to be a better choice. It is faster than M1 by a factor of 0.77 at 196 array elements. It does not utilize both levels of the multilevel Toeplitz structure, i.e., storing scales as for Rybicki compared to for MLFFT. Here, is the number of columns in the array, the number of rows and the number of mesh cells per element. But when solving the full RHS in MLFFT, the Krylov subspace for iterations scales as . Therefore, if the number of iterations is on scale with the number of mesh cells of one antenna element, the Krylov subspace starts to dominate the memory usage. On the other hand, the Krylov subspace of the split RHS scales as . Therefore, M3 can still be a good choice for memory limited cases, at the cost of computation time in the cases presented in Figure 2, Figure 3 and Figure 6.

Figure 6. Construction and solution time for the wide bowtie array over number of array elements at 150 MHz with tolerance for iterative solvers.
To verify the results of the Rybicki solver and the MLFFT solvers, the CSA EEP of the center and a corner element are compared with the mld solution. The comparison is done for the array, the largest array where the impedance matrix required for the mld solution could be stored in memory. For the EEP from the Rybicki solver, the results are virtually identical, with an RMS deviation on the order of when compared to the mld solution. For the MLFFT solvers, the RMS deviation is on the order of , in line with the set convergence criteria.
Comparing the times for the wide bowtie array () in Figure 6 with the results from the CSA in Figure 2 there are some clear differences. The M1 solver is the fastest in both, but for the bowtie array M2, M3 and Rybicki take a similar amount of time to solve. While not presented as a plot, the wide bowtie was also investigated at 225 MHz and similar effects in solution time could be seen as when the CSA frequency was increased to 4 GHz. The three MLFFT solvers see an increase in solution time, making R faster than M2 and M3. The increased scaling for the MLFFT solvers when going up in frequency was observed for the preconditioner (M2 configuration) whereas the preconditioner (M1 and M3 configuration) had similar scaling for both 150 MHz and 225 MHz. At 225 MHz M1 is still the fastest solver.
To investigate how the methods work for larger arrays, M1 and R were were used to solve the narrow bowtie up to 400 and 900 elements respectively. As seen in Figure 7 they scale in a similar manner as when solving the CSA or wide bowtie, although Rybicki is notably faster compared to M1. Which solver to choose for the fastest simulation time seems to depend on the problem. For the cases in Figure 2 and Figure 6, M1 is the fastest investigated solver. Furthermore, the MLFFT solver utilizes both levels in the multilevel Toeplitz structure for the most memory efficient storage of among the investigated solvers.

Figure 7. Construction and solution time for light bowtie array over number of array elements at 150 MHz with tolerance for iterative solvers.
For the iterative solvers, both the smaller and the larger have their respective advantages and disadvantages. On one hand, is smaller and faster to apply, leading to shorter simulations in Figure 2 and Figure 6. On the other hand, includes interactions with antenna elements in the same row of the array and allows for around twice as fast convergence in iterations. However, as is larger it takes longer time to apply to the matrix and is overall slower compared to , except for in Figure 4. Fewer iterations does decrease the size of the Krylov subspace. A preconditioner which takes more neighboring elements into account, not just those in the same row, may be a better choice compared to both and , though it must also be memory efficient.
To gain further understanding in the difference between the smaller preconditioner and the larger , the spectrum of the preconditioned problem has been investigated. In Figure 8, the first 4000 of the 17300 singular values of are plotted, where is given by the legend. Here gives the spectrum of . These singular values are found using the methods described in [42], implemented for matlab at [43]. The code has been modified to use the fast MLFFT multiplication described in § 2 and Sec. III. As mentioned in [44], it is difficult to determine convergence behavior from the spectrum alone, but some clear differences and similarities can be seen. The frequency only seems to affect the largest singular values. It can also be seen that both preconditioners gives a lot of singular values grouped around 1, which [44] gives as a sign of good convergence for GMRES. The preconditioner has fewer singular values larger than 1, which may explain why it converges in fewer iterations in Figure 5 compared to . It can also be seen that the spectrum of seems to decrease faster than that of from the tenth singular value. Further, it seems that the highest singular values are higher for higher frequency in the preconditioned spectrums. Similar results are seen when investigating the spectrum of the bowtie array.

Figure 8. First 4000 singular values of for a 6 × 6 CSA different preconditioners and at different frequencies. Results for 1 GHz are drawn with solid lines and 4 GHz with dashed lines.
The three iterative MLFFT configurations are faster for certain problems, mainly when the demands on accuracy are and for lower frequencies. On the other hand, the Rybicki method does seem to be more stable and consistent, with solution times and scaling that is largely unaffected by frequency. Further, it is a direct solver that finds an exact solution down to machine accuracy and that works without any need for a preconditioner.
Conclusion
We have implemented two variants of solvers that are accelerated by utilizing the multilevel Toeplitz structure inherent to an impedance matrix of an array antenna. The method of [31] further allows us to apply the solvers to connected elements with an RWG mesh. The goal of these Toeplitz solvers is to find the excitation of arrays with connected elements faster and by using less memory compared to using a full impedance matrix. The results show that by using the decomposition of [31] and solver utilizing the multilevel Toeplitz structure, we can find the excitation of much larger arrays than conventional regular GMRES or the linear equation solver of MATLAB. We also demonstrate that the Toeplitz solvers are significantly faster compared to the two conventional solvers.
We have presented two solvers: the direct Rybicki method and the iterative MLFFT method. The Rybicki method we present is an extension of the algorithm in [33] which works on block Toeplitz matrices without requirements on e.g. symmetry. The MLFFT method is presented along with the underlying theory, the methods behind it, and ready-to-use code. The Rybicki method outperforms the direct inversion mldivide in MATLAB in memory, time and scaling. The iterative MLFFT method also outperform regular GMRES in all of its three configurations in regards to memory, time and scaling. For the array examples shown, the best choice between MLFFT configurations and Rybicki depends on array type, frequency, desired accuracy and available memory. The Rybicki method is more robust, delivering high performance regardless of the problem parameters. The MLFFT method has more problem dependent performance, but is the faster choice for certain configurations. Our solver results have been validated against the mldivide results. The problem dependency of the MLFFT solver has been investigated by examining the spectrum of the preconditioned problem.
MATLAB Code for Single Level Block FFT
function Fx = blockFft(x, N_0, fftHandle)
%BLOCKFFT takes the blockwise fft or
% ifft (1D) with blocksize N_0xN_0
% input:
% x - column block vector
% N_0 - blocksize
% fftHandle - @fft or @ifft
% allocate Fx
Fx = x;
% fft block-wise
for row = 1:N_0
Fx(row:N_0:end,:) = fftHandle(x(
row:N_0:end,:), [], 1);
end
end
MATLAB Code for Dual Level Block FFT
function [Fx] = multiLevelFft(x, N_2, N_1
, N_0, fftHandle)
%multiLevelFft takes the multilevel
% blockwise fft or ifft with
% blocksize N_1N_0xN_1N_0 on the upper
% level and blocksize N_0xN_0 on the
% lower
% input:
% x - column block vector
% N_2 - number of blocks on upper level
% N_1 - number of blocks on lower level
% N_0 - size of block on lower level
% fftHandle - @fft or @ifft
% allocate Fx
Fx = x;
% fft blockwise on lower level
for blockN_2 = 1:N_2
rowBlockStart = (blockN_2-1)*N_1*
N_0;
for rowInBlock = 1:N_0
rowIndices = rowBlockStart +
(rowInBlock:N_0:((N_1-1)*
N_0+rowInBlock));
Fx(rowIndices,:) = fftHandle(
Fx(rowIndices,:), [], 1);
end
end
% fft blockwise on upper level
N_2Size = N_1*N_0;
for rowInBlock = 1:N_2Size
Fx(rowInBlock:N_2Size:end,:) =
fftHandle(Fx(rowInBlock:
N_2Size:end,:), [], 1);
end
endReferences
- [1]T. Latha, G. Ram, G. A. Kumar, and M. Chakravarthy, “Review on ultra-wideband phased array antennas,” IEEE Access, vol. 9, pp. 129742–129755, 2021.DOI
- [2]Y. Liu et al., “Reconfigurable intelligent surfaces: Principles and opportunities,” IEEE Commun. Surveys Tuts., vol. 23, no. 3, pp. 1546–1577, 2021.
- [3]O. Quevedo-Teruel et al., “Roadmap on metasurfaces,” J. Opt., vol. 21, no. 7, p. 073002, 2019.
- [4]A. E. Spezio, “Electronic warfare systems,” IEEE Trans. Microw. Theory Tech., vol. 50, no. 3, pp. 633–644, 2002.DOI
- [5]R. L. Haupt and Y. Rahmat-Samii, “Antenna array developments: A perspective on the past, present and future,” IEEE Antennas Propag. Mag., vol. 57, no. 1, pp. 86–96, 2015.DOI
- [6]S. H. Talisa, K. W. O’Haver, T. M. Comberiate, M. D. Sharp, and O. F. Somerlock, “Benefits of digital phased array radars,” Proc. IEEE, vol. 104, no. 3, pp. 530–543, 2016.DOI
- [7]S. Ghosh and D. Sen, “An inclusive survey on array antenna design for millimeter-wave communications,” IEEE Access, vol. 7, pp. 83 137–83 161, 2019.DOI
- [8]W. Jiang, B. Han, M. A. Habibi, and H. D. Schotten, “The road towards 6G: A comprehensive survey,” IEEE Open J. Commun. Soc., vol. 2, pp. 334–366, 2021.DOI
- [9]P. E. Dewdney, P. J. Hall, R. T. Schilizzi, and T. J. L. Lazio, “The square kilometre array,” Proc. IEEE, vol. 97, no. 8, pp. 1482–1496, 2009.
- [10]J. Cavillot, D. Tihon, F. Mesa, E. L. Acedo, and C. Craeye, “Efficient simulation of large irregular arrays on a finite ground plane,” IEEE Trans. Antennas Propag., vol. 68, no. 4, pp. 2753–2764, 2020.DOI
- [11]R. J. Mailloux, Phased array antenna handbook. Artech house, 2017.
- [12]A. Harlakin, J. Mietzner, P. A. Hoeher, and A. Meusling, “Compressive sensing-aided mimo radar enabling multi-functional and compact sensors in all scenarios using optimized antenna arrays,” IEEE access, vol. 9, pp. 41 417–41 429, 2021.DOI
- [13]J. Helander, D. Tayli, and D. Sjöberg, “Synthesis of large endfire antenna arrays using convex optimization,” IEEE Trans. Antennas Propag., vol. 66, no. 2, pp. 712–720, 2018.DOI
- [14]A. Emadeddin, “Advancements in RF front-end efficiency for next-generation communication systems,” Ph.D. dissertation, KTH Royal Institute of Technology, 2024.
- [15]H. Hultin, H. Frid, and B. L. G. Jonsson, “Wideband side-lobe suppression of tightly coupled arrays,” in 2025 19th European Conference on Antennas and Propagation (EuCAP). IEEE, 2025, pp. 1–5.DOI
- [16]B. L. G. Jonsson, A. Emadeddin, H. Hultin, and L. Åkerstedt, “Far-field accuracy and embedded element pattern approximations in hexomino subarrays,” in 2025 19th European Conference on Antennas and Propagation (EuCAP). IEEE, 2025, pp. 1–5.DOI
- [17]O. Ergül and L. Gürel, The multilevel fast multipole algorithm (MLFMA) for solving large-scale computational electromagnetics problems. John Wiley & Sons, 2014.DOI
- [18]W.-J. He, Z. Yang, X.-W. Huang, W. Wang, M.-L. Yang, and X.-Q. Sheng, “Solving electromagnetic scattering problems with tens of billions of unknowns using GPU accelerated massively parallel MLFMA,” IEEE Trans. Antennas Propag., vol. 70, no. 7, pp. 5672–5682, 2022.
- [19]S. Kurz, O. Rain, and S. Rjasanow, “The adaptive cross-approximation technique for the 3D boundary-element method,” IEEE Trans. Magn., vol. 38, no. 2, pp. 421–424, 2002.DOI
- [20]K. Zhao, M. N. Vouvakis, and J.-F. Lee, “The adaptive cross approximation algorithm for accelerated method of moments computations of EMC problems,” IEEE Trans. Electromagn. Compat., vol. 47, no. 4, pp. 763–773, 2005.DOI
- [21]R. Maaskant, R. Mittra, and A. Tijhuis, “Fast analysis of large antenna arrays using the characteristic basis function method and the adaptive cross approximation algorithm,” IEEE Trans. Antennas Propag., vol. 56, no. 11, pp. 3440–3451, 2008.DOI
- [22]S. Börm, L. Grasedyck, and W. Hackbusch, “Introduction to hierarchical matrices with applications,” Engineering analysis with boundary elements, vol. 27, no. 5, pp. 405–422, 2003.DOI
- [23]V. Gujjula and S. Ambikasaran, “A new nested cross approximation,” arXiv preprint arXiv:2203.14832, 2023.arxiv.org/abs/2203.14832
- [24]W. Hackbusch and B. N. Khoromskij, “Blended kernel approximation in the H-matrix techniques,” Numerical linear algebra with applications, vol. 9, no. 4, pp. 281–304, 2002.
- [25]J. R. Phillips and J. K. White, “A precorrected-FFT method for electrostatic analysis of complicated 3-D structures,” IEEE Trans. computer-aided des. integr. circuits syst., vol. 16, no. 10, pp. 1059–1072, 1997.DOI
- [26]E. H. Błezynski, M. K. Bleszynski, and T. Jaroszewicz, “AIM: Adaptive integral method for solving large-scale electromagnetic scattering and radiation problems,” Radio Science, vol. 31, no. 5, pp. 1225–1251, 1996.
- [27]——, “Block-Toeplitz fast integral equation solver for large finite periodic and partially periodic array systems,” IEICE Trans. Electronics, vol. 87, no. 9, pp. 1586–1594, 2004.
- [28]R. W. Kindt, K. Sertel, E. Topsakal, and J. L. Volakis, “Array decomposition method for the accurate analysis of finite arrays,” IEEE Trans. Antennas Propag., vol. 51, no. 6, pp. 1364–1372, 2003.DOI
- [29]M. Brandt-Möller, M. Mattes, O. Breinberg, M. Zhou, and E. Jørgensen, “Extended higher-order array decomposition method for fully populated or thinned array antennas and scatterers with connected elements,” IEEE Trans. Antennas Propag., 2024.
- [30]S. Rao, D. Wilton, and A. Glisson, “Electromagnetic scattering by surfaces of arbitrary shape,” IEEE Trans. Antennas Propag., vol. 30, no. 3, pp. 409–418, 1982.
- [31]L. Åkerstedt, H. Hultin, and B. L. G. Jonsson, “An array decomposition method for finite arrays with electrically connected elements for fast Toeplitz solvers,” arXiv preprint arXiv:2506.04710, 2025.
- [32]H. Zhai, Q. Chen, Q. Yuan, K. Sawaya, and C. Liang, “Analysis of large-scale periodic array antennas by CG-FFT combined with equivalent sub-array preconditioner,” IEICE Trans. Commun., vol. E89-B, no. 3, pp. 922–928, 2006.DOI
- [33]W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical recipes : the art of scientific computing. Cambridge: Cambridge Univ. Press, 1986.
- [34]G. A. Watson, “An algorithm for the inversion of block matrices of Toeplitz form,” J. Assoc. Comput. Machinery, vol. 20, no. 3, pp. 409–415, 1973.DOI
- [35]K. Choromanski et al., “From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked transformers,” in Int. Conf. Machine Learning. Proc. Machine Learning Res., 2022, pp. 3962–3983.arxiv.org/abs/2107.07999
- [36]D. Lee, “Fast multiplication of a recursive block Toeplitz matrix by a vector and its application,” J. Complexity, vol. 2, no. 4, pp. 295–305, 1986.DOI
- [37]R. A. Horn and C. R. Johnson, Topics in matrix analysis. Cambridge: Cambridge Univ. Press, 1991.DOI
- [38]C. Jelich, M. Karimi, N. Kessissoglou, and S. Marburg, “Efficient solution of block Toeplitz systems with multiple right-hand sides arising from a periodic boundary element formulation,” Engineering Analysis with Boundary Elements, vol. 130, pp. 135–144, 2021.DOI
- [39]Y. Saad, Iterative methods for sparse linear systems, 2nd ed. Philadelphia: Society for Industrial and Applied Mathematics, 2003.DOI
- [40]V. Simoncini and E. Gallopoulos, “An iterative method for nonsymmetric systems with multiple right-hand sides,” SIAM J. Scientific Comput., vol. 16, no. 4, pp. 917–933, 1995.DOI
- [41]“Bordering method”. Encyclopedia of Mathematics. Accessed: May 19, 2025. [Online]. Available: https://encyclopediaofmath.org/wiki/Bordering_method
- [42]N. Halko, P.-G. Martinsson, and J. A. Tropp, “Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions,” SIAM Rev., vol. 53, no. 2, pp. 217–288, 2011.arxiv.org/abs/0909.4061
- [43]L. Li, “Randomized NLA Matlab toolbox”. GitHub. Accessed: Jun. 12, 2025. [Online]. Available: https://github.com/LeeeeLy/Randomized-NLA-Matlab-Toolbox
- [44]E. Carson, J. Liesen, and Z. Strakoš, “Towards understanding CG and GMRES through examples,” Linear Algebra Appl., vol. 692, pp. 241–291, 2024.arxiv.org/abs/2211.00953
