betaFeedback

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 ZZ has the form

Z=[ZAZBTZBZC],(1)Z = \begin{bmatrix} Z_A & Z_B^{T} \\ Z_B & Z_C \end{bmatrix}, \tag*{(1)}

where ZAZ_A is the multilevel Toeplitz-structured matrix of the array elements, ZCZ_C is the impedance matrix of the border and ZBZ_B 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 ZAZ_A, 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 ZAZ_A. 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 ZAZ_A. 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 ZAZ_A. For an array antenna with NxN_x columns and NyN_y rows, the full size of ZAZ_A in (1) scales as Nx2Ny2N_x^2N_y^2. As described in [31], ZAZ_A 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 ZAZ_A is reduced to scale as Nx2NyN_x^2N_y. Furthermore, the scaling is reduced even further by utilizing both levels in the structure in the MLFFT method, down to NxNyN_xN_y. 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 LL-level block-Toeplitz structures [35], with LL levels have the following structure. On the highest level LL, it is a block-Toeplitz structure:

T[L]=[R0R−1⋯R−N[L]+1R1R0⋮⋮⋱⋱R−1RN[L]−1⋯R1R0].(2)T^{[L]} = \begin{bmatrix} R_0 & R_{-1} & \cdots& R_{-N^{[L]}+1} \\ R_1 & R_0 & & \vdots\\ \vdots& \ddots& \ddots& R_{-1} \\ R_{N^{[L]}-1} & \cdots& R_1 & R_0 \end{bmatrix}. \tag*{(2)}

If L−1=l>0L-1=l>0, each block RnR_n is a multilevel block-Toeplitz matrix with ll levels. If l=0l=0, RnR_n is here an unstructured matrix. The matrix T[L]T^{[L]} 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, N[l]N^{[l]}, is defined by the problem. For a one dimensional array with NxN_x antenna elements, which in turn are discretized to NeN_e mesh cells, the impedance matrix is a 1-level block-Toeplitz matrix with N[1]=NxN^{[1]}=N_x and N[0]=NeN^{[0]}=N_e. Extending to a two dimensional array with Nx×NyN_x \times N_y elements gives a 2-level block-Toeplitz matrix, with N[2]=NyN^{[2]}=N_y, N[1]=NxN^{[1]}=N_x and N[0]=NeN^{[0]}=N_e, 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, CC, is diagonalized by the Discrete Fourier Transform (DFT), F\mathcal{F}:

FCF−1=diag⁡(Fc1),(3)\mathcal{F}C\mathcal{F}^{-1}=\operatorname{diag}(\mathcal{F}c_1), \tag*{(3)}

where c1c_1 is the vector consisting of the first column in CC. Using F−1F=I\mathcal{F}^{-1}\mathcal{F}=\mathbb{I}, where I\mathbb{I} is the identity matrix, the product Cuc=vcCu_c=v_c can be written as

Cuc=F−1FCF−1Fuc=F−1diag⁡(Fc1)Fuc.(4)Cu_c=\mathcal{F}^{-1}\mathcal{F}C\mathcal{F}^{-1}\mathcal{F}u_c=\mathcal{F}^{-1}\operatorname{diag}(\mathcal{F}c_1)\mathcal{F}u_c. \tag*{(4)}

A Toeplitz matrix TT is not circulant, but can be padded to create the circulant matrix. Denote the circulant matrix created from TT by C(T)C(T). To show the procedure, consider the following example. Take

T=[t0t−1t−2t1t0t−1t2t1t0],T′=[t0t−1t1t0].(5)T=\begin{bmatrix} t_0 & t_{-1} & t_{-2} \\ t_1 & t_0 & t_{-1} \\ t_2 & t_1 & t_0 \end{bmatrix},\quad T'=\begin{bmatrix} t_0 & t_{-1} \\ t_1 & t_0 \end{bmatrix}. \tag*{(5)}

The circulant matrix C(T)C(T) is populated:

C(T)=[T∗∗T′].(6)C(T)=\begin{bmatrix} T & * \\ * & T' \end{bmatrix}. \tag*{(6)}

where ∗* are to be determined. Following the cyclic pattern in a circulant matrix, the missing entries follows as:

C(T)=[t0t−1t−2t2t1t1t0t−1t−2t2t2t1t0t−1t−2t−2t2t1t0t−1t−1t−2t2t1t0].(7)C(T)=\begin{bmatrix} t_0 & t_{-1} & t_{-2} & t_2 & t_1 \\ t_1 & t_0 & t_{-1} & t_{-2} & t_2 \\ t_2 & t_1 & t_0 & t_{-1} & t_{-2} \\ t_{-2} & t_2 & t_1 & t_0 & t_{-1} \\ t_{-1} & t_{-2} & t_2 & t_1 & t_0 \end{bmatrix}. \tag*{(7)}

The matrix multiplication Tu=vTu=v can now be evaluated by

C(T)[u0]=[Tuγ]=[vγ].(8)C(T)\begin{bmatrix}u\\0\end{bmatrix}=\begin{bmatrix}Tu\\\gamma\end{bmatrix}=\begin{bmatrix}v\\\gamma\end{bmatrix}. \tag*{(8)}

Note that 00 is here a zero vector of length 2 and γ\gamma a vector of unused values. To form c1c_1, the first column of CC, take the first column of TT. Then, take the elements in first row of TT, except the first element, invert the order and append the the first column to create

c1=[t0t1t2t−2t−1]T.(9)c_1=\begin{bmatrix}t_0&t_1&t_2&t_{-2}&t_{-1}\end{bmatrix}^{T}. \tag*{(9)}

That is, for a Toeplitz matrix of size n×nn\times n, we only need to save 2n+12n+1 values to carry out the multiplication. Further, the multiplication is carried out with computational complexity in O(nlog⁡(n))O(n\log(n)) if the DFT in (4) is replaced by the FFT.

Multiplication of multilevel Toeplitz Matrix using DFT

If the elements in TT and C(T)C(T) in § 2-B are replaced by block-matrices, it gives the single-level block matrices T[1]T^{[1]} and C[1](T[1])C^{[1]}(T^{[1]}) which is defined analogously to (7). The multiplication in (8) is carried out in the same manner using the first block column of C[1](T[1])C^{[1]}(T^{[1]}) analogously to (9). The block column is a block vector, a block matrix with a single column of blocks. However, C[1](T[1])C^{[1]}(T^{[1]}) 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 NxN_x antenna elements, where each element is meshed with NeN_e mesh cells, the 1-level block-wise DFT (1LDFT) F[1]\mathcal{F}^{[1]} is defined as

F[1]=FNx⊗INe=[f1,1INe⋯f1,NxINe⋮⋱⋮fNx,1INe⋯fNx,NxINe],(10)\mathcal{F}^{[1]}=\mathcal{F}_{N_x}\otimes\mathbb{I}_{N_e}= \begin{bmatrix} f_{1,1}\mathbb{I}_{N_e} & \cdots& f_{1,N_x}\mathbb{I}_{N_e}\\ \vdots& \ddots& \vdots\\ f_{N_x,1}\mathbb{I}_{N_e} & \cdots& f_{N_x,N_x}\mathbb{I}_{N_e} \end{bmatrix}, \tag*{(10)}

where FNx\mathcal{F}_{N_x} is the DFT of size NxN_x, ⊗\otimes is the Kronecker product, INe\mathbb{I}_{N_e} is the identity matrix of size NeN_e and fi,jf_{i,j} is an element of FN\mathcal{F}_{N}. The inverse 1LDFT is defined in the same manner, with FN\mathcal{F}_{N} replaced by FN−1\mathcal{F}_{N}^{-1}.

With the 1LDFT, the multiplication T[1]u=vT^{[1]}u=v can be carried out in two steps. First, create the first block column C1[1](T[1])C_1^{[1]}(T^{[1]}) analogously to Section II-B:

C1[1](T[1])=[R0T ⋯ RNx−1T RNx+1T ⋯ R1T]T,(11)C_1^{[1]}(T^{[1]})=\left[R_0^{T}\ \cdots\ R_{N_x-1}^{T}\ R_{N_x+1}^{T}\ \cdots\ R_1^{T}\right]^{T}, \tag*{(11)}

where tit_i in (7) is replaced by the corresponding submatrix RiR_i in (2). As each submatrix RiR_i has dimension Ne×NeN_e\times N_e, the matrix C1[1](T[1])C_1^{[1]}(T^{[1]}) has dimension (2Nx−1)Ne×Ne(2N_x-1)N_e\times N_e.

Second, a block analogue to (4) is required. For a general level LL, the product can be written as

C[L](T[L])u[L]=(F[L])−1diag⁡N[0](F[L]C1[L](T[L])F[L])F[L]u[L]=v[L],(12)C^{[L]}(T^{[L]})u^{[L]}= \left(\mathcal{F}^{[L]}\right)^{-1}\operatorname{diag}_{N^{[0]}}\left(\mathcal{F}^{[L]}C_1^{[L]}(T^{[L]})\mathcal{F}^{[L]}\right)\mathcal{F}^{[L]}u^{[L]}=v^{[L]}, \tag*{(12)}

u[L],v[L]∈CNCu^{[L]},v^{[L]}\in\mathbb{C}^{N_C}, where NC=N[0]∏i=1L(2N[i]−1)N_C=N^{[0]}\prod_{i=1}^{L}(2N^{[i]}-1) is the dimension of C[L]C^{[L]}, diag⁡N[0]\operatorname{diag}_{N^{[0]}} denotes a block-diagonal matrix with block size N[0]N^{[0]} and vectors u[L]u^{[L]} and v[L]v^{[L]} are padded versions of uu and vv. For the one dimensional array, L=1L=1, the vectors are defined as

u[1]=[u0],v[1]=[vγ],(13)u^{[1]}=\begin{bmatrix}u\\0\end{bmatrix},\quad v^{[1]}=\begin{bmatrix}v\\\gamma\end{bmatrix}, \tag*{(13)}

where the desired product vv lies in the first N[1]N[0]N^{[1]}N^{[0]} elements of v[1]v^{[1]}. Using (12) and (13) the matrix multiplication for L=1L=1 can be carried out by only storing (2N[1]−1)(N[0])2(2N^{[1]}-1)(N^{[0]})^2 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) F[2]\mathcal{F}^{[2]} is defined similarly to the 1LDFT in (10):

F[2]=FN[2]⊗(FN[1]⊗IN[0])=FN[2]⊗F[1](14)\mathcal{F}^{[2]}=\mathcal{F}_{N^{[2]}}\otimes\left(\mathcal{F}_{N^{[1]}}\otimes\mathbb{I}_{N^{[0]}}\right)=\mathcal{F}_{N^{[2]}}\otimes\mathcal{F}^{[1]} \tag*{(14)}

where N[2]N^{[2]} is the number of blocks on level 2. To create C[2](T[2])C^{[2]}(T^{[2]}) from T[2]T^{[2]}, the blocks need to be rearranged. The Toeplitz matrix of level 2, T[2]T^{[2]}, is structured as follows:

T[2]=[T0[1]⋯T−N[1]+1[1]⋮⋱⋮TN[1]−1[1]⋯T0[1]],(15)T^{[2]}= \begin{bmatrix} T_0^{[1]} & \cdots& T_{-N^{[1]}+1}^{[1]}\\ \vdots& \ddots& \vdots\\ T_{N^{[1]}-1}^{[1]} & \cdots& T_0^{[1]} \end{bmatrix}, \tag*{(15)}

where Tn[1]T_n^{[1]} are 1-level block-Toeplitz matrices.

This structure can, similar to creating C[1](T[1])C^{[1]}(T^{[1]}), be used to create the block diagonalizable matrix C[2](T[2])C^{[2]}(T^{[2]}):

C[2](T[2])=[C[1](T0[1])C[1](T−1[1])⋯C[1](T1[1])⋮⋮C[1](TN[1]−1[1])⋱⋮C[1](T−N[1]+1[1])⋱⋮⋮⋮C[1](T1[1])⋯⋯C[1](T0[1])](16)C^{[2]}(T^{[2]}) = \begin{bmatrix} C^{[1]}(T^{[1]}_0) & C^{[1]}(T^{[1]}_{-1}) & \cdots& C^{[1]}(T^{[1]}_1) \\ \vdots& & & \vdots\\ C^{[1]}(T^{[1]}_{N^{[1]}-1}) & \ddots& & \vdots\\ C^{[1]}(T^{[1]}_{-N^{[1]}+1}) & & \ddots& \vdots\\ \vdots& & & \vdots\\ C^{[1]}(T^{[1]}_1) & \cdots& \cdots& C^{[1]}(T^{[1]}_0) \end{bmatrix} \tag*{(16)}

which has a structure similar to (7) with tit_i replaced by C[1](Ti[1])C^{[1]}(T^{[1]}_i). The first block column of C[2](T[2])C^{[2]}(T^{[2]}), with blocks of size N[0]×N[0]N^{[0]} \times N^{[0]}, is found as follows. For each Tn[1]T^{[1]}_n, n=1,…,N[1],−N[1],…,−1n = 1, \ldots, N^{[1]}, -N^{[1]}, \ldots, -1, form a block column C[1](Tn[1])C^{[1]}(T^{[1]}_n) as in (11). Construct the complete block column C1[2](T[2])C^{[2]}_1(T^{[2]}) as

C1[2](T[2])=[C1[1](T0[1])T⋯C1[1](TN[1]−1[1])TC1[1](T−N[1]+1[1])T⋯C1[1](T−1[1])T]T,(17)C^{[2]}_1(T^{[2]}) = \begin{bmatrix} C^{[1]}_1(T^{[1]}_0)^T & \cdots& C^{[1]}_1(T^{[1]}_{N^{[1]}-1})^T \\ C^{[1]}_1(T^{[1]}_{-N^{[1]}+1})^T & \cdots& C^{[1]}_1(T^{[1]}_{-1})^T \end{bmatrix}^{T}, \tag*{(17)}

which gives the same structure as in [29], Figure 1. From this structure it can also be seen that the zero-padding of uu and vv becomes more complicated, also shown in [29]. Take the original vector uu and divide it into N[2]N^{[2]} subvectors of length N[1]N[0]N^{[1]}N^{[0]}:

Figure 1. Antenna unit cell geometries, feed shown in red. (a) CSA unit cell from the side, h=20.7h=20.7 mm and w=30w=30 mm. The unit cell is 3030 mm ×\times 3030 mm seen from above. (b) bowtie unit cell from above, the bowtie is placed 0.25λ0.25\lambda over a ground plane.

u=[u0Tu1T⋯uN[2]−1T]T.(18)u = \begin{bmatrix} u_0^T & u_1^T & \cdots& u_{N^{[2]}-1}^T \end{bmatrix}^T. \tag*{(18)}

To perform the multiplication C[2](T[2])u[2]=v[2]C^{[2]}(T^{[2]})u^{[2]} = v^{[2]} 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:

u[2]=[u0T0(N[1]−1)N[0]u1T0(N[1]−1)N[0]⋯uN[2]−1T0(N[2]−1)(2N[1]−1)N[0]]T,(19)u^{[2]} = \begin{bmatrix} u_0^T & 0_{(N^{[1]}-1)N^{[0]}} & u_1^T & 0_{(N^{[1]}-1)N^{[0]}} & \cdots& u_{N^{[2]}-1}^T & 0_{(N^{[2]}-1)(2N^{[1]}-1)N^{[0]}} \end{bmatrix}^T, \tag*{(19)}

where 0N0_N is a zero row-vector of length NN. The multiplication can now be performed using (12) with L=2L = 2. The resulting v[2]v^{[2]} has a similar structure to (19), but with unwanted data instead of zero vectors. Finally, vnv_n can be extracted from positions (1,…,N[1]N[0])+n(2N[1]−1)N[0](1, \ldots, N^{[1]}N^{[0]}) + n(2N^{[1]} - 1)N^{[0]} of v[2]v^{[2]} giving

v=[v0Tv1T⋯vN[2]−1T]T.(20)v = \begin{bmatrix} v_0^T & v_1^T & \cdots& v_{N^{[2]}-1}^T \end{bmatrix}^T. \tag*{(20)}

Method

Method of Moments (MoM) gives a typical linear equation system on the form ZI=VZI = V, where ZZ is an impedance matrix, II is the unknown current and VV 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 N[0]N^{[0]}th row of (10) and multiplying it with each N[0]N^{[0]}th row of a vector uu just gives the DFT of those elements in uu, 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 N[0]N^{[0]} FFTs of length (2N[1]−1)=LF(2N^{[1]} - 1) = L_F and is applied on a block matrix on the form of (11) with length LFN[0]L_FN^{[0]} and width WW. Each FFT here has a computational complexity of O(LFlog⁡(LF))O(L_F\log(L_F)). An FFT is applied for each of the N[0]N^{[0]} set of rows, once per column over a total of WW columns, resulting in a total computational complexity of O(WN[0]N[1]log⁡(N[1]))O(WN^{[0]}N^{[1]}\log(N^{[1]})).

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 WW columns, first apply N[2]N[0]N^{[2]}N^{[0]} FFTs of length N[1]N^{[1]}, with complexity O(WN[2]N[0]N[1]log⁡(N[1]))O(WN^{[2]}N^{[0]}N^{[1]}\log(N^{[1]})). Second, apply N[1]N[0]N^{[1]}N^{[0]} FFTs of length N[2]N^{[2]}, complexity O(WN[1]N[0]N[2]log⁡(N[2]))O(WN^{[1]}N^{[0]}N^{[2]}\log(N^{[2]})). The first operation dominates if N[1]>N[2]N^{[1]} > N^{[2]} 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 ZZ 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 PP, rewriting the problem as

P−1ZI=P−1V,(21)P^{-1}ZI = P^{-1}V, \tag*{(21)}

where the goal is for P−1ZP^{-1}Z to be better conditioned compared to ZZ.

One approach is to use an incomplete LU-decomposition (ILU) [39] on ZZ which gives a decomposition such that Z≈LU=PZ \approx LU = P. Then, the preconditioner P−1=(LU)−1P^{-1} = (LU)^{-1} can be applied efficiently using back substitution. However, even if an incomplete LU of ZZ is cheaper than a regular LU, both LL and UU have the same size as ZZ. 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 PK′P'_K is a block-diagonal matrix, where each block is the self-interaction of one element in the matrix Zn,nZ_{n,n}, which has already been computed as it is the block-diagonal part of ZAZ_A 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 Zn,nZ_{n,n} is sufficient to apply the inverse of PK′P'_K 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 PK′P'_K, we use the knowledge that ZAZ_A is largely dominated by the strong block diagonal self-interaction. The matrix PK′P'_K has Ne2N_e^2 elements.

This knowledge of the underlying problem can be extended to another block-diagonal preconditioner PZ′P'_Z, 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 ZAZ_A, but on one level higher in the multilevel block-Toeplitz structure. Each block Z1n,nZ^{n,n}_1 is a block-Toeplitz matrix which describes the self interaction of a row of elements in the array. The preconditioner PZ′P'_Z can be applied in the same manner as PK′P'_K, though the block is larger with Nx2Ne2N_x^2N_e^2 elements.

The preconditioners PK′P'_K and PZ′P'_Z are defined for ZAZ_A in (1). However, ZAZ_A is only one, albeit the largest, part of ZZ. To account for the margin parts of ZZ, the full preconditioners PKP_K and PZP_Z are defined as

PX=[PX′00ZC],(22)P_X = \begin{bmatrix} P'_X & 0 \\ 0 & Z_C \end{bmatrix}, \tag*{(22)}

where the index XX is either KK or ZZ. As the self interaction matrix of the border ZCZ_C is small, its full LU-decomposition is used as a preconditioner for the border. The LU-decomposition of ZCZ_C 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 ZIi=ViZI_i = V_i can be solved using an iterative method. Here ViV_i is an excitation vector corresponding to applying the desired excitation voltage to antenna port ii. 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 IiI_i, 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 ViV_i. A straightforward way to achieve this is to run the solver once for each element, but that scales with computational complexity of O(N[2]N[1])\mathcal{O}(N^{[2]}N^{[1]}).

Instead of solving each element one by one, consider the problem on matrix form:

Z[I1⋯IN[2]N[1]]=[V1⋯VN[2]N[1]]=ZIM=VM.(23)Z\begin{bmatrix} I_1 & \cdots& I_{N^{[2]}N^{[1]}} \end{bmatrix} = \begin{bmatrix} V_1 & \cdots& V_{N^{[2]}N^{[1]}} \end{bmatrix} = ZI_M = V_M. \tag*{(23)}

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

(I⊗Z)vec⁡(IM)=vec⁡(VM),(24)(\mathbb{I} \otimes Z)\operatorname{vec}(I_M) = \operatorname{vec}(V_M), \tag*{(24)}

where vec⁡()\operatorname{vec}() 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 I⊗Z\mathbb{I} \otimes Z. 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 T[1]x=yT^{[1]}x = y through a sequence of solutions x(M)x^{(M)} that converge in the last step when M=NM = N. In our case RnR_n 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

xM+1(M+1)=(∑j=1MRM+1−jGM+1−j(M)−R0)−1(∑j=1MRM+1−jxj(M)−yM+1).(25)x_{M+1}^{(M+1)} = \left( \sum_{j=1}^{M} R_{M+1-j}G_{M+1-j}^{(M)} - R_0 \right)^{-1} \left( \sum_{j=1}^{M} R_{M+1-j}x_j^{(M)} - y_{M+1} \right). \tag*{(25)}

Similarly, rewrite [33 eq. (2.8.18)] as

xj(M+1)=xj(M)−GM+1−j(M)xM+1(M+1),(26)x_j^{(M+1)} = x_j^{(M)} - G_{M+1-j}^{(M)}x_{M+1}^{(M+1)}, \tag*{(26)}

[33 eq. (2.8.24)] as

GM+1(M+1)=(∑j=1MRj−(M+1)HM+1−j(M)−R0)−1(∑j=1MRj−(M+1)Gj(M)−R−(M+1))(27)G_{M+1}^{(M+1)} = \left( \sum_{j=1}^{M} R_{j-(M+1)}H_{M+1-j}^{(M)} - R_0 \right)^{-1} \left( \sum_{j=1}^{M} R_{j-(M+1)}G_j^{(M)} - R_{-(M+1)} \right) \tag*{(27)}

and [33 eq. (2.8.23)] as

HM+1(M+1)=(∑j=1MRM+1−jGM+1−j(M)−R0)−1(∑j=1MRM+1−jHj(M)−RM+1).(28)H_{M+1}^{(M+1)} = \left( \sum_{j=1}^{M} R_{M+1-j}G_{M+1-j}^{(M)} - R_0 \right)^{-1} \left( \sum_{j=1}^{M} R_{M+1-j}H_j^{(M)} - R_{M+1} \right). \tag*{(28)}

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

HM+1−j(M+1)=HM+1−j(M)−Gj(M)HM+1(M+1),j=1,…M.(29)H_{M+1-j}^{(M+1)} = H_{M+1-j}^{(M)} - G_j^{(M)}H_{M+1}^{(M+1)},\quad j=1,\ldots M. \tag*{(29)}

Similarly, the order in [33 eq. (2.8.25)] is changed to

Gj(M+1)=Gj(M)−HM+1−j(M)GM+1(M+1)(30)G_j^{(M+1)} = G_j^{(M)} - H_{M+1-j}^{(M)}G_{M+1}^{(M+1)} \tag*{(30)}
Hj(M+1)=Hj(M)−GM+1−j(M)HM+1(M+1).H_j^{(M+1)} = H_j^{(M)} - G_{M+1-j}^{(M)}H_{M+1}^{(M+1)}.

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 ZAZ_A. 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 R\mathbf{R}, is a full block-Toeplitz matrix. Even so, this reduces the memory usage from the full matrix ZAZ_A with Ny2Nx2Ne2N_y^2N_x^2N_e^2 elements down to a structure with (2Ny−1)Nx2Ne2(2N_y-1)N_x^2N_e^2 elements. Note that this method works for any set of invertible RnR_n, 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.

  1. MLFFT: The MLFFT method is based on matrix multiplication, which can be performed blockwise. For a single RHS, partition the current vector I=[IAT ICT]T\mathbf{I} = [I_A^T\ I_C^T]^T and the excitation vector V=[VAT VCT]T\mathbf{V} = [V_A^T\ V_C^T]^T into the values on the array elements (denoted by AA) and the values on the border (denoted by CC). Then, multiply blockwise:

ZI=[ZAZBTZBZC][IAIC]=[ZAIA+ZBTICZBIA+ZCIC]=[VAVC].(31)Z I = \begin{bmatrix} Z_A & Z_B^T \\ Z_B & Z_C \end{bmatrix} \begin{bmatrix} I_A \\ I_C \end{bmatrix} = \begin{bmatrix} Z_A I_A + Z_B^T I_C \\ Z_B I_A + Z_C I_C \end{bmatrix} = \begin{bmatrix} V_A \\ V_C \end{bmatrix}. \tag*{(31)}

Multiplying with ZAZ_A is accelerated as in § 2, while the smaller margin matrices ZBZ_B and ZCZ_C are multiplied using matrix multiplication.

  1. Rybicki: The Rybicki method only works on a Toeplitz structure, i.e. the problem must be on the form T[1]x=yT^{[1]}x=y. Here, Schur decomposition is used to rewrite the matrix equation to only invert ZAZ_A, moving the border matrices ZBZ_B and ZCZ_C 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), IAI_A can be written as

IA=ZA−1(VA−ZBTIC).(32)I_A = Z_A^{-1}(V_A-Z_B^T I_C). \tag*{(32)}

Inserting this in the second row of blocks gives

ZBZA−1VA−ZBZA−1ZBTIC+ZCIC=VC.(33)Z_BZ_A^{-1}V_A-Z_BZ_A^{-1}Z_B^T I_C+Z_CI_C=V_C. \tag*{(33)}

Isolating ICI_C gives

(ZC−ZBZA−1ZBT)IC=VC−ZBZA−1VA.(34)(Z_C-Z_BZ_A^{-1}Z_B^T)I_C=V_C-Z_BZ_A^{-1}V_A. \tag*{(34)}

Let U=ZA−1VAU=Z_A^{-1}V_A and F=ZA−1ZBTF=Z_A^{-1}Z_B^T and solve the problem

ZA[UF]=[VABT](35)Z_A[U\quad F]=[V_A\quad B^T] \tag*{(35)}

for [UF][U\quad F]. The currents can then be found using

IC=(ZC−ZBF)−1(VC−ZBU),(36)I_C=(Z_C-Z_BF)^{-1}(V_C-Z_BU), \tag*{(36)}

a relatively small inversion, and

IA=U−FIC.(37)I_A=U-FI_C. \tag*{(37)}

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 W=0.375λW=0.375\lambda and 1081 unknowns per element is simulated at 150 MHz and 225 MHz, and a narrower element with W=0.25λW=0.25\lambda and 253 unknowns per element at 150 MHz.

For ZZ 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 PKP_K 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:

  1. read the mesh file of the antenna element,

  2. define simulation parameters, e.g. array size and frequency,

  3. create the unique sub-matrices of ZZ in (1) as described in [31],

  4. (conditional) fill in a full matrix variant of ZZ (for mldivide or GMRES) or fill in the lowest Toeplitz level of ZZ (for the Rybicki method),

  5. solve ZI=VZI=V.

All simulations are run on a computer with an Intel Xeon Gold 5217 processor and 191 GB RAM.

By default in this publication, VV is a matrix where each column cc consists of zeros, except for the feeding edge of array element cc which is set to 1. The corresponding column cc of II then contains the currents of the array from exciting the feeding point of element cc. 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 ZZ 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 PKP_K and the larger PZP_Z. Configuration M1 uses a PKP_K preconditioner with a vectorized RHS, M2 a PZP_Z preconditioner with vectorized RHS and M3 a PKP_K 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 M2log⁡MM^2 \log M but better than M3M^3 as seen in Figure 2 and Figure 3, where MM 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 PKP_K and full RHS variant M1 solves the problem in the least amount of time. The PZP_Z and full RHS variant M2 takes around 1.6 times longer time to solve, and the PKP_K 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.

Construction and solution time for a CSA at 1 GHz over number of array elements with $10^{-3}$ tolerance for iterative solvers.

Figure 2. Construction and solution time for a CSA at 1 GHz over number of array elements with 10−310^{-3} tolerance for iterative solvers.

Construction and solution time for a CSA at 1 GHz over number of array elements with $10^{-6}$ tolerance for iterative solvers.

Figure 3. Construction and solution time for a CSA at 1 GHz over number of array elements with 10−610^{-6} tolerance for iterative solvers.

Construction and solution time for a CSA array at 4 GHz over number of array elements

Figure 4. Construction and solution time for a CSA array at 4 GHz over number of array elements with 10−310^{-3} tolerance for iterative solvers. M1 and M3 did not fully converge for 196 elements.

If the tolerance is instead set to 10−610^{-6}, 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 10−610^{-6} 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 PZP_Z 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.

Convergence of MLFFT solvers

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 10−610^{-6} 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 ZAZ_A scales as NxNy2Ne2N_xN_y^2N_e^2 for Rybicki compared to NxNyNe2N_xN_yN_e^2 for MLFFT. Here, NxN_x is the number of columns in the array, NyN_y the number of rows and NeN_e the number of mesh cells per element. But when solving the full RHS in MLFFT, the Krylov subspace for LL iterations scales as LNx2Ny2NeLN_x^2N_y^2N_e. 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 LNxNyNeLN_xN_yN_e. 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.

Construction and solution time for the wide bowtie array over number of array elements

Figure 6. Construction and solution time for the wide bowtie array over number of array elements at 150 MHz with 10−310^{-3} 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 9×99 \times9 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 10−1410^{-14} when compared to the mld solution. For the MLFFT solvers, the RMS deviation is on the order of 10−310^{-3}, in line with the set convergence criteria.

Comparing the times for the wide bowtie array (W=0.375λW = 0.375\lambda) 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 PZP_Z preconditioner (M2 configuration) whereas the PKP_K 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 ZAZ_A among the investigated solvers.

Construction and solution time for light bowtie array over number of array elements

Figure 7. Construction and solution time for light bowtie array over number of array elements at 150 MHz with 10−310^{-3} tolerance for iterative solvers.

For the iterative solvers, both the smaller PKP_K and the larger PZP_Z have their respective advantages and disadvantages. On one hand, PKP_K is smaller and faster to apply, leading to shorter simulations in Figure 2 and Figure 6. On the other hand, PZP_Z includes interactions with antenna elements in the same row of the array and allows for around twice as fast convergence in iterations. However, as PZP_Z is larger it takes longer time to apply to the matrix and is overall slower compared to PKP_K, 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 PKP_K and PZP_Z, though it must also be memory efficient.

To gain further understanding in the difference between the smaller preconditioner PKP_K and the larger PZP_Z, the spectrum of the preconditioned problem has been investigated. In Figure 8, the first 4000 of the 17300 singular values of P−1ZP^{-1}Z are plotted, where PP is given by the legend. Here P=IP = \mathbb{I} gives the spectrum of ZZ. 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 ≈120\approx120 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 PZP_Z has fewer singular values larger than 1, which may explain why it converges in fewer iterations in Figure 5 compared to PKP_K. It can also be seen that the spectrum of PZP_Z seems to decrease faster than that of PKP_K 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.

First 4000 singular values of Z for a 6 × 6 CSA

Figure 8. First 4000 singular values of ZZ 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 10−310^{-3} 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
end

References

  1. [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. [2]Y. Liu et al., “Reconfigurable intelligent surfaces: Principles and opportunities,” IEEE Commun. Surveys Tuts., vol. 23, no. 3, pp. 1546–1577, 2021.
  3. [3]O. Quevedo-Teruel et al., “Roadmap on metasurfaces,” J. Opt., vol. 21, no. 7, p. 073002, 2019.
  4. [4]A. E. Spezio, “Electronic warfare systems,” IEEE Trans. Microw. Theory Tech., vol. 50, no. 3, pp. 633–644, 2002.DOI
  5. [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. [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. [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. [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. [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. [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. [11]R. J. Mailloux, Phased array antenna handbook. Artech house, 2017.
  12. [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. [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. [14]A. Emadeddin, “Advancements in RF front-end efficiency for next-generation communication systems,” Ph.D. dissertation, KTH Royal Institute of Technology, 2024.
  15. [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. [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. [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. [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. [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. [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. [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. [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. [23]V. Gujjula and S. Ambikasaran, “A new nested cross approximation,” arXiv preprint arXiv:2203.14832, 2023.arxiv.org/abs/2203.14832
  24. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [37]R. A. Horn and C. R. Johnson, Topics in matrix analysis. Cambridge: Cambridge Univ. Press, 1991.DOI
  38. [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. [39]Y. Saad, Iterative methods for sparse linear systems, 2nd ed. Philadelphia: Society for Industrial and Applied Mathematics, 2003.DOI
  40. [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. [41]“Bordering method”. Encyclopedia of Mathematics. Accessed: May 19, 2025. [Online]. Available: https://encyclopediaofmath.org/wiki/Bordering_method
  42. [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. [43]L. Li, “Randomized NLA Matlab toolbox”. GitHub. Accessed: Jun. 12, 2025. [Online]. Available: https://github.com/LeeeeLy/Randomized-NLA-Matlab-Toolbox
  44. [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

Paper details

vlnc:W_fdpnb2wk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents