Introduction
Frequency-dependent permittivities turn the Maxwell eigenvalue problem in photonic crystals into a nonlinear eigenvalue problem (NEP). Material absorption leads to complex frequencies and non-Hermitian matrices [5 , 21 ] . The resulting three-dimensional problems combine material nonlinearity with a large curl kernel. Iterative frequency updates require repeated solutions of large eigenproblems, so both the nonlinear iteration and the treatment of the kernel affect the computational cost [8 , 12 ] .
Several methods address the frequency dependence. Auxiliary-field and linearization formulations replace the NEP by a larger linear problem [5 , 20 ] , while spectral indicator methods treat frequency-dependent permittivities through finite-element discretization [25 ] . For general analytic NEPs, infinite Arnoldi uses an infinite-dimensional linear operator [14 ] , NLEIGS uses rational interpolation and structured linearization [9 ] , and contour integration recovers eigenvalues inside a prescribed contour from resolvent moments [1 ] . Quasi-Newton analyses identify the effect of Jacobian approximations [13 ] ; inexact Newton analyses relate inner accuracy to local convergence [3 , 23 ] . Our analysis concerns the particular derivative approximation used in repeated frozen-frequency Maxwell eigensolves.
The Yee discretization preserves the discrete curl–divergence relation [26 ] . FFT-based null-space-free methods exploit the curl structure to remove zero eigenvalues [10 ] . Tiexiang Li and collaborators developed this approach in FAME, including CPU and GPU implementations [19 ] , and extended it to anisotropic crystals in oblique coordinates [24 ] . Their structure-preserving complex-band method fixes a real frequency and computes a complex wave-vector component through a palindromic quadratic eigenvalue formulation [11 ] . That formulation differs from the present NEP, which fixes a real Bloch wave vector and seeks complex frequencies in a dispersive material. For dispersive metallic crystals, Huang, Lin, and Mehrmann combined a Newton-type iteration with nonequivalence deflation and FFT-based null-space-free eigensolves [12 ] . Their scalar Newton update uses a left eigenvector as well as the right eigenpair.
Our earlier work introduced kernel compensation with mimetic finite differences [15 ] . A discrete divergence penalty treats the curl kernel while retaining the original vector space. We subsequently developed anisotropic discretizations and a GPU-accelerated Hermitian solver [17 ] , and combined kernel compensation with fixed-point and Newton iterations for nonlinear Hermitian problems [16 ] . In that setting, the normalized right eigenvector gives the exact eigenvalue derivative, and the Hermitian min–max principle separates the compensated spectrum.
The non-Hermitian extension requires different spectral and convergence arguments. The min–max principle is unavailable for complex spectra, and a simple eigenvalue derivative involves both left and right eigenvectors [7 ] . We retain the mimetic DFT operators and use a right Generalized Davidson eigensolver [2 , 22 ] at each frozen frequency. The quasi-Newton update uses the available normalized right eigenvector in place of the left eigenvector and avoids an additional adjoint eigensolve. Its derivative defect is expressed through the gradient of the material Rayleigh quotient and bounded using the relative spectral gap of the Hermitian part.
The contributions of this work are as follows.
A frequency-independent unitary transformation block-diagonalizes the compensated non-Hermitian matrix, separating the discrete curl image, divergence image, and harmonic spaces, and proves that kernel compensation preserves the original nonlinear eigenpairs under an explicit penalty condition.
The spectral analysis of the preconditioner is extended to complex material coefficients: the two-sided preconditioned matrix is normal, its spectrum lies on a complex line segment, and its condition number admits a material-dependent bound independent of the grid size.
The right-Rayleigh update reuses the computed right eigenvector. For exact inner eigenpairs, we express its linear error factor in terms of the gradient of the material Rayleigh quotient. A relative-gap estimate for the Hermitian part bounds the derivative defect and gives a sufficient condition for local contraction at a simple root. We implement the method in complex double precision with matrix-free CUDA operators. For the SC_CURV/SiC tests with 64 ≤ N ≤ \le N \le ≤ N ≤ 128, the GPU implementation achieves speedups of 69.6–73.0 over the single-core, single-thread CPU implementation.
The paper is organized as follows. § 2 gives the mimetic discretization and matrix-free operators. § 3 establishes the kernel compensation formulation and preconditioning results. § 4 presents the eigensolver, the quasi-Newton update, and the local convergence analysis. § 6 reports complex band structures, convergence histories, and CPU and GPU timings. § 7 concludes the paper.
Discretization
Model Problem and Mimetic Finite Difference Scheme
The model problem is defined over the primitive cell
Ω : = { x = ∑ i = 1 3 x i a i : x i ∈ [ 0 , 1 ] , i = 1 , 2 , 3 } (1) \Omega:= \left\{ \mathbf{x} = \sum_{i=1}^{3} x_i \mathbf{a}_i : x_i \in[0,1],\ i = 1,2,3 \right\} \tag*{(1)} Ω := { x = i = 1 ∑ 3 x i a i : x i ∈ [ 0 , 1 ] , i = 1 , 2 , 3 } (1)
where { a i } i = 1 3 \{\mathbf{a}_i\}_{i=1}^{3} { a i } i = 1 3 forms a basis in R 3 \mathbb{R}^{3} R 3 . For a Bloch wave vector k \mathbf{k} k , the original magnetic field satisfies
H P Q ( x + a i ) = exp ( i k ⋅ a i ) H P Q ( x ) . \mathbf{H}^{\mathrm{PQ}}(\mathbf{x}+\mathbf{a}_i)=\exp(\mathrm{i}\mathbf{k}\cdot\mathbf{a}_i)\mathbf{H}^{\mathrm{PQ}}(\mathbf{x}). H PQ ( x + a i ) = exp ( i k ⋅ a i ) H PQ ( x ) .
The phase transformation H ( x ) : = exp ( − i k ⋅ x ) H P Q ( x ) \mathbf{H}(\mathbf{x}):=\exp(-\mathrm{i}\mathbf{k}\cdot\mathbf{x})\mathbf{H}^{\mathrm{PQ}}(\mathbf{x}) H ( x ) := exp ( − i k ⋅ x ) H PQ ( x ) makes the transformed field periodic. The corresponding differential operator is
∇ k : = ∇ + i k . (2) \nabla_{\mathbf{k}} := \nabla+ \mathrm{i}\mathbf{k}. \tag*{(2)} ∇ k := ∇ + i k . (2)
The magnetic-field formulation with this shifted operator is
{ ∇ k × ε − 1 ( x , ω ) ∇ k × H = ω 2 H in Ω , ∇ k ⋅ H = 0 in Ω , H ( x + a i ) = H ( x ) , i = 1 , 2 , 3. (3) \begin{cases}
\nabla_{\mathbf{k}} \times\varepsilon^{-1}(\mathbf{x},\omega)\nabla_{\mathbf{k}} \times\mathbf{H} = \omega^{2}\mathbf{H} & \text{in }\Omega,\\
\nabla_{\mathbf{k}} \cdot\mathbf{H} = 0 & \text{in }\Omega,\\
\mathbf{H}(\mathbf{x}+\mathbf{a}_{i}) = \mathbf{H}(\mathbf{x}), \quad i=1,2,3. \tag*{(3)}
\end{cases} ⎩ ⎨ ⎧ ∇ k × ε − 1 ( x , ω ) ∇ k × H = ω 2 H ∇ k ⋅ H = 0 H ( x + a i ) = H ( x ) , i = 1 , 2 , 3. in Ω , in Ω , (3)
The dielectric coefficient ε \varepsilon ε satisfies the spatial periodicity condition: ε ( x + a i , ω ) = ε ( x , ω ) \varepsilon(\mathbf{x}+\mathbf{a}_{i},\omega)=\varepsilon(\mathbf{x},\omega) ε ( x + a i , ω ) = ε ( x , ω ) . ε − 1 \varepsilon^{-1} ε − 1 is piecewise defined in Ω \Omega Ω :
ε − 1 ( x , ω ) = { η ( ω ) , x ∈ Ω 1 , 1 , x ∈ Ω ∖ Ω 1 , (4) \varepsilon^{-1}(\mathbf{x},\omega)=
\begin{cases}
\eta(\omega), & \mathbf{x}\in\Omega_{1},\\
1, & \mathbf{x}\in\Omega\setminus\Omega_{1},
\end{cases} \tag*{(4)} ε − 1 ( x , ω ) = { η ( ω ) , 1 , x ∈ Ω 1 , x ∈ Ω ∖ Ω 1 , (4)
where Ω 1 \Omega_{1} Ω 1 denotes the material subregion. The function η \eta η is holomorphic in a pole-free neighborhood of each frequency under consideration. We consider frequencies in Ω s o l ⊂ C \Omega_{\mathrm{sol}}\subset\mathbb{C} Ω sol ⊂ C such that
Ω s o l ⊂ { ω : ω ≠ 0 , 0 < Re η ( ω ) < 1 } . (5) \Omega_{\mathrm{sol}}\subset\{\omega:\ \omega\ne0,\ 0<\operatorname{Re}\eta(\omega)<1\}. \tag*{(5)} Ω sol ⊂ { ω : ω = 0 , 0 < Re η ( ω ) < 1 } . (5)
We map the primitive cell to the unit cube and divide each coordinate direction into N N N intervals of width h = 1 N h=\frac{1}{N} h = N 1 . As in our previous mimetic finite-difference discretizations [15 , 16 , 17 ] , the Yee scheme [26 ] places the three electric components at edge centers, the three magnetic components at face centers, and the divergence value at the cell center, as is illustrated in Table 1 .
Table 1. Degrees of freedom of the discrete electromagnetic fields and divergence image on the Yee grid with N N N intervals in each direction. The indices satisfy i , j , k ∈ { 1 , 2 , … , N } i,j,k\in\{1,2,\ldots,N\} i , j , k ∈ { 1 , 2 , … , N } .
The symbol ψ \psi ψ denotes the divergence. The discrete electric and magnetic fields each contain 3 N 3 3N^{3} 3 N 3 degrees of freedom (DoFs), whereas the discrete divergence contains N 3 N^{3} N 3 DoFs. The outer discrete curl maps edge DoFs to face DoFs; its conjugate transpose gives the inner curl. The discrete inverse dielectric matrix M η ( ω ) \mathcal{M}_{\eta}(\omega) M η ( ω ) maps edge DoFs to edge DoFs.
Discrete Matrix Operators
The matrix representations of the discrete operators have circulant structures. We introduce two N × N N\times N N × N circulant matrices:
D 1 : = 1 h ( 1 0 ⋯ 0 − 1 − 1 1 ⋱ 0 0 ⋱ ⋱ ⋱ ⋮ ⋮ − 1 1 0 0 ⋯ 0 − 1 1 ) , D 0 : = 1 2 ( 1 0 ⋯ 0 1 1 1 ⋱ 0 0 ⋱ ⋱ ⋱ ⋮ ⋮ 1 1 0 0 ⋯ 0 1 1 ) . (6) \mathbf{D}_{1}:=\frac{1}{h}
\begin{pmatrix}
1 & 0 & \cdots& 0 & -1\\
-1 & 1 & \ddots& 0\\
0 & \ddots& \ddots& \ddots& \vdots\\
\vdots& -1 & 1 & 0\\
0 & \cdots& 0 & -1 & 1
\end{pmatrix},
\qquad
\mathbf{D}_{0}:=\frac{1}{2}
\begin{pmatrix}
1 & 0 & \cdots& 0 & 1\\
1 & 1 & \ddots& 0\\
0 & \ddots& \ddots& \ddots& \vdots\\
\vdots& 1 & 1 & 0\\
0 & \cdots& 0 & 1 & 1
\end{pmatrix}. \tag*{(6)} D 1 := h 1 1 − 1 0 ⋮ 0 0 1 ⋱ − 1 ⋯ ⋯ ⋱ ⋱ 1 0 0 0 ⋱ 0 − 1 − 1 ⋮ 1 , D 0 := 2 1 1 1 0 ⋮ 0 0 1 ⋱ 1 ⋯ ⋯ ⋱ ⋱ 1 0 0 0 ⋱ 0 1 1 ⋮ 1 . (6)
The matrix D 1 \mathbf{D}_{1} D 1 approximates a first derivative between staggered locations, while D 0 \mathbf{D}_{0} D 0 averages the zeroth-order Bloch term to the same target DoFs. The higher-order mimetic stencils in [16 , 17 ] replace the circulant coefficients while preserving the factorizations and commutativity used below. The matrix representation in 3D is assembled by Kronecker products between D s \mathbf{D}_{s} D s (s = 0 , 1 s=0,1 s = 0 , 1 ) and identity matrices:
D s , 1 = I N 2 ⊗ D s , D s , 2 = I N ⊗ D s ⊗ I N , D s , 3 = D s ⊗ I N 2 . (7) \mathcal{D}_{s,1}=I_{N^{2}}\otimes\mathbf{D}_{s},\qquad
\mathcal{D}_{s,2}=I_{N}\otimes\mathbf{D}_{s}\otimes I_{N},\qquad
\mathcal{D}_{s,3}=\mathbf{D}_{s}\otimes I_{N^{2}}. \tag*{(7)} D s , 1 = I N 2 ⊗ D s , D s , 2 = I N ⊗ D s ⊗ I N , D s , 3 = D s ⊗ I N 2 . (7)
For a general primitive cell, the matrix A : = ( a 1 a 2 a 3 ) \mathbf{A}:=(\mathbf{a}_1\ \mathbf{a}_2\ \mathbf{a}_3) A := ( a 1 a 2 a 3 ) collects the lattice vectors, and b i j : = ( A − 1 ) i j b_{ij}:=(\mathbf{A}^{-1})_{ij} b ij := ( A − 1 ) ij denotes the ( i , j ) (i,j) ( i , j ) -th entry of its inverse. After mapping Ω \Omega Ω to the unit cube, we define the transformed blocks as in [15 , 17 ] :
D i : = ∑ j = 1 3 b i j D 1 , j + i k i D 0 , i , i = 1 , 2 , 3. (8) D_i:=\sum_{j=1}^{3}b_{ij}D_{1,j}+\mathrm{i}k_iD_{0,i},\qquad i=1,2,3. \tag*{(8)} D i := j = 1 ∑ 3 b ij D 1 , j + i k i D 0 , i , i = 1 , 2 , 3. (8)
The discrete curl and divergence operators A \mathcal{A} A and B \mathcal{B} B are defined by
A : = ( 0 − D 3 D 2 D 3 0 − D 1 − D 2 D 1 0 ) , B : = ( D 1 D 2 D 3 ) . (9) \mathcal{A}:=\begin{pmatrix} 0 & -D_3 & D_2 \\ D_3 & 0 & -D_1 \\ -D_2 & D_1 & 0 \end{pmatrix},\qquad\mathcal{B}:=(D_1\quad D_2\quad D_3). \tag*{(9)} A := 0 D 3 − D 2 − D 3 0 D 1 D 2 − D 1 0 , B := ( D 1 D 2 D 3 ) . (9)
Proposition 2.1. The discrete matrices A \mathcal{A} A and B \mathcal{B} B satisfy
B A = 0 , A A † + B † B = diag ( L , L , L ) , (10) \mathcal{B}\mathcal{A}=0,\qquad\mathcal{A}\mathcal{A}^{\dagger}+\mathcal{B}^{\dagger}\mathcal{B}=\operatorname{diag}(\mathcal{L},\mathcal{L},\mathcal{L}), \tag*{(10)} B A = 0 , A A † + B † B = diag ( L , L , L ) , (10) where
L : = B B † = ∑ i = 1 3 D i † D i . (11) \mathcal{L}:=\mathcal{B}\mathcal{B}^{\dagger}=\sum_{i=1}^{3}D_i^{\dagger}D_i. \tag*{(11)} L := B B † = i = 1 ∑ 3 D i † D i . (11)
Proof. The result follows from [17 Proposition 2.2, Lemma 2.4] .
We define the diagonal matrices M 0 , M 1 ∈ R 3 N 3 × 3 N 3 \mathcal{M}_0,\mathcal{M}_1\in\mathbb{R}^{3N^3\times3N^3} M 0 , M 1 ∈ R 3 N 3 × 3 N 3 by
( M 1 ) β β : = { 1 , the β -th edge DoF lies in Ω 1 , 0 , otherwise, M 0 : = I 3 N 3 − M 1 , β = 1 , … , 3 N 3 . (12) (\mathcal{M}_1)_{\beta\beta}:=\begin{cases}1, & \text{the }\beta\text{-th edge DoF lies in }\Omega_1\text{,}\\0, & \text{otherwise,}\end{cases}\qquad\mathcal{M}_0:=\mathcal{I}_{3N^3}-\mathcal{M}_1,\qquad\beta=1,\ldots,3N^3. \tag*{(12)} ( M 1 ) β β := { 1 , 0 , the β -th edge DoF lies in Ω 1 , otherwise, M 0 := I 3 N 3 − M 1 , β = 1 , … , 3 N 3 . (12)
The matrices M 0 \mathcal{M}_0 M 0 and M 1 \mathcal{M}_1 M 1 are complementary orthogonal projectors. The discrete inverse dielectric matrix is
M η ( ω ) : = M 0 + η ( ω ) M 1 . (13) \mathcal{M}_{\eta}(\omega):=\mathcal{M}_0+\eta(\omega)\mathcal{M}_1. \tag*{(13)} M η ( ω ) := M 0 + η ( ω ) M 1 . (13)
The discretization of (3) gives the constrained nonlinear matrix eigenproblem
{ ( A M η ( ω ) A † ) H h = ω 2 H h , B H h = 0. (14) \begin{cases}
(\mathcal{A}\mathcal{M}_{\eta}(\omega)\mathcal{A}^{\dagger})\mathbf{H}_h=\omega^2\mathbf{H}_h,\\
\mathcal{B}\mathbf{H}_h=0. \tag*{(14)}
\end{cases} { ( A M η ( ω ) A † ) H h = ω 2 H h , B H h = 0. (14)
The unitary one-dimensional DFT matrix F \mathbf{F} F and its three-dimensional and vector-valued forms are defined by
( F ) p q = N − 1 2 exp ( 2 π i ( p − 1 ) ( q − 1 ) N ) , (15) (\mathbf{F})_{pq}=N^{-\frac{1}{2}}\exp\left(\frac{2\pi\mathrm{i}(p-1)(q-1)}{N}\right), \tag*{(15)} ( F ) pq = N − 2 1 exp ( N 2 π i ( p − 1 ) ( q − 1 ) ) , (15)
F = F ⊗ F ⊗ F , F 3 = diag ( F , F , F ) . \mathcal{F}=\mathbf{F}\otimes\mathbf{F}\otimes\mathbf{F},\qquad\mathcal{F}_3=\operatorname{diag}(\mathcal{F},\mathcal{F},\mathcal{F}). F = F ⊗ F ⊗ F , F 3 = diag ( F , F , F ) .
The matrices in (6) are circulant, so each directional block admits the diagonal factorization
D i = F K i F † , i = 1 , 2 , 3. (16) D_i=\mathcal{F}\mathcal{K}_i\mathcal{F}^{\dagger},\qquad i=1,2,3. \tag*{(16)} D i = F K i F † , i = 1 , 2 , 3. (16)
Here K i \mathcal{K}_i K i is diagonal. The discrete matrices A \mathcal{A} A and B \mathcal{B} B satisfy the factorizations
A = F 3 K A F 3 † , B † B = F 3 K B F 3 † . (17) \mathcal{A}=\mathcal{F}_3\mathcal{K}_{\mathcal{A}}\mathcal{F}_3^{\dagger},\qquad
\mathcal{B}^{\dagger}\mathcal{B}=\mathcal{F}_3\mathcal{K}_{\mathcal{B}}\mathcal{F}_3^{\dagger}. \tag*{(17)} A = F 3 K A F 3 † , B † B = F 3 K B F 3 † . (17)
Here the Fourier symbols are
K A : = ( 0 − κ 3 κ 2 κ 3 0 − κ 1 − κ 2 κ 1 0 ) , K B : = ( κ 1 † κ 2 † κ 3 † ) ( κ 1 κ 2 κ 3 ) . (18) \mathcal{K}_{A} := \begin{pmatrix} 0 & -\kappa_{3} & \kappa_{2} \\ \kappa_{3} & 0 & -\kappa_{1} \\ -\kappa_{2} & \kappa_{1} & 0 \end{pmatrix}, \qquad\mathcal{K}_{B} := \begin{pmatrix} \kappa_{1}^{\dagger} \\ \kappa_{2}^{\dagger} \\ \kappa_{3}^{\dagger} \end{pmatrix}(\kappa_{1}\quad\kappa_{2}\quad\kappa_{3}). \tag*{(18)} K A := 0 κ 3 − κ 2 − κ 3 0 κ 1 κ 2 − κ 1 0 , K B := κ 1 † κ 2 † κ 3 † ( κ 1 κ 2 κ 3 ) . (18)
In particular, B A = 0 \mathcal{B}\mathcal{A}=0 B A = 0 of (10) reduces to
K B K A = 0. (19) \mathcal{K}_{B}\mathcal{K}_{A}=0. \tag*{(19)} K B K A = 0. (19)
With x = F 3 † H h \mathbf{x}=\mathcal{F}_{3}^{\dagger}\mathbf{H}_{h} x = F 3 † H h , the constrained problem becomes
{ K 0 ( ω ) x = ω 2 x , K B x = 0 , where K 0 ( ω ) : = K A F 3 † M η ( ω ) F 3 K A † . (20) \left\{\begin{aligned}
\mathcal{K}_{0}(\omega)\mathbf{x}&=\omega^{2}\mathbf{x},\\
\mathcal{K}_{B}\mathbf{x}&=0,
\end{aligned}\right.
\qquad\text{where }\mathcal{K}_{0}(\omega):=\mathcal{K}_{A}\mathcal{F}_{3}^{\dagger}\mathcal{M}_{\eta}(\omega)\mathcal{F}_{3}\mathcal{K}_{A}^{\dagger}. \tag*{(20)} { K 0 ( ω ) x K B x = ω 2 x , = 0 , where K 0 ( ω ) := K A F 3 † M η ( ω ) F 3 K A † . (20)
In practice, we store the nonzero elements of K A \mathcal{K}_{A} K A , K B \mathcal{K}_{B} K B , and corresponding integer indices of M 1 \mathcal{M}_{1} M 1 . Each application of K 0 ( ω ) \mathcal{K}_{0}(\omega) K 0 ( ω ) uses elementwise multiplication and one forward and one backward 3D FFT. For a block of m m m vectors X ∈ C 3 N 3 × m \mathbf{X}\in\mathbb{C}^{3N^{3}\times m} X ∈ C 3 N 3 × m , the dominant runtime cost is O ( m N 3 log N ) O(mN^{3}\log N) O ( m N 3 log N ) .
We conclude this section with the derivatives of K 0 ( ω ) \mathcal{K}_{0}(\omega) K 0 ( ω ) . The material derivatives satisfy
M η ( ℓ ) ( ω ) : = d ℓ M η ( ω ) d ω ℓ = η ( ℓ ) ( ω ) M 1 , ℓ = 1 , 2 , … (21) \mathcal{M}_{\eta}^{(\ell)}(\omega):=\frac{d^{\ell}\mathcal{M}_{\eta}(\omega)}{d\omega^{\ell}}=\eta^{(\ell)}(\omega)\mathcal{M}_{1},\qquad\ell=1,2,\ldots \tag*{(21)} M η ( ℓ ) ( ω ) := d ω ℓ d ℓ M η ( ω ) = η ( ℓ ) ( ω ) M 1 , ℓ = 1 , 2 , … (21)
The superscript “ℓ \ell ℓ ” denotes the derivative order. Consequently, the derivatives of K 0 ( ω ) \mathcal{K}_{0}(\omega) K 0 ( ω ) are
K 0 ( ℓ ) ( ω ) = η ( ℓ ) ( ω ) K A F 3 † M 1 F 3 K A † , ℓ = 1 , 2 , … (22) \mathcal{K}_{0}^{(\ell)}(\omega)=\eta^{(\ell)}(\omega)\mathcal{K}_{A}\mathcal{F}_{3}^{\dagger}\mathcal{M}_{1}\mathcal{F}_{3}\mathcal{K}_{A}^{\dagger},\qquad\ell=1,2,\ldots \tag*{(22)} K 0 ( ℓ ) ( ω ) = η ( ℓ ) ( ω ) K A F 3 † M 1 F 3 K A † , ℓ = 1 , 2 , … (22)
In a matrix-free implementation, M η ( ω ) \mathcal{M}_{\eta}(\omega) M η ( ω ) and its derivatives are applied by elementwise multiplications on the edge indices. We denote the frequency-independent term by
Q : = K A F 3 † M 1 F 3 K A † . (23) Q:=\mathcal{K}_{A}\mathcal{F}_{3}^{\dagger}\mathcal{M}_{1}\mathcal{F}_{3}\mathcal{K}_{A}^{\dagger}. \tag*{(23)} Q := K A F 3 † M 1 F 3 K A † . (23)
The derivatives therefore satisfy K 0 ( ℓ ) ( ω ) = η ( ℓ ) ( ω ) Q \mathcal{K}_{0}^{(\ell)}(\omega)=\eta^{(\ell)}(\omega)Q K 0 ( ℓ ) ( ω ) = η ( ℓ ) ( ω ) Q for ℓ = 1 , 2 , … \ell=1,2,\ldots ℓ = 1 , 2 , … .
Kernel Compensation Formulation
The kernel compensation method adds a penalty term with coefficient γ ≥ 0 \gamma\geq0 γ ≥ 0 to K 0 ( ω ) \mathcal{K}_{0}(\omega) K 0 ( ω ) :
K γ ( ω ) x = ω 2 x , K γ ( ω ) : = K 0 ( ω ) + γ K B . (24) \mathcal{K}_{\gamma}(\omega)\mathbf{x}=\omega^{2}\mathbf{x},\qquad\mathcal{K}_{\gamma}(\omega):=\mathcal{K}_{0}(\omega)+\gamma\mathcal{K}_{B}. \tag*{(24)} K γ ( ω ) x = ω 2 x , K γ ( ω ) := K 0 ( ω ) + γ K B . (24)
The value γ = 0 \gamma=0 γ = 0 recovers the original matrix K 0 ( ω ) \mathcal{K}_{0}(\omega) K 0 ( ω ) . Since the compensation term is independent of ω \omega ω , the derivatives satisfy
K γ ( ℓ ) ( ω ) = K 0 ( ℓ ) ( ω ) = η ( ℓ ) ( ω ) Q , ℓ = 1 , 2 , … \mathcal{K}_{\gamma}^{(\ell)}(\omega)=\mathcal{K}_{0}^{(\ell)}(\omega)=\eta^{(\ell)}(\omega)Q,\qquad\ell=1,2,\ldots K γ ( ℓ ) ( ω ) = K 0 ( ℓ ) ( ω ) = η ( ℓ ) ( ω ) Q , ℓ = 1 , 2 , …
In this section, we rebuild the kernel compensation formulation for the non-Hermitian Maxwell eigenproblem through unitary diagonalization, then extend the theory to nonlinear cases. In Subsection 3.3, we prove that the preconditioning in [16 , 17 ] remains efficient for nonlinear, non-Hermitian cases.
Space Decomposition
The following lemma gives the kernel of K 0 ( ω ) \mathcal{K}_{0}(\omega) K 0 ( ω ) .
Lemma 3.1. The matrices A \mathcal{A} A and M \mathcal{M} M have compatible dimensions. If M + M † \mathcal{M}+\mathcal{M}^{\dagger} M + M † is Hermitian positive definite (HPD), then the following equality holds:
ker ( A † M A ) = ker ( A ) . \operatorname{ker}(\mathcal{A}^{\dagger}\mathcal{M}\mathcal{A})=\operatorname{ker}(\mathcal{A}). ker ( A † M A ) = ker ( A ) .
Proof. The inclusion ker ( A ) ⊂ ker ( A † M A ) \ker(\mathcal{A}) \subset\ker(\mathcal{A}^{\dagger}\mathcal{M}\mathcal{A}) ker ( A ) ⊂ ker ( A † M A ) follows directly. If A † M A x = 0 \mathcal{A}^{\dagger}\mathcal{M}\mathcal{A}x=0 A † M A x = 0 , then
0 = 2 Re ( x † A † M A x ) = ( A x ) † ( M + M † ) ( A x ) . 0=2\operatorname{Re}\left(x^{\dagger}\mathcal{A}^{\dagger}\mathcal{M}\mathcal{A}x\right)=(\mathcal{A}x)^{\dagger}\left(\mathcal{M}+\mathcal{M}^{\dagger}\right)(\mathcal{A}x). 0 = 2 Re ( x † A † M A x ) = ( A x ) † ( M + M † ) ( A x ) .
The positive definiteness of M + M † \mathcal{M}+\mathcal{M}^{\dagger} M + M † implies A x = 0 \mathcal{A}x=0 A x = 0 , which proves the reverse inclusion.
We introduce the discrete curl image space V A \mathcal{V}_{\mathcal{A}} V A , the discrete divergence image space V B \mathcal{V}_{\mathcal{B}} V B , and the discrete harmonic space V 0 \mathcal{V}_{0} V 0 by
V A : = im ( K A ) , V B : = im ( K B ) , V 0 : = ker ( K A † ) ∩ ker ( K B ) . (25) \mathcal{V}_{\mathcal{A}}:=\operatorname{im}(\mathcal{K}_{\mathcal{A}}),\qquad\mathcal{V}_{\mathcal{B}}:=\operatorname{im}(\mathcal{K}_{\mathcal{B}}),\qquad\mathcal{V}_{0}:=\ker(\mathcal{K}_{\mathcal{A}}^{\dagger})\cap\ker(\mathcal{K}_{\mathcal{B}}). \tag*{(25)} V A := im ( K A ) , V B := im ( K B ) , V 0 := ker ( K A † ) ∩ ker ( K B ) . (25)
The following proposition gives the discrete space decomposition and identifies the kernel and image of K γ ( ω ) \mathcal{K}_{\gamma}(\omega) K γ ( ω ) .
Proposition 3.2. The spaces in (3.2) are mutually orthogonal and satisfy
C 3 N 3 = V A ⊕ V B ⊕ V 0 . (26) \mathbb{C}^{3N^{3}}=\mathcal{V}_{\mathcal{A}}\oplus\mathcal{V}_{\mathcal{B}}\oplus\mathcal{V}_{0}. \tag*{(26)} C 3 N 3 = V A ⊕ V B ⊕ V 0 . (26) If Re η ( ω ) > 0 \operatorname{Re}\eta(\omega)>0 Re η ( ω ) > 0 , the kernels and images satisfy
ker ( K γ ( ω ) ) = ker ( K γ ( ω ) † ) = { ker ( K A † ) , γ = 0 , V 0 , γ > 0 , (27) \ker(\mathcal{K}_{\gamma}(\omega))=\ker(\mathcal{K}_{\gamma}(\omega)^{\dagger})=
\begin{cases}
\ker(\mathcal{K}_{\mathcal{A}}^{\dagger}), & \gamma=0,\\
\mathcal{V}_{0}, & \gamma>0,
\end{cases} \tag*{(27)} ker ( K γ ( ω )) = ker ( K γ ( ω ) † ) = { ker ( K A † ) , V 0 , γ = 0 , γ > 0 , (27) im ( K γ ( ω ) ) = im ( K γ ( ω ) † ) = { V A , γ = 0 , V A ⊕ V B , γ > 0. \operatorname{im}(\mathcal{K}_{\gamma}(\omega))=\operatorname{im}(\mathcal{K}_{\gamma}(\omega)^{\dagger})=
\begin{cases}
\mathcal{V}_{\mathcal{A}}, & \gamma=0,\\
\mathcal{V}_{\mathcal{A}}\oplus\mathcal{V}_{\mathcal{B}}, & \gamma>0.
\end{cases} im ( K γ ( ω )) = im ( K γ ( ω ) † ) = { V A , V A ⊕ V B , γ = 0 , γ > 0.
Proof. Due to the range–kernel orthogonality, the following equalities hold:
V A ⊥ = ker ( K A † ) , V B ⊥ = ker ( K B ) . \mathcal{V}_{\mathcal{A}}^{\perp}=\ker(\mathcal{K}_{\mathcal{A}}^{\dagger}),\qquad\mathcal{V}_{\mathcal{B}}^{\perp}=\ker(\mathcal{K}_{\mathcal{B}}). V A ⊥ = ker ( K A † ) , V B ⊥ = ker ( K B ) .
The identities in (2.19) imply V A ⊥ V B \mathcal{V}_{\mathcal{A}}\perp\mathcal{V}_{\mathcal{B}} V A ⊥ V B . The harmonic space therefore satisfies
V 0 = V A ⊥ ∩ V B ⊥ = ( V A ⊕ V B ) ⊥ , \mathcal{V}_{0}=\mathcal{V}_{\mathcal{A}}^{\perp}\cap\mathcal{V}_{\mathcal{B}}^{\perp}=(\mathcal{V}_{\mathcal{A}}\oplus\mathcal{V}_{\mathcal{B}})^{\perp}, V 0 = V A ⊥ ∩ V B ⊥ = ( V A ⊕ V B ) ⊥ ,
which proves the orthogonal decomposition in (3.3).
The Hermitian part of M η ( ω ) \mathcal{M}_{\eta}(\omega) M η ( ω ) satisfies
M η ( ω ) + M η ( ω ) † 2 = M 0 + Re η ( ω ) M 1 > 0 \frac{\mathcal{M}_{\eta}(\omega)+\mathcal{M}_{\eta}(\omega)^{\dagger}}{2}=\mathcal{M}_{0}+\operatorname{Re}\eta(\omega)\mathcal{M}_{1}>0 2 M η ( ω ) + M η ( ω ) † = M 0 + Re η ( ω ) M 1 > 0
if Re η ( ω ) > 0 \operatorname{Re}\eta(\omega)>0 Re η ( ω ) > 0 according to (2.12) and (2.13). Lemma 3.1 then implies
ker ( K 0 ( ω ) ) = ker ( K 0 ( ω ) † ) = ker ( K A † ) . \ker(\mathcal{K}_{0}(\omega))=\ker(\mathcal{K}_{0}(\omega)^{\dagger})=\ker(\mathcal{K}_{\mathcal{A}}^{\dagger}). ker ( K 0 ( ω )) = ker ( K 0 ( ω ) † ) = ker ( K A † ) .
For γ > 0 \gamma>0 γ > 0 and every x ∈ C 3 N 3 x\in\mathbb{C}^{3N^{3}} x ∈ C 3 N 3 , the real part of the quadratic form satisfies
Re ( x † K γ ( ω ) x ) = ( F 3 K A † x ) † ( M 0 + Re η ( ω ) M 1 ) ( F 3 K A † x ) + γ x † K B x . \operatorname{Re}\left(x^{\dagger}\mathcal{K}_{\gamma}(\omega)x\right)=\left(\mathcal{F}_{3}\mathcal{K}_{\mathcal{A}}^{\dagger}x\right)^{\dagger}\left(\mathcal{M}_{0}+\operatorname{Re}\eta(\omega)\mathcal{M}_{1}\right)\left(\mathcal{F}_{3}\mathcal{K}_{\mathcal{A}}^{\dagger}x\right)+\gamma x^{\dagger}\mathcal{K}_{\mathcal{B}}x. Re ( x † K γ ( ω ) x ) = ( F 3 K A † x ) † ( M 0 + Re η ( ω ) M 1 ) ( F 3 K A † x ) + γ x † K B x .
Both terms on the right-hand side are nonnegative. The conditions for their sum to vanish yield
K γ ( ω ) x = 0 ⟺ K A † x = 0 , K B x = 0 , \mathcal{K}_{\gamma}(\omega)x=0\quad\Longleftrightarrow\quad\mathcal{K}_{\mathcal{A}}^{\dagger}x=0,\quad\mathcal{K}_{\mathcal{B}}x=0, K γ ( ω ) x = 0 ⟺ K A † x = 0 , K B x = 0 ,
leading to ker ( K γ ( ω ) ) = V 0 \ker(\mathcal{K}_{\gamma}(\omega))=\mathcal{V}_{0} ker ( K γ ( ω )) = V 0 for γ > 0 \gamma>0 γ > 0 . The same argument gives ker ( K γ ( ω ) † ) = V 0 \ker(\mathcal{K}_{\gamma}(\omega)^{\dagger})=\mathcal{V}_{0} ker ( K γ ( ω ) † ) = V 0 because the adjoint has exactly the same Hermitian part. Finally, im ( K γ ( ω ) ) = ker ( K γ ( ω ) † ) ⊥ \operatorname{im}(\mathcal{K}_{\gamma}(\omega))=\ker(\mathcal{K}_{\gamma}(\omega)^{\dagger})^{\perp} im ( K γ ( ω )) = ker ( K γ ( ω ) † ) ⊥ and im ( K γ ( ω ) † ) = ker ( K γ ( ω ) ) ⊥ \operatorname{im}(\mathcal{K}_{\gamma}(\omega)^{\dagger})=\ker(\mathcal{K}_{\gamma}(\omega))^{\perp} im ( K γ ( ω ) † ) = ker ( K γ ( ω ) ) ⊥ give the image formulas in (3.4).
The kernel of the discrete Laplacian determines the dimensions of these spaces. For the simple cubic lattice A = I 3 \mathcal{A}=\mathcal{I}_{3} A = I 3 , we assume max i = 1 , 2 , 3 ∣ k i ∣ ≤ π \max_{i=1,2,3}|k_{i}|\leq\pi max i = 1 , 2 , 3 ∣ k i ∣ ≤ π and h < 1 π h<\frac{1}{\pi} h < π 1 .
Proposition 3.3. Under these assumptions, the discrete Laplacian L \mathcal{L} L satisfies
dim ker ( L ) = { 0 , k ≠ 0 , 1 , k = 0 , (28) \dim\ker(\mathcal{L}) =
\begin{cases}
0, & \mathbf{k} \ne0,\\
1, & \mathbf{k} = 0,
\end{cases} \tag*{(28)} dim ker ( L ) = { 0 , 1 , k = 0 , k = 0 , (28) and the dimensions of V A \mathcal{V}_{\mathcal{A}} V A , V B \mathcal{V}_{\mathcal{B}} V B , and V 0 \mathcal{V}_{0} V 0 are
( dim V A , dim V B , dim V 0 ) = { ( 2 N 3 , N 3 , 0 ) , k ≠ 0 , ( 2 N 3 − 2 , N 3 − 1 , 3 ) , k = 0. (29) (\dim\mathcal{V}_{\mathcal{A}},\dim\mathcal{V}_{\mathcal{B}},\dim\mathcal{V}_{0}) =
\begin{cases}
(2N^{3},N^{3},0), & \mathbf{k} \ne0,\\
(2N^{3}-2,N^{3}-1,3), & \mathbf{k} = 0.
\end{cases} \tag*{(29)} ( dim V A , dim V B , dim V 0 ) = { ( 2 N 3 , N 3 , 0 ) , ( 2 N 3 − 2 , N 3 − 1 , 3 ) , k = 0 , k = 0. (29)
Proof. The dimension of ker ( L ) \ker(\mathcal{L}) ker ( L ) in (28) follows from [17 Lemma 2.4] for k ≠ 0 \mathbf{k} \ne0 k = 0 ; at k = 0 \mathbf{k}=0 k = 0 , ker ( L ) \ker(\mathcal{L}) ker ( L ) is spanned by the constant Fourier mode. The identities in (10) and (17) give
K A K A † + K B = F 3 † diag ( L , L , L ) F 3 . \mathcal{K}_{\mathcal{A}}\mathcal{K}_{\mathcal{A}}^{\dagger}+\mathcal{K}_{\mathcal{B}}=\mathcal{F}_{3}^{\dagger}\operatorname{diag}(\mathcal{L},\mathcal{L},\mathcal{L})\mathcal{F}_{3}. K A K A † + K B = F 3 † diag ( L , L , L ) F 3 .
Therefore, V 0 = ker ( K A K A † + K B ) \mathcal{V}_{0}=\ker(\mathcal{K}_{\mathcal{A}}\mathcal{K}_{\mathcal{A}}^{\dagger}+\mathcal{K}_{\mathcal{B}}) V 0 = ker ( K A K A † + K B ) implies dim V 0 = 3 dim ker ( L ) \dim\mathcal{V}_{0}=3\dim\ker(\mathcal{L}) dim V 0 = 3 dim ker ( L ) . Since B B † = L \mathcal{B}\mathcal{B}^{\dagger}=\mathcal{L} B B † = L , the rank satisfies
dim V B = rank ( K B ) = rank ( B † B ) = rank ( L ) = N 3 − dim ker ( L ) . (30) \dim\mathcal{V}_{\mathcal{B}}=\operatorname{rank}(\mathcal{K}_{\mathcal{B}})=\operatorname{rank}(\mathcal{B}^{\dagger}\mathcal{B})=\operatorname{rank}(\mathcal{L})=N^{3}-\dim\ker(\mathcal{L}). \tag*{(30)} dim V B = rank ( K B ) = rank ( B † B ) = rank ( L ) = N 3 − dim ker ( L ) . (30)
The orthogonal decomposition (26) then gives dim V A = 3 N 3 − dim V B − dim V 0 \dim\mathcal{V}_{\mathcal{A}}=3N^{3}-\dim\mathcal{V}_{\mathcal{B}}-\dim\mathcal{V}_{0} dim V A = 3 N 3 − dim V B − dim V 0 , which proves (29) . □
The same dimension formulas hold for other lattices whenever (28) holds. The Fourier symbols satisfy this condition for the face centered cubic and body centered cubic grids and wave vectors used in Section 5.
Unitary Block Diagonalization
The following lemma identifies the spectrum retained by compression to the image space.
Lemma 3.4. The matrix A \mathcal{A} A is square, and the columns of U \mathcal{U} U form an orthonormal basis of im ( A ) \operatorname{im}(\mathcal{A}) im ( A ) . The nonzero spectra agree, including algebraic multiplicities:
σ ( U † A U ) ∖ { 0 } = σ ( A ) ∖ { 0 } . (31) \sigma(\mathcal{U}^{\dagger}\mathcal{A}\mathcal{U})\setminus\{0\}=\sigma(\mathcal{A})\setminus\{0\}. \tag*{(31)} σ ( U † A U ) ∖ { 0 } = σ ( A ) ∖ { 0 } . (31) The matrix U † A U \mathcal{U}^{\dagger}\mathcal{A}\mathcal{U} U † A U is nonsingular if and only if im ( A ) ∩ ker ( A ) = { 0 } \operatorname{im}(\mathcal{A})\cap\ker(\mathcal{A})=\{0\} im ( A ) ∩ ker ( A ) = { 0 } .
Proof. Since U U † A = A \mathcal{U}\mathcal{U}^{\dagger}\mathcal{A}=\mathcal{A} U U † A = A , a unitary completion of U \mathcal{U} U transforms A \mathcal{A} A into an upper triangular block matrix with diagonal blocks U † A U \mathcal{U}^{\dagger}\mathcal{A}\mathcal{U} U † A U and 0 0 0 . This proves (31) and preserves the nonzero algebraic multiplicities. The identity A U = U ( U † A U ) \mathcal{A}\mathcal{U}=\mathcal{U}(\mathcal{U}^{\dagger}\mathcal{A}\mathcal{U}) A U = U ( U † A U ) also gives U ker ( U † A U ) = im ( A ) ∩ ker ( A ) \mathcal{U}\ker(\mathcal{U}^{\dagger}\mathcal{A}\mathcal{U})=\operatorname{im}(\mathcal{A})\cap\ker(\mathcal{A}) U ker ( U † A U ) = im ( A ) ∩ ker ( A ) , which proves the last assertion. □
We select arbitrary orthonormal bases of V A \mathcal{V}_{\mathcal{A}} V A , V B \mathcal{V}_{\mathcal{B}} V B , and V 0 \mathcal{V}_{0} V 0 , and denote the corresponding basis matrices by U A \mathcal{U}_{\mathcal{A}} U A , U B \mathcal{U}_{\mathcal{B}} U B , and U 0 \mathcal{U}_{0} U 0 , respectively. Each matrix has 3 N 3 3N^{3} 3 N 3 rows and as many columns as the dimension of its space. Proposition 3.2 implies that the matrix
U : = ( U A U B U 0 ) (32) \mathcal{U}:=(\mathcal{U}_{\mathcal{A}}\ \mathcal{U}_{\mathcal{B}}\ \mathcal{U}_{0}) \tag*{(32)} U := ( U A U B U 0 ) (32)
is unitary. Moreover, U 0 \mathcal{U}_{0} U 0 is omitted when V 0 = { 0 } \mathcal{V}_{0}=\{0\} V 0 = { 0 } . The restrictions of K 0 ( ω ) \mathcal{K}_{0}(\omega) K 0 ( ω ) and K B \mathcal{K}_{\mathcal{B}} K B to their image spaces are defined by
R A ( ω ) : = U A † K 0 ( ω ) U A , R B : = U B † K B U B . (33) \mathcal{R}_{\mathcal{A}}(\omega):=\mathcal{U}_{\mathcal{A}}^{\dagger}\mathcal{K}_{0}(\omega)\mathcal{U}_{\mathcal{A}},\qquad\mathcal{R}_{\mathcal{B}}:=\mathcal{U}_{\mathcal{B}}^{\dagger}\mathcal{K}_{\mathcal{B}}\mathcal{U}_{\mathcal{B}}. \tag*{(33)} R A ( ω ) := U A † K 0 ( ω ) U A , R B := U B † K B U B . (33)
For ω ∈ Ω s o l \omega\in\Omega_{\mathrm{sol}} ω ∈ Ω sol , Lemma 3.4 and Proposition 3.2 imply that R A ( ω ) \mathcal{R}_{\mathcal{A}}(\omega) R A ( ω ) and R B \mathcal{R}_{\mathcal{B}} R B are nonsingular and retain all nonzero eigenvalues and algebraic multiplicities of K 0 ( ω ) \mathcal{K}_{0}(\omega) K 0 ( ω ) and K B \mathcal{K}_{\mathcal{B}} K B , respectively.
Proposition 3.5. If ω ∈ Ω s o l \omega\in\Omega_{\mathrm{sol}} ω ∈ Ω sol , then R A ( ω ) + R A ( ω ) † \mathcal{R}_{\mathcal{A}}(\omega)+\mathcal{R}_{\mathcal{A}}(\omega)^{\dagger} R A ( ω ) + R A ( ω ) † and R B \mathcal{R}_{\mathcal{B}} R B are HPD. The following factorizations hold:
K 0 ( ω ) = U A R A ( ω ) U A † , K B = U B R B U B † . (34) \mathcal{K}_{0}(\omega)=\mathcal{U}_{\mathcal{A}}\mathcal{R}_{\mathcal{A}}(\omega)\mathcal{U}_{\mathcal{A}}^{\dagger},\qquad\mathcal{K}_{\mathcal{B}}=\mathcal{U}_{\mathcal{B}}\mathcal{R}_{\mathcal{B}}\mathcal{U}_{\mathcal{B}}^{\dagger}. \tag*{(34)} K 0 ( ω ) = U A R A ( ω ) U A † , K B = U B R B U B † . (34)
Proof. For any y ≠ 0 y \ne0 y = 0 , the vector K A † V A y \mathcal{K}_{A}^{\dagger}\mathcal{V}_{A}y K A † V A y is nonzero because V A ⊥ ker ( K A † ) \mathcal{V}_{A} \perp\ker(\mathcal{K}_{A}^{\dagger}) V A ⊥ ker ( K A † ) . The associated quadratic form satisfies
Re ( y † R A ( ω ) y ) = ( F 3 K A † V A y ) † ( M 0 + Re η ( ω ) M 1 ) ( F 3 K A † V A y ) > 0. \operatorname{Re}\left(y^{\dagger}\mathcal{R}_{A}(\omega)y\right)=\left(\mathcal{F}_{3}\mathcal{K}_{A}^{\dagger}\mathcal{V}_{A}y\right)^{\dagger}\left(\mathcal{M}_{0}+\operatorname{Re}\eta(\omega)\mathcal{M}_{1}\right)\left(\mathcal{F}_{3}\mathcal{K}_{A}^{\dagger}\mathcal{V}_{A}y\right)>0. Re ( y † R A ( ω ) y ) = ( F 3 K A † V A y ) † ( M 0 + Re η ( ω ) M 1 ) ( F 3 K A † V A y ) > 0.
Thus R A ( ω ) + R A ( ω ) † \mathcal{R}_{A}(\omega)+\mathcal{R}_{A}(\omega)^{\dagger} R A ( ω ) + R A ( ω ) † is HPD. Since V A V A † \mathcal{V}_{A}\mathcal{V}_{A}^{\dagger} V A V A † is the orthogonal projection onto V A \mathcal{V}_{A} V A , while Proposition 3.2 gives im ( K 0 ( ω ) ) = im ( K 0 ( ω ) † ) = V A \operatorname{im}(\mathcal{K}_{0}(\omega))=\operatorname{im}(\mathcal{K}_{0}(\omega)^{\dagger})=\mathcal{V}_{A} im ( K 0 ( ω )) = im ( K 0 ( ω ) † ) = V A , we have
V A V A † K 0 ( ω ) = K 0 ( ω ) = K 0 ( ω ) V A V A † . \mathcal{V}_{A}\mathcal{V}_{A}^{\dagger}\mathcal{K}_{0}(\omega)=\mathcal{K}_{0}(\omega)=\mathcal{K}_{0}(\omega)\mathcal{V}_{A}\mathcal{V}_{A}^{\dagger}. V A V A † K 0 ( ω ) = K 0 ( ω ) = K 0 ( ω ) V A V A † .
The two identities give
K 0 ( ω ) = V A V A † K 0 ( ω ) V A V A † = V A R A ( ω ) V A † . \mathcal{K}_{0}(\omega)=\mathcal{V}_{A}\mathcal{V}_{A}^{\dagger}\mathcal{K}_{0}(\omega)\mathcal{V}_{A}\mathcal{V}_{A}^{\dagger}=\mathcal{V}_{A}\mathcal{R}_{A}(\omega)\mathcal{V}_{A}^{\dagger}. K 0 ( ω ) = V A V A † K 0 ( ω ) V A V A † = V A R A ( ω ) V A † .
The same argument proves that R B \mathcal{R}_{B} R B is HPD and K B = V B R B V B † \mathcal{K}_{B}=\mathcal{V}_{B}\mathcal{R}_{B}\mathcal{V}_{B}^{\dagger} K B = V B R B V B † .
The factorizations (34) imply the block diagonalization of the compensated matrix. We summarize the conclusion as the theorem below.
Theorem 3.6. For ω ∈ Ω s o l \omega\in\Omega_{\mathrm{sol}} ω ∈ Ω sol and γ ≥ 0 \gamma\ge0 γ ≥ 0 , the unitary matrix in (32) satisfies
V † K γ ( ω ) V = ( R A ( ω ) γ R B 0 ) , (35) \mathcal{V}^{\dagger}\mathcal{K}_{\gamma}(\omega)\mathcal{V}=
\begin{pmatrix}
\mathcal{R}_{A}(\omega) & \\
& \gamma\mathcal{R}_{B} \\
& & 0
\end{pmatrix}, \tag*{(35)} V † K γ ( ω ) V = R A ( ω ) γ R B 0 , (35) where the zero block at (26) is omitted when V 0 = { 0 } \mathcal{V}_{0}=\{0\} V 0 = { 0 } .
Proof. The result follows by substituting (34) into (24) .
For the Hermitian case, we prove in [16 , 17 ] that the spectrum of K γ ( ⋅ ) \mathcal{K}_{\gamma}(\cdot) K γ ( ⋅ ) can be separated through the Courant-Fischer min-max principle, which does not hold for non-Hermitian matrices. Theorem 3.6 reveals that, when ω ∈ Ω s o l \omega\in\Omega_{\mathrm{sol}} ω ∈ Ω sol is fixed, the nonzero eigenvalues of K γ ( ω ) \mathcal{K}_{\gamma}(\omega) K γ ( ω ) consist of the nonzero eigenvalues of both K 0 ( ω ) \mathcal{K}_{0}(\omega) K 0 ( ω ) and γ K B \gamma\mathcal{K}_{B} γ K B , which is compatible with the Hermitian case.
For the nonlinear, non-Hermitian case, the unitary block argument also proves the equivalence between the original problem and its restriction.
Proposition 3.7. For every ω ∈ Ω s o l \omega\in\Omega_{\mathrm{sol}} ω ∈ Ω sol , the kernels satisfy
ker ( K 0 ( ω ) − ω 2 I 3 N 3 ) = V A ker ( R A ( ω ) − ω 2 I dim V A ) . (36) \ker\left(\mathcal{K}_{0}(\omega)-\omega^{2}I_{3N^{3}}\right)=\mathcal{V}_{A}\ker\left(\mathcal{R}_{A}(\omega)-\omega^{2}I_{\dim\mathcal{V}_{A}}\right). \tag*{(36)} ker ( K 0 ( ω ) − ω 2 I 3 N 3 ) = V A ker ( R A ( ω ) − ω 2 I d i m V A ) . (36) The correspondence x = V A y x=\mathcal{V}_{A}y x = V A y has inverse y = V A † x y=\mathcal{V}_{A}^{\dagger}x y = V A † x , and every vector on the left satisfies K B x = 0 \mathcal{K}_{B}x=0 K B x = 0 .
Proof. If K 0 ( ω ) x = ω 2 x \mathcal{K}_{0}(\omega)x=\omega^{2}x K 0 ( ω ) x = ω 2 x , then x ∈ im ( K 0 ( ω ) ) = V A x\in\operatorname{im}(\mathcal{K}_{0}(\omega))=\mathcal{V}_{A} x ∈ im ( K 0 ( ω )) = V A . Due to V A V A † x = x \mathcal{V}_{A}\mathcal{V}_{A}^{\dagger}x=x V A V A † x = x , left multiplication by V A † \mathcal{V}_{A}^{\dagger} V A † gives
R A ( ω ) ( V A † x ) = ω 2 ( V A † x ) , \mathcal{R}_{A}(\omega)(\mathcal{V}_{A}^{\dagger}x)=\omega^{2}(\mathcal{V}_{A}^{\dagger}x), R A ( ω ) ( V A † x ) = ω 2 ( V A † x ) , thus y = V A † x y=\mathcal{V}_{A}^{\dagger}x y = V A † x solves R A ( ω ) y = ω 2 y \mathcal{R}_{A}(\omega)y=\omega^{2}y R A ( ω ) y = ω 2 y . Conversely, (34) shows that x = V A y x=\mathcal{V}_{A}y x = V A y solves K 0 ( ω ) x = ω 2 x \mathcal{K}_{0}(\omega)x=\omega^{2}x K 0 ( ω ) x = ω 2 x for any y y y that solves R A ( ω ) y = ω 2 y \mathcal{R}_{A}(\omega)y=\omega^{2}y R A ( ω ) y = ω 2 y .
Theorem 3.8. If γ > 0 \gamma>0 γ > 0 satisfies
sup { ∣ ω ∣ 2 : ω ∈ Ω s o l } < γ min { λ > 0 : λ ∈ σ ( K B ) } , (37) \sup\left\{|\omega|^{2}:\omega\in\Omega_{\mathrm{sol}}\right\}<\gamma\min\left\{\lambda>0:\lambda\in\sigma(\mathcal{K}_{B})\right\}, \tag*{(37)} sup { ∣ ω ∣ 2 : ω ∈ Ω sol } < γ min { λ > 0 : λ ∈ σ ( K B ) } , (37) then the compensated problem (24) and the original constrained problem (20) have the same eigenpairs for ω ∈ Ω s o l \omega\in\Omega_{\mathrm{sol}} ω ∈ Ω sol .
Proof. The block diagonalization (35) gives
det ( K γ ( ω ) − ω 2 I 3 N 3 ) = det ( V † ( K γ ( ω ) − ω 2 I 3 N 3 ) V ) \det\left(\mathcal{K}_{\gamma}(\omega)-\omega^{2}I_{3N^{3}}\right)=\det\left(\mathcal{V}^{\dagger}\left(\mathcal{K}_{\gamma}(\omega)-\omega^{2}I_{3N^{3}}\right)\mathcal{V}\right) det ( K γ ( ω ) − ω 2 I 3 N 3 ) = det ( V † ( K γ ( ω ) − ω 2 I 3 N 3 ) V )
= det ( R A ( ω ) − ω 2 I dim V A ) det ( γ R B − ω 2 I dim V B ) ( − ω 2 ) dim V 0 . = \det\left(\mathcal{R}_{A}(\omega)-\omega^{2}I_{\dim\mathcal{V}_{A}}\right)\det\left(\gamma\mathcal{R}_{B}-\omega^{2}I_{\dim\mathcal{V}_{B}}\right)(-\omega^{2})^{\dim\mathcal{V}_{0}}. = det ( R A ( ω ) − ω 2 I d i m V A ) det ( γ R B − ω 2 I d i m V B ) ( − ω 2 ) d i m V 0 .
The condition (3.14) makes γ R B − ω 2 I dim V B \gamma\mathcal{R}_{B}-\omega^{2}I_{\dim\mathcal{V}_{B}} γ R B − ω 2 I d i m V B nonsingular. Since 0 ∉ Ω s o l 0\notin\Omega_{\mathrm{sol}} 0 ∈ / Ω sol , we have
det ( K γ ( ω ) − ω 2 I 3 N 3 ) = 0 ⟺ det ( R A ( ω ) − ω 2 I dim V A ) = 0. \det\left(\mathcal{K}_{\gamma}(\omega)-\omega^{2}I_{3N_{3}}\right)=0
\quad\Longleftrightarrow\quad
\det\left(\mathcal{R}_{A}(\omega)-\omega^{2}I_{\dim\mathcal{V}_{A}}\right)=0. det ( K γ ( ω ) − ω 2 I 3 N 3 ) = 0 ⟺ det ( R A ( ω ) − ω 2 I d i m V A ) = 0.
Therefore K γ ( ω ) x = ω 2 x \mathcal{K}_{\gamma}(\omega)x=\omega^{2}x K γ ( ω ) x = ω 2 x and det ( R A ( ω ) − ω 2 I dim V A ) = 0 \det\left(\mathcal{R}_{A}(\omega)-\omega^{2}I_{\dim\mathcal{V}_{A}}\right)=0 det ( R A ( ω ) − ω 2 I d i m V A ) = 0 have the same eigenfrequencies. The V B \mathcal{V}_{B} V B and V 0 \mathcal{V}_{0} V 0 blocks of K γ ( ω ) − ω 2 I \mathcal{K}_{\gamma}(\omega)-\omega^{2}I K γ ( ω ) − ω 2 I are nonsingular by (3.12), so every compensated eigenvector lies in V A \mathcal{V}_{A} V A . Proposition 3.7 then gives the assertion.
Preconditioning
The condition (3.14) places the positive compensation eigenvalues above all ∣ ω ∣ 2 |\omega|^{2} ∣ ω ∣ 2 in the search domain, so the compensation block cannot contribute an eigenfrequency there. In this paper, we use the penalty coefficient in [17 Remark 2.6] :
γ = { 4 π 2 , k = 0 or ∥ k ∥ 2 > 1 , 4 π 2 ∥ k ∥ 2 − 2 , 0 < ∥ k ∥ 2 ≤ 1. (38) \gamma=
\begin{cases}
4\pi^{2}, & \mathbf{k}=0\text{ or }\lVert\mathbf{k}\rVert_{2}>1,\\
4\pi^{2}\lVert\mathbf{k}\rVert_{2}^{-2}, & 0<\lVert\mathbf{k}\rVert_{2}\leq1.
\end{cases} \tag*{(38)} γ = { 4 π 2 , 4 π 2 ∥ k ∥ 2 − 2 , k = 0 or ∥ k ∥ 2 > 1 , 0 < ∥ k ∥ 2 ≤ 1. (38)
The Fourier symbols determine the smallest positive eigenvalue in (3.14) for each grid and Bloch wave vector. The chosen search domain must also satisfy this condition.
The frequency dependence of K γ ( ω ) \mathcal{K}_{\gamma}(\omega) K γ ( ω ) occurs only through M η ( ω ) \mathcal{M}_{\eta}(\omega) M η ( ω ) . We follow [16 , 17 ] and replace M η ( ω ) \mathcal{M}_{\eta}(\omega) M η ( ω ) by the identity to obtain the matrix K A K A † + γ K B \mathcal{K}_{A}\mathcal{K}_{A}^{\dagger}+\gamma\mathcal{K}_{B} K A K A † + γ K B . The resulting matrix and K γ ( ω ) \mathcal{K}_{\gamma}(\omega) K γ ( ω ) have the common kernel V 0 \mathcal{V}_{0} V 0 . We use the shifted preconditioner
K P : = K A K A † + γ K B + δ I 3 N 3 . (39) \mathcal{K}_{P}:=\mathcal{K}_{A}\mathcal{K}_{A}^{\dagger}+\gamma\mathcal{K}_{B}+\delta I_{3N_{3}}. \tag*{(39)} K P := K A K A † + γ K B + δ I 3 N 3 . (39)
In the implementation, the frozen matrix K γ ( ω ) + δ I \mathcal{K}_{\gamma}(\omega)+\delta I K γ ( ω ) + δ I and the preconditioner use the same nonnegative shift
δ = { π − 1 , k = 0 , ∥ k ∥ 2 , 0 < ∥ k ∥ 2 ≤ 1 , 0 , ∥ k ∥ 2 > 1. (40) \delta=
\begin{cases}
\pi^{-1}, & \mathbf{k}=0,\\
\lVert\mathbf{k}\rVert_{2}, & 0<\lVert\mathbf{k}\rVert_{2}\leq1,\\
0, & \lVert\mathbf{k}\rVert_{2}>1.
\end{cases} \tag*{(40)} δ = ⎩ ⎨ ⎧ π − 1 , ∥ k ∥ 2 , 0 , k = 0 , 0 < ∥ k ∥ 2 ≤ 1 , ∥ k ∥ 2 > 1. (40)
Under (3.5) and for γ > 0 \gamma>0 γ > 0 , Proposition 3.2 and (3.17) imply that K P \mathcal{K}_{P} K P is HPD. Its 3 × 3 3\times3 3 × 3 blocks are diagonal, so its inverse is applied elementwise. At k = 0 \mathbf{k}=0 k = 0 , the common shift replaces the three-dimensional harmonic zero block in (3.12) by δ I 3 \delta I_{3} δ I 3 . The shifted frozen matrix has the same eigenvectors as K γ \mathcal{K}_{\gamma} K γ , with every eigenvalue increased by δ \delta δ . The implementation orders the shifted Ritz values by modulus and subtracts δ \delta δ before the frequency update. This ordering can differ from the ordering of the unshifted eigenvalues by modulus. The following proposition gives the spectrum of the preconditioned system.
Proposition 3.9. For every ω ∈ Ω s o l \omega\in\Omega_{\mathrm{sol}} ω ∈ Ω sol , the spectrum of the symmetrically preconditioned matrix satisfies
σ ( K P − 1 2 ( K γ ( ω ) + δ I 3 N 3 ) K P − 1 2 ) ⊂ { 1 + t ( η ( ω ) − 1 ) : 0 ≤ t ≤ 1 } . (41) \sigma\left(\mathcal{K}_{P}^{-\frac{1}{2}}\left(\mathcal{K}_{\gamma}(\omega)+\delta I_{3N_{3}}\right)\mathcal{K}_{P}^{-\frac{1}{2}}\right)\subset\{1+t(\eta(\omega)-1):0\leq t\leq1\}. \tag*{(41)} σ ( K P − 2 1 ( K γ ( ω ) + δ I 3 N 3 ) K P − 2 1 ) ⊂ { 1 + t ( η ( ω ) − 1 ) : 0 ≤ t ≤ 1 } . (41)
Proof. The kernel compensation formulation with shift δ \delta δ can be rewritten as
K γ ( ω ) + δ I 3 N 3 = K P + ( η ( ω ) − 1 ) Q , \mathcal{K}_{\gamma}(\omega)+\delta I_{3N_{3}}=\mathcal{K}_{P}+(\eta(\omega)-1)Q, K γ ( ω ) + δ I 3 N 3 = K P + ( η ( ω ) − 1 ) Q ,
where Q Q Q is defined in (2.23). The definition of Q Q Q gives
K A K A † − Q = K A F 3 † M 0 F 3 K A † . \mathcal{K}_{A}\mathcal{K}_{A}^{\dagger}-Q=\mathcal{K}_{A}\mathcal{F}_{3}^{\dagger}\mathcal{M}_{0}\mathcal{F}_{3}\mathcal{K}_{A}^{\dagger}. K A K A † − Q = K A F 3 † M 0 F 3 K A † .
Since M 0 \mathcal{M}_{0} M 0 is positive semidefinite, the matrices satisfy
0 ≤ Q ≤ K A K A † ≤ K P . (42) 0\leq Q\leq\mathcal{K}_{A}\mathcal{K}_{A}^{\dagger}\leq\mathcal{K}_{P}. \tag*{(42)} 0 ≤ Q ≤ K A K A † ≤ K P . (42)
The two-sided preconditioned matrix therefore satisfies
K P − 1 2 ( K γ ( ω ) + δ I 3 N 3 ) K P − 1 2 = I 3 N 3 + ( η ( ω ) − 1 ) K P − 1 2 Q K P − 1 2 . (43) \mathcal{K}_{\mathcal{P}}^{-\frac{1}{2}}\left(\mathcal{K}_{\gamma}(\omega)+\delta I_{3N^3}\right)\mathcal{K}_{\mathcal{P}}^{-\frac{1}{2}}=I_{3N^3}+(\eta(\omega)-1)\mathcal{K}_{\mathcal{P}}^{-\frac{1}{2}}\mathcal{Q}\mathcal{K}_{\mathcal{P}}^{-\frac{1}{2}}. \tag*{(43)} K P − 2 1 ( K γ ( ω ) + δ I 3 N 3 ) K P − 2 1 = I 3 N 3 + ( η ( ω ) − 1 ) K P − 2 1 Q K P − 2 1 . (43)
The Hermitian matrix K P − 1 2 Q K P − 1 2 \mathcal{K}_{\mathcal{P}}^{-\frac{1}{2}}\mathcal{Q}\mathcal{K}_{\mathcal{P}}^{-\frac{1}{2}} K P − 2 1 Q K P − 2 1 has eigenvalues in [ 0 , 1 ] [0,1] [ 0 , 1 ] by (42) . Hence the matrix in (43) has eigenvalues of the form 1 + t ( η ( ω ) − 1 ) 1+t(\eta(\omega)-1) 1 + t ( η ( ω ) − 1 ) for some t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] .
For every eigenvalue λ \lambda λ in (41) , the assumption 0 < Re η ( ω ) < 1 0<\operatorname{Re}\eta(\omega)<1 0 < Re η ( ω ) < 1 in (5) gives
Re η ( ω ) ≤ Re λ ≤ 1 , Re η ( ω ) ≤ ∣ λ ∣ ≤ max { 1 , ∣ η ( ω ) ∣ } . (44) \operatorname{Re}\eta(\omega)\leq\operatorname{Re}\lambda\leq1,
\qquad
\operatorname{Re}\eta(\omega)\leq|\lambda|\leq\max\{1,|\eta(\omega)|\}. \tag*{(44)} Re η ( ω ) ≤ Re λ ≤ 1 , Re η ( ω ) ≤ ∣ λ ∣ ≤ max { 1 , ∣ η ( ω ) ∣ } . (44)
Since the two-sided matrix is normal, its condition number satisfies
κ 2 ( K P − 1 2 ( K γ ( ω ) + δ I 3 N 3 ) K P − 1 2 ) ≤ max { 1 , ∣ η ( ω ) ∣ } Re η ( ω ) . (45) \kappa_2\left(\mathcal{K}_{\mathcal{P}}^{-\frac{1}{2}}\left(\mathcal{K}_{\gamma}(\omega)+\delta I_{3N^3}\right)\mathcal{K}_{\mathcal{P}}^{-\frac{1}{2}}\right)\leq\frac{\max\{1,|\eta(\omega)|\}}{\operatorname{Re}\eta(\omega)}. \tag*{(45)} κ 2 ( K P − 2 1 ( K γ ( ω ) + δ I 3 N 3 ) K P − 2 1 ) ≤ Re η ( ω ) max { 1 , ∣ η ( ω ) ∣ } . (45)
The same bound holds for the condition number of the left-preconditioned operator in the K P \mathcal{K}_{\mathcal{P}} K P -weighted norm. When ∣ η ( ω ) ∣ < 1 |\eta(\omega)|<1 ∣ η ( ω ) ∣ < 1 , the upper bound in (45) becomes 1 Re η ( ω ) \frac{1}{\operatorname{Re}\eta(\omega)} Re η ( ω ) 1 . In the Hermitian case η ( ω ) = ε − 1 ( ω ) ∈ ( 0 , 1 ) \eta(\omega)=\varepsilon^{-1}(\omega)\in(0,1) η ( ω ) = ε − 1 ( ω ) ∈ ( 0 , 1 ) , the complex line segment in (41) reduces to [ ε − 1 ( ω ) , 1 ] [\varepsilon^{-1}(\omega),1] [ ε − 1 ( ω ) , 1 ] , and (45) reduces to κ 2 ≤ ε ( ω ) \kappa_2\leq\varepsilon(\omega) κ 2 ≤ ε ( ω ) . This recovers the preconditioning result in [16 ] .
In Section 4, we take δ = 0 \delta=0 δ = 0 and assume k ≠ 0 \mathbf{k}\ne\mathbf{0} k = 0 , γ > 0 \gamma>0 γ > 0 , and that (28) holds. Proposition 3.2 then gives V 0 = { 0 } \mathcal{V}_0=\{\mathbf{0}\} V 0 = { 0 } and implies that K P \mathcal{K}_{\mathcal{P}} K P is HPD.
Solution of the Nonlinear Eigenproblem
This section presents the iterative solution of the nonlinear eigenproblem. Subsection 4.1 introduces the linearized eigenproblem, the regularity of its eigenpairs, and the Generalized Davidson eigensolver. Subsection 4.2 presents the quasi-Newton iteration and the local regularity estimates used in its analysis. Subsection 4.3 analyzes local convergence with exact inner eigenpairs.
Linearized Eigenproblem
For each prescribed frequency ω ∈ Ω s o l \omega\in\Omega_{\mathrm{sol}} ω ∈ Ω sol , we freeze the frequency dependence of K γ ( ω ) \mathcal{K}_{\gamma}(\omega) K γ ( ω ) and solve a non-Hermitian eigenproblem. The linearized problem is
K γ ( ω ) u i ( ω ) = μ i ( ω ) u i ( ω ) , i = 1 , … , n e v , (46) \mathcal{K}_{\gamma}(\omega)\mathbf{u}_i(\omega)=\mu_i(\omega)\mathbf{u}_i(\omega),\qquad i=1,\ldots,\mathrm{nev}, \tag*{(46)} K γ ( ω ) u i ( ω ) = μ i ( ω ) u i ( ω ) , i = 1 , … , nev , (46)
where μ i ( ω ) \mu_i(\omega) μ i ( ω ) is the i i i -th eigenvalue in increasing order of magnitude, and u i ( ω ) \mathbf{u}_i(\omega) u i ( ω ) is the corresponding normalized right eigenvector. The number of desired eigenpairs is denoted by n e v \mathrm{nev} nev . Throughout this section, we assume that all desired eigenvalues are algebraically simple:
μ i ( ω ) is algebraically simple , ω ∈ Ω s o l , i = 1 , … , n e v . (47) \mu_i(\omega)\text{ is algebraically simple},\qquad\omega\in\Omega_{\mathrm{sol}},\qquad i=1,\ldots,\mathrm{nev}. \tag*{(47)} μ i ( ω ) is algebraically simple , ω ∈ Ω sol , i = 1 , … , nev . (47)
We also assume that the desired eigenvalues remain separated from the remaining spectrum and that their increasing order of magnitude does not change on Ω s o l \Omega_{\mathrm{sol}} Ω sol . Hence, μ i ( ω ) \mu_i(\omega) μ i ( ω ) consistently denotes the i i i -th desired eigenvalue. Algebraic simplicity makes the corresponding eigenspace one-dimensional, while unit normalization fixes the magnitude of u i ( ω ) \mathbf{u}_i(\omega) u i ( ω ) .
The following theorem establishes the local holomorphy of μ i \mu_i μ i and the regularity of its normalized eigenvectors.
Theorem 4.1. We assume that η \eta η is holomorphic near ω 0 ∈ Ω s o l \omega_0 \in\Omega_{\mathrm{sol}} ω 0 ∈ Ω sol and that μ i ( ω 0 ) \mu_i(\omega_0) μ i ( ω 0 ) is algebraically simple. The eigenvalue admits a locally holomorphic simple branch μ i ( ω ) \mu_i(\omega) μ i ( ω ) . The corresponding right and left eigenvectors can be chosen real analytic with ∥ u i ( ω ) ∥ 2 = 1 \lVert\mathbf{u}_i(\omega)\rVert_2 = 1 ∥ u i ( ω ) ∥ 2 = 1 and
K γ ( ω ) † v i ( ω ) ‾ = μ i ( ω ) ‾ v i ( ω ) ‾ , v i ( ω ) † u i ( ω ) = 1. (48) \mathcal{K}_{\gamma}(\omega)^\dagger\overline{\mathbf{v}_i(\omega)} = \overline{\mu_i(\omega)}\overline{\mathbf{v}_i(\omega)}, \qquad\mathbf{v}_i(\omega)^\dagger\mathbf{u}_i(\omega) = 1. \tag*{(48)} K γ ( ω ) † v i ( ω ) = μ i ( ω ) v i ( ω ) , v i ( ω ) † u i ( ω ) = 1. (48)
Proof. The matrix K γ \mathcal{K}_{\gamma} K γ is holomorphic wherever η \eta η is holomorphic. Theorem 1 of [7 ] therefore gives the locally holomorphic simple eigenvalue branch μ i \mu_i μ i . Theorem 2 of [7 ] gives a holomorphic right eigenvector x i \mathbf{x}_i x i and a holomorphic left eigenvector row y i † \mathbf{y}_i^\dagger y i † with y i † x i = 1 \mathbf{y}_i^\dagger\mathbf{x}_i = 1 y i † x i = 1 . We normalize them by
u i = x i ∥ x i ∥ 2 , v i = ∥ x i ∥ 2 y i . \mathbf{u}_i = \frac{\mathbf{x}_i}{\lVert\mathbf{x}_i\rVert_2}, \qquad\mathbf{v}_i = \lVert\mathbf{x}_i\rVert_2\mathbf{y}_i. u i = ∥ x i ∥ 2 x i , v i = ∥ x i ∥ 2 y i .
The positive function ∥ x i ∥ 2 \lVert\mathbf{x}_i\rVert_2 ∥ x i ∥ 2 and its reciprocal are real analytic on a sufficiently small neighborhood, so u i \mathbf{u}_i u i and v i \mathbf{v}_i v i are real analytic and satisfy (48) . □ \square □
The following proposition expresses the exact eigenvalue derivative through the right and left eigenvectors.
Proposition 4.2. Under the hypotheses of Theorem 4.1, the derivative of the simple eigenvalue branch satisfies
μ i ′ ( ω ) = v i ( ω ) † K γ ′ ( ω ) u i ( ω ) = η ′ ( ω ) v i ( ω ) † Q u i ( ω ) . (49) \mu_i'(\omega) = \mathbf{v}_i(\omega)^\dagger\mathcal{K}_{\gamma}'(\omega)\mathbf{u}_i(\omega) = \eta'(\omega)\mathbf{v}_i(\omega)^\dagger Q\mathbf{u}_i(\omega). \tag*{(49)} μ i ′ ( ω ) = v i ( ω ) † K γ ′ ( ω ) u i ( ω ) = η ′ ( ω ) v i ( ω ) † Q u i ( ω ) . (49)
Proof. The derivative formula in Theorem 1 of [7 ] and K γ ′ = η ′ Q \mathcal{K}_{\gamma}'=\eta'Q K γ ′ = η ′ Q give (49) . □ \square □
The right eigenpairs are computed by a Generalized Davidson method with thick restart and soft locking. The method maintains an orthonormal search basis Z \mathcal{Z} Z and solves a local eigenproblem defined by
( Z † K γ ( ω ) Z ) y j = θ j y j , (50) (\mathcal{Z}^\dagger\mathcal{K}_{\gamma}(\omega)\mathcal{Z})\mathbf{y}_j = \theta_j\mathbf{y}_j, \tag*{(50)} ( Z † K γ ( ω ) Z ) y j = θ j y j , (50)
during each iteration, where θ j \theta_j θ j and y j \mathbf{y}_j y j are an eigenvalue and the corresponding right unit eigenvector of the local matrix, respectively. Since K γ ( ω ) \mathcal{K}_{\gamma}(\omega) K γ ( ω ) is generally non-Hermitian, the vectors y j \mathbf{y}_j y j need not be mutually orthogonal. The approximate right eigenvector x j \mathbf{x}_j x j and residual r j \mathbf{r}_j r j are defined by
x j : = Z y j , r j : = K γ ( ω ) x j − θ j x j . (51) \mathbf{x}_j := \mathcal{Z}\mathbf{y}_j, \qquad\mathbf{r}_j := \mathcal{K}_{\gamma}(\omega)\mathbf{x}_j - \theta_j\mathbf{x}_j. \tag*{(51)} x j := Z y j , r j := K γ ( ω ) x j − θ j x j . (51)
During each iteration, the search space Z \mathcal{Z} Z is expanded by adding new directions computed from the preconditioned residuals K γ − 1 r j \mathcal{K}_{\gamma}^{-1}\mathbf{r}_j K γ − 1 r j to the columns. We preserve part of the columns of Z \mathcal{Z} Z and discard the rest when the number of columns of Z \mathcal{Z} Z reaches a given maximum. The complete procedure is summarized in Algorithm 1.
Algorithm 1 Generalized Davidson Method with Thick Restart and Soft Locking for Solving the Exterior Eigenpairs of the Non-Hermitian Matrix K γ ( ω ) \mathcal{K}_{\gamma}(\omega) K γ ( ω ) with a Fixed Frequency ω \omega ω .
Require: The matrix K γ ( ω ) \mathcal{K}_{\gamma}(\omega) K γ ( ω ) , the preconditioner K P − 1 \mathcal{K}_{P}^{-1} K P − 1 , an initial block Z 0 \mathcal{Z}_{0} Z 0 of rank m ≥ n e v m \ge\mathrm{nev} m ≥ nev , tolerance τ G D > 0 \tau_{\mathrm{GD}} > 0 τ GD > 0 , maximum dimension of the search space m max ≥ 2 m m_{\max} \ge2m m m a x ≥ 2 m .
Ensure: Approximate right eigenpairs ( μ i ( ω ) , u i ( ω ) ) (\mu_i(\omega),u_i(\omega)) ( μ i ( ω ) , u i ( ω )) for i = 1 , … , n e v i=1,\ldots,\mathrm{nev} i = 1 , … , nev .
Set Z ← orth ( Z 0 ) \mathcal{Z} \leftarrow\operatorname{orth}(\mathcal{Z}_{0}) Z ← orth ( Z 0 ) and W ← K γ ( ω ) Z \mathcal{W} \leftarrow\mathcal{K}_{\gamma}(\omega)\mathcal{Z} W ← K γ ( ω ) Z .
while the desired eigenpairs have not converged do
Compute H ← Z † W \mathcal{H} \leftarrow\mathcal{Z}^{\dagger}\mathcal{W} H ← Z † W and the local eigenproblem H y j = θ j y j \mathcal{H}y_j=\theta_j y_j H y j = θ j y j .
The algorithm arranges θ j \theta_j θ j in increasing order of magnitude and retains the first m m m pairs.
Compute x j ← Z y j x_j \leftarrow\mathcal{Z}y_j x j ← Z y j and residuals r j ← W y j − θ j x j r_j \leftarrow\mathcal{W}y_j-\theta_jx_j r j ← W y j − θ j x j for j = 1 , … , m j=1,\ldots,m j = 1 , … , m .
if max 1 ≤ j ≤ n e v ∥ r j ∥ 2 ≤ τ G D \max_{1\le j\le\mathrm{nev}}\lVert r_j\rVert_2 \le\tau_{\mathrm{GD}} max 1 ≤ j ≤ nev ∥ r j ∥ 2 ≤ τ GD then
Return ( θ i , x i ) (\theta_i,x_i) ( θ i , x i ) as ( μ i ( ω ) , u i ( ω ) ) (\mu_i(\omega),u_i(\omega)) ( μ i ( ω ) , u i ( ω )) for i = 1 , … , n e v i=1,\ldots,\mathrm{nev} i = 1 , … , nev .
end if
Find the unconverged indices I ← { j ∈ { 1 , … , m } : ∥ r j ∥ 2 > τ G D } \mathcal{I}\leftarrow\{j\in\{1,\ldots,m\}:\lVert r_j\rVert_2>\tau_{\mathrm{GD}}\} I ← { j ∈ { 1 , … , m } : ∥ r j ∥ 2 > τ GD } and set R ← ( r j ) j ∈ I \mathcal{R}\leftarrow(r_j)_{j\in\mathcal{I}} R ← ( r j ) j ∈ I .
if rank ( Z ) + ∣ I ∣ > m max \operatorname{rank}(\mathcal{Z})+|\mathcal{I}|>m_{\max} rank ( Z ) + ∣ I ∣ > m m a x then
The thick restart sets Z ← orth ( [ x 1 , … , x m ] ) \mathcal{Z}\leftarrow\operatorname{orth}([x_1,\ldots,x_m]) Z ← orth ([ x 1 , … , x m ]) and W ← K γ ( ω ) Z \mathcal{W}\leftarrow\mathcal{K}_{\gamma}(\omega)\mathcal{Z} W ← K γ ( ω ) Z .
end if
Compute the new directions by preconditioning the unconverged residuals: T ← K P − 1 R \mathcal{T}\leftarrow\mathcal{K}_{P}^{-1}\mathcal{R} T ← K P − 1 R .
Apply T ← ( I 3 N 3 − Z Z † ) T \mathcal{T}\leftarrow(\mathcal{I}_{3N^3}-\mathcal{Z}\mathcal{Z}^{\dagger})\mathcal{T} T ← ( I 3 N 3 − Z Z † ) T , then orthogonalize T ← orth ( T ) \mathcal{T}\leftarrow\operatorname{orth}(\mathcal{T}) T ← orth ( T ) .
Expand the space Z ← [ Z , T ] \mathcal{Z}\leftarrow[\mathcal{Z},\mathcal{T}] Z ← [ Z , T ] and W ← [ W , K γ ( ω ) T ] \mathcal{W}\leftarrow[\mathcal{W},\mathcal{K}_{\gamma}(\omega)\mathcal{T}] W ← [ W , K γ ( ω ) T ] .
end while
Within the Davidson iteration, orth ( ⋅ ) \operatorname{orth}(\cdot) orth ( ⋅ ) uses Cholesky QR only for the restarted basis and projected preconditioned residual blocks. Although forming the Gram matrix squares the block condition number, these factorizations are numerically stable in our computations and more efficient than Householder QR.
Remark 4.1. The projected Jacobi–Davidson correction associated with K P \mathcal{K}_{P} K P replaces lines 13–14 of Algorithm 1 by
( I 3 N 3 − Z Z † ) K P ( I 3 N 3 − Z Z † ) T = − R , Z † T = 0. (\mathcal{I}_{3N^3}-\mathcal{Z}\mathcal{Z}^{\dagger})\mathcal{K}_{P}(\mathcal{I}_{3N^3}-\mathcal{Z}\mathcal{Z}^{\dagger})\mathcal{T}=-\mathcal{R},\qquad\mathcal{Z}^{\dagger}\mathcal{T}=0. ( I 3 N 3 − Z Z † ) K P ( I 3 N 3 − Z Z † ) T = − R , Z † T = 0.
Its solution is
T = − K P − 1 R + K P − 1 Z ( Z † K P − 1 Z ) − 1 Z † K P − 1 R . \mathcal{T}=-\mathcal{K}_{P}^{-1}\mathcal{R}+\mathcal{K}_{P}^{-1}\mathcal{Z}(\mathcal{Z}^{\dagger}\mathcal{K}_{P}^{-1}\mathcal{Z})^{-1}\mathcal{Z}^{\dagger}\mathcal{K}_{P}^{-1}\mathcal{R}. T = − K P − 1 R + K P − 1 Z ( Z † K P − 1 Z ) − 1 Z † K P − 1 R .
This requires computing and storing K P − 1 Z \mathcal{K}_{P}^{-1}\mathcal{Z} K P − 1 Z . Algorithm 1 avoids this additional cost by applying K P − 1 \mathcal{K}_{P}^{-1} K P − 1 only to the unconverged residuals R \mathcal{R} R .
Remark 4.2. We preallocate Z \mathcal{Z} Z and W = K γ Z \mathcal{W}=\mathcal{K}_{\gamma}\mathcal{Z} W = K γ Z with m max m_{\max} m m a x columns, requiring O ( m max N 3 ) O(m_{\max}N^3) O ( m m a x N 3 ) storage. Each expansion applies K γ \mathcal{K}_{\gamma} K γ only to at most m m m new directions at a cost of O ( m N 3 log N ) O(mN^3\log N) O ( m N 3 log N ) , while residual preconditioning costs O ( m N 3 ) O(mN^3) O ( m N 3 ) . Projection and orthogonalization cost at most O ( m max 2 N 3 ) O(m_{\max}^{2}N^3) O ( m m a x 2 N 3 ) , and the dense projected eigensolve costs O ( m max 3 ) O(m_{\max}^{3}) O ( m m a x 3 ) . A restart recomputes the operator action on the retained basis. The total cost per outer step depends on the numbers of expansions and restarts.
Quasi-Newton Iteration
The i i i -th characteristic frequency of K γ ( ω ) x = ω 2 x \mathcal{K}_{\gamma}(\omega)x=\omega^2x K γ ( ω ) x = ω 2 x is a root of
ω 2 − μ i ( ω ) = 0. (52) \omega^2-\mu_i(\omega)=0. \tag*{(52)} ω 2 − μ i ( ω ) = 0. (52)
In [16 ] , we apply Newton iteration to solve the corresponding nonlinear equation in the Hermitian case. The exact Newton update for (52) is
ω i ( k + 1 ) ← ω i ( k ) − ( ω i ( k ) ) 2 − μ i ( ω i ( k ) ) 2 ω i ( k ) − μ i ′ ( ω i ( k ) ) . (53) \omega_i^{(k+1)}\leftarrow\omega_i^{(k)}-\frac{(\omega_i^{(k)})^2-\mu_i(\omega_i^{(k)})}{2\omega_i^{(k)}-\mu_i'(\omega_i^{(k)})}. \tag*{(53)} ω i ( k + 1 ) ← ω i ( k ) − 2 ω i ( k ) − μ i ′ ( ω i ( k ) ) ( ω i ( k ) ) 2 − μ i ( ω i ( k ) ) . (53)
where ω i ( k ) \omega_i^{(k)} ω i ( k ) denotes the approximate i i i -th frequency after k k k iterations. Since the formula for μ i ′ \mu_i' μ i ′ in (49) involves both left and right eigenvectors, we replace μ i ′ ( ω ) \mu_i'(\omega) μ i ′ ( ω ) by u i ( ω ) † K γ ′ ( ω ) u i ( ω ) u_i(\omega)^{\dagger}\mathcal{K}_{\gamma}'(\omega)u_i(\omega) u i ( ω ) † K γ ′ ( ω ) u i ( ω ) as an approximate derivative. We denote the right Rayleigh quotient with respect to Q Q Q as
q i ( ω ) : = u i ( ω ) † Q u i ( ω ) . (54) q_i(\omega) := u_i(\omega)^\dagger Q u_i(\omega). \tag*{(54)} q i ( ω ) := u i ( ω ) † Q u i ( ω ) . (54)
The quasi-Newton update is defined by
ω i ( k + 1 ) ← ω i ( k ) − ( ω i ( k ) ) 2 − μ i ( ω i ( k ) ) 2 ω i ( k ) − ( η ′ q i ) ( ω i ( k ) ) . (55) \omega_i^{(k+1)} \leftarrow\omega_i^{(k)} - \frac{(\omega_i^{(k)})^2-\mu_i(\omega_i^{(k)})}{2\omega_i^{(k)}-(\eta' q_i)(\omega_i^{(k)})}. \tag*{(55)} ω i ( k + 1 ) ← ω i ( k ) − 2 ω i ( k ) − ( η ′ q i ) ( ω i ( k ) ) ( ω i ( k ) ) 2 − μ i ( ω i ( k ) ) . (55)
In general, ( η ′ q i ) ( ω ) (\eta' q_i)(\omega) ( η ′ q i ) ( ω ) differs from μ i ′ ( ω ) \mu_i'(\omega) μ i ′ ( ω ) for the non-normal, non-Hermitian matrix K γ ( ω ) K_\gamma(\omega) K γ ( ω ) .
At frequencies with ∣ ω i ( k ) ∣ > 10 − 10 |\omega_i^{(k)}| > 10^{-10} ∣ ω i ( k ) ∣ > 1 0 − 10 , we accept the quasi-Newton candidate only when it and its inverse dielectric coefficient are finite and the numerical safeguard conditions are satisfied:
∣ 2 ω i ( k ) − ( η ′ q i ) ( ω i ( k ) ) ∣ > 10 − 30 , Re η ( ω i ( k + 1 ) ) ≥ 0. (56) \left|2\omega_i^{(k)}-(\eta' q_i)(\omega_i^{(k)})\right| > 10^{-30}, \qquad\operatorname{Re}\eta(\omega_i^{(k+1)}) \ge0. \tag*{(56)} 2 ω i ( k ) − ( η ′ q i ) ( ω i ( k ) ) > 1 0 − 30 , Re η ( ω i ( k + 1 ) ) ≥ 0. (56)
Otherwise we set ω i ( k + 1 ) ← μ i ( ω i ( k ) ) \omega_i^{(k+1)} \leftarrow\sqrt{\mu_i(\omega_i^{(k)})} ω i ( k + 1 ) ← μ i ( ω i ( k ) ) . The local convergence analysis concerns frequencies in Ω s o l \Omega_{\mathrm{sol}} Ω sol ; the numerical safeguard allows a wider set of candidates. The nonlinear residual of each step is defined by
r i ( k + 1 ) : = K γ ( ω i ( k + 1 ) ) u i ( ω i ( k ) ) − ( ω i ( k + 1 ) ) 2 u i ( ω i ( k ) ) . (57) r_i^{(k+1)} := K_\gamma(\omega_i^{(k+1)})u_i(\omega_i^{(k)})-(\omega_i^{(k+1)})^2u_i(\omega_i^{(k)}). \tag*{(57)} r i ( k + 1 ) := K γ ( ω i ( k + 1 ) ) u i ( ω i ( k ) ) − ( ω i ( k + 1 ) ) 2 u i ( ω i ( k ) ) . (57)
The iteration terminates when ∥ r i ( k + 1 ) ∥ 2 ≤ τ N E P \lVert r_i^{(k+1)}\rVert_2 \le\tau_{\mathrm{NEP}} ∥ r i ( k + 1 ) ∥ 2 ≤ τ NEP . Algorithm 2 summarizes the procedure of the quasi-Newton method. The returned vector is computed at the preceding outer frequency; (57) tests the approximate eigenpair at the accepted new frequency. The complete-band and tolerance experiments use the inner tolerance
τ G D = 0.9 τ N E P . (58) \tau_{\mathrm{GD}} = 0.9\tau_{\mathrm{NEP}}. \tag*{(58)} τ GD = 0.9 τ NEP . (58)
Subsection 5.4 specifies the tolerances used for the convergence histories.
Algorithm 2 A Quasi-Newton Method for Solving the Nonlinear Eigenproblem.
Require: Matrix-valued function K γ ( ω ) K_\gamma(\omega) K γ ( ω ) , initial frequency ω 1 ( 0 ) \omega_1^{(0)} ω 1 ( 0 ) , number of required eigenpairs nev, and tolerances τ N E P \tau_{\mathrm{NEP}} τ NEP and τ G D \tau_{\mathrm{GD}} τ GD .
Ensure: Approximate frequencies ω i \omega_i ω i and corresponding right eigenvectors x i x_i x i
for i = 1 , … , n e v i = 1,\ldots,\mathrm{nev} i = 1 , … , nev .
for i = 1 , … , n e v i = 1,\ldots,\mathrm{nev} i = 1 , … , nev do
for k = 0 , … k = 0,\ldots k = 0 , … do
Compute the normalized i i i -th right eigenpair ( μ i ( ω i ( k ) ) , u i ( ω i ( k ) ) ) (\mu_i(\omega_i^{(k)}),u_i(\omega_i^{(k)})) ( μ i ( ω i ( k ) ) , u i ( ω i ( k ) )) by the Generalized Davidson method in Algorithm 1 with i i i target eigenpairs and tolerance τ G D \tau_{\mathrm{GD}} τ GD .
Compute q i ( ω i ( k ) ) ← u i ( ω i ( k ) ) † Q u i ( ω i ( k ) ) q_i(\omega_i^{(k)}) \leftarrow u_i(\omega_i^{(k)})^\dagger Q u_i(\omega_i^{(k)}) q i ( ω i ( k ) ) ← u i ( ω i ( k ) ) † Q u i ( ω i ( k ) ) .
Apply (55) , or use ω i ( k + 1 ) ← μ i ( ω i ( k ) ) \omega_i^{(k+1)} \leftarrow\sqrt{\mu_i(\omega_i^{(k)})} ω i ( k + 1 ) ← μ i ( ω i ( k ) ) if the acceptance checks above fail.
Compute the nonlinear residual r i ( k + 1 ) r_i^{(k+1)} r i ( k + 1 ) by (57) . Break the loop if ∥ r i ( k + 1 ) ∥ 2 ≤ τ N E P \lVert r_i^{(k+1)}\rVert_2 \le\tau_{\mathrm{NEP}} ∥ r i ( k + 1 ) ∥ 2 ≤ τ NEP .
end for
Set ω i ← ω i ( k + 1 ) \omega_i \leftarrow\omega_i^{(k+1)} ω i ← ω i ( k + 1 ) and x i ← u i ( ω i ( k ) ) x_i \leftarrow u_i(\omega_i^{(k)}) x i ← u i ( ω i ( k ) ) .
if i < n e v i < \mathrm{nev} i < nev then
Set ω i + 1 ( 0 ) ← μ i + 1 ( ω i ( k ) ) \omega_{i+1}^{(0)} \leftarrow\sqrt{\mu_{i+1}(\omega_i^{(k)})} ω i + 1 ( 0 ) ← μ i + 1 ( ω i ( k ) ) using the additional Ritz value retained by the inner solve.
end if
end for
The retained block size m > i m > i m > i in Algorithm 1 increases with the current target i i i . The additional Ritz value used to initialize the next frequency need not satisfy the inner stopping tolerance. The fixed-point step uses the principal square root. For the next-frequency initialization, its sign is chosen closest to the preceding frequency. Theorem 4.1 implies that q i : R 2 → R q_i : \mathbb{R}^2 \to\mathbb{R} q i : R 2 → R and η ′ q i : R 2 → C \eta' q_i : \mathbb{R}^2 \to\mathbb{C} η ′ q i : R 2 → C are locally real analytic, with ω = x + i y \omega= x+\mathrm{i}y ω = x + i y identified with ( x , y ) (x,y) ( x , y ) . We write
∇ q i : = ( ∂ x q i , ∂ y q i ) , \nabla q_i := (\partial_x q_i,\partial_y q_i), ∇ q i := ( ∂ x q i , ∂ y q i ) ,
and define its product with e ∈ C e \in\mathbb{C} e ∈ C as
⟨ ∇ q i , e ⟩ : = ( ∂ x q i ) Re e + ( ∂ y q i ) Im e . \langle\nabla q_i,e\rangle:= (\partial_x q_i)\operatorname{Re}e + (\partial_y q_i)\operatorname{Im}e. ⟨ ∇ q i , e ⟩ := ( ∂ x q i ) Re e + ( ∂ y q i ) Im e .
Since q i q_i q i is real-valued, it can be holomorphic only if it is locally constant. For a general frequency ω \omega ω , we omit the argument “( ω ) (\omega) ( ω ) ” hereafter. The superscript “∗ * ∗ ” along with the subscript “i i i ” denotes the evaluation at ω i ∗ \omega_i^* ω i ∗ , for example:
q i ∗ = q i ( ω i ∗ ) , ( η i ′ ) ∗ = η ′ ( ω i ∗ ) , ( ∂ x q i ) ∗ = ∂ x q i ( ω i ∗ ) . q_i^* = q_i(\omega_i^*), \qquad(\eta_i')^* = \eta'(\omega_i^*), \qquad(\partial_x q_i)^* = \partial_x q_i(\omega_i^*). q i ∗ = q i ( ω i ∗ ) , ( η i ′ ) ∗ = η ′ ( ω i ∗ ) , ( ∂ x q i ) ∗ = ∂ x q i ( ω i ∗ ) .
We further assume that
Re η ′ < 0 , for ω ∈ Ω s o l . (59) \operatorname{Re}\eta' < 0, \qquad\text{for }\omega\in\Omega_{\mathrm{sol}}. \tag*{(59)} Re η ′ < 0 , for ω ∈ Ω sol . (59)
For real frequencies with ε > 0 \varepsilon> 0 ε > 0 and ε ′ > 0 \varepsilon' > 0 ε ′ > 0 , this follows from η ′ = − ε ′ ε 2 < 0 \eta' = -\frac{\varepsilon'}{\varepsilon^2} < 0 η ′ = − ε 2 ε ′ < 0 . Continuity preserves the strict inequality under sufficiently small complex perturbations. For Re ω > 0 \operatorname{Re}\omega> 0 Re ω > 0 , the update denominator satisfies
∣ 2 ω − η ′ q i ∣ ≥ Re ( 2 ω − η ′ q i ) = 2 Re ω − ( Re η ′ ) q i > 0. (60) \lvert2\omega-\eta' q_i\rvert\ge\operatorname{Re}(2\omega-\eta' q_i) = 2\operatorname{Re}\omega-(\operatorname{Re}\eta')q_i > 0. \tag*{(60)} ∣ 2 ω − η ′ q i ∣ ≥ Re ( 2 ω − η ′ q i ) = 2 Re ω − ( Re η ′ ) q i > 0. (60)
This bound is uniform on a sufficiently small closed neighborhood of each frequency in Ω s o l \Omega_{\mathrm{sol}} Ω sol with Re ω > 0 \operatorname{Re}\omega> 0 Re ω > 0 . The safeguard (56) checks the denominator numerically.
Analysis of Convergence
In this subsection, we analyze the generally linear local convergence of the quasi-Newton iteration and estimate its linear factor through the gradient of q i q_i q i . Throughout this subsection, we assume γ > 0 \gamma> 0 γ > 0 .
Expansion of the Error Term
We analyze the update (55) with exact eigenpairs. We denote the frequency error after k k k iterations by e i ( k ) : = ω i ( k ) − ω i ∗ e_i^{(k)} := \omega_i^{(k)}-\omega_i^* e i ( k ) := ω i ( k ) − ω i ∗ . The following proposition gives the local error expansion, with ρ i ∗ \rho_i^* ρ i ∗ evaluated at ω i ∗ \omega_i^* ω i ∗ .
Proposition 4.3. We assume that ω i ∗ ∈ Ω s o l \omega_i^* \in\Omega_{\mathrm{sol}} ω i ∗ ∈ Ω sol has positive real part and satisfies
( ω i ∗ ) 2 − μ i ∗ = 0 , 2 ω i ∗ − ( μ i ′ ) ∗ ≠ 0. (61) (\omega_i^*)^2-\mu_i^* = 0, \qquad2\omega_i^*-(\mu_i')^* \ne0. \tag*{(61)} ( ω i ∗ ) 2 − μ i ∗ = 0 , 2 ω i ∗ − ( μ i ′ ) ∗ = 0. (61) For ω i ( k ) \omega_i^{(k)} ω i ( k ) sufficiently close to ω i ∗ \omega_i^* ω i ∗ , the error e i ( k ) e_i^{(k)} e i ( k ) satisfies
e i ( k + 1 ) = ρ i ∗ e i ( k ) + O ( ∣ e i ( k ) ∣ 2 ) . (62) e_i^{(k+1)} = \rho_i^* e_i^{(k)} + O\left(\lvert e_i^{(k)}\rvert^2\right). \tag*{(62)} e i ( k + 1 ) = ρ i ∗ e i ( k ) + O ( ∣ e i ( k ) ∣ 2 ) . (62) Here, the linear error factor ρ i \rho_i ρ i is defined by
ρ i : = μ i ′ − η ′ q i 2 ω − η ′ q i = η ′ ( v i − u i ) † Q u i 2 ω − η ′ q i . (63) \rho_i := \frac{\mu_i'-\eta' q_i}{2\omega-\eta' q_i} = \frac{\eta'(\boldsymbol{v}_i-\boldsymbol{u}_i)^\dagger\mathcal{Q}\boldsymbol{u}_i}{2\omega-\eta' q_i}. \tag*{(63)} ρ i := 2 ω − η ′ q i μ i ′ − η ′ q i = 2 ω − η ′ q i η ′ ( v i − u i ) † Q u i . (63) Proof. The holomorphy of μ i \mu_i μ i and the root condition (61) give
( ω i ∗ + e i ( k ) ) 2 − μ i ( ω i ∗ + e i ( k ) ) = ( 2 ω i ∗ − ( μ i ′ ) ∗ ) e i ( k ) + O ( ∣ e i ( k ) ∣ 2 ) . (\omega_i^*+e_i^{(k)})^2-\mu_i(\omega_i^*+e_i^{(k)}) = (2\omega_i^*-(\mu_i')^*)e_i^{(k)} + O\left(\lvert e_i^{(k)}\rvert^2\right). ( ω i ∗ + e i ( k ) ) 2 − μ i ( ω i ∗ + e i ( k ) ) = ( 2 ω i ∗ − ( μ i ′ ) ∗ ) e i ( k ) + O ( ∣ e i ( k ) ∣ 2 ) . The real analyticity of q i q_i q i and the denominator bound (60) also give
1 2 ( ω i ∗ + e i ( k ) ) − η ′ q i ( ω i ∗ + e i ( k ) ) = 1 2 ω i ∗ − ( η i ′ ) ∗ q i ∗ + O ( ∣ e i ( k ) ∣ ) . \frac{1}{2(\omega_i^*+e_i^{(k)})-\eta' q_i(\omega_i^*+e_i^{(k)})}
=
\frac{1}{2\omega_i^*-(\eta_i')^*q_i^*}
+O\left(\lvert e_i^{(k)}\rvert\right). 2 ( ω i ∗ + e i ( k ) ) − η ′ q i ( ω i ∗ + e i ( k ) ) 1 = 2 ω i ∗ − ( η i ′ ) ∗ q i ∗ 1 + O ( ∣ e i ( k ) ∣ ) . Substitution into (55) yields
e i ( k + 1 ) = ( 1 − 2 ω i ∗ − ( μ i ′ ) ∗ 2 ω i ∗ − ( η i ′ ) ∗ q i ∗ ) e i ( k ) + O ( ∣ e i ( k ) ∣ 2 ) (64) e_i^{(k+1)}
=
\left(1-\frac{2\omega_i^*-(\mu_i')^*}{2\omega_i^*-(\eta_i')^*q_i^*}\right)e_i^{(k)}
+O\left(\lvert e_i^{(k)}\rvert^2\right) \tag*{(64)} e i ( k + 1 ) = ( 1 − 2 ω i ∗ − ( η i ′ ) ∗ q i ∗ 2 ω i ∗ − ( μ i ′ ) ∗ ) e i ( k ) + O ( ∣ e i ( k ) ∣ 2 ) (64) = ρ i ∗ e i ( k ) + O ( ∣ e i ( k ) ∣ 2 ) . = \rho_i^*e_i^{(k)}+O\left(\lvert e_i^{(k)}\rvert^2\right). = ρ i ∗ e i ( k ) + O ( ∣ e i ( k ) ∣ 2 ) .
The last equality uses (63) . Thus (64) proves (62) .
For the exact Newton update (53) , the same Taylor expansion with μ i ′ \mu_i' μ i ′ in the denominator cancels the linear term and gives local quadratic convergence at a simple root. For (55) , the expansion gives local linear convergence when 0 < ∣ ρ i ∗ ∣ < 1 0 < |\rho_i^*| < 1 0 < ∣ ρ i ∗ ∣ < 1 and at least quadratic convergence when ρ i ∗ = 0 \rho_i^* = 0 ρ i ∗ = 0 .
The following proposition expresses the linear factor ρ i \rho_i ρ i in terms of the gradient of q i q_i q i .
Proposition 4.4. Under the assumptions of Theorem 4.1 , the factor ρ i \rho_i ρ i satisfies
ρ i = Im η 2 ω − η ′ q i ( ∂ y q i + i ∂ x q i ) . (65) \rho_i = \frac{\operatorname{Im}\eta}{2\omega-\eta' q_i}\left(\partial_y q_i+\mathrm{i}\partial_x q_i\right). \tag*{(65)} ρ i = 2 ω − η ′ q i Im η ( ∂ y q i + i ∂ x q i ) . (65) As a result, the modulus ∣ ρ i ∣ |\rho_i| ∣ ρ i ∣ equals
∣ ρ i ∣ = ∣ Im η ∣ ∣ 2 ω − η ′ q i ∣ ∣ ∇ q i ∣ . (66) |\rho_i| = \frac{|\operatorname{Im}\eta|}{|2\omega-\eta' q_i|}|\nabla q_i|. \tag*{(66)} ∣ ρ i ∣ = ∣2 ω − η ′ q i ∣ ∣ Im η ∣ ∣∇ q i ∣. (66) Proof. The real and imaginary parts of μ i = u i † K P u i + ( η − 1 ) q i \mu_i=\mathbf{u}_i^\dagger\mathcal{K}_{\mathcal{P}}\mathbf{u}_i+(\eta-1)q_i μ i = u i † K P u i + ( η − 1 ) q i give
q i ≤ Re μ i Re η , Im μ i = q i Im η , (67) q_i\le\frac{\operatorname{Re}\mu_i}{\operatorname{Re}\eta},\qquad\operatorname{Im}\mu_i=q_i\operatorname{Im}\eta, \tag*{(67)} q i ≤ Re η Re μ i , Im μ i = q i Im η , (67) respectively. The Cauchy–Riemann equations give
μ i ′ = ∂ x ( Re μ i ) + i ∂ x ( Im μ i ) = ∂ y ( Im μ i ) + i ∂ x ( Im μ i ) . \mu_i'=\partial_x(\operatorname{Re}\mu_i)+\mathrm{i}\partial_x(\operatorname{Im}\mu_i)=\partial_y(\operatorname{Im}\mu_i)+\mathrm{i}\partial_x(\operatorname{Im}\mu_i). μ i ′ = ∂ x ( Re μ i ) + i ∂ x ( Im μ i ) = ∂ y ( Im μ i ) + i ∂ x ( Im μ i ) . The relation Im μ i = q i Im η \operatorname{Im}\mu_i=q_i\operatorname{Im}\eta Im μ i = q i Im η yields
μ i ′ = η ′ q i + Im η ( ∂ y q i + i ∂ x q i ) . (68) \mu_i'=\eta' q_i+\operatorname{Im}\eta\left(\partial_y q_i+\mathrm{i}\partial_x q_i\right). \tag*{(68)} μ i ′ = η ′ q i + Im η ( ∂ y q i + i ∂ x q i ) . (68) The formulas (68) and (63) give (65) .
The representation (66) reduces the estimate of ∣ ρ i ∣ |\rho_i| ∣ ρ i ∣ to a bound on ∣ ∇ q i ∣ |\nabla q_i| ∣∇ q i ∣ . The next subsection derives this bound from the relative spectral gap of the Hermitian part.
Gradient Bound from Spectral Regularity
For the real-valued function q i = q i ( x , y ) q_i=q_i(x,y) q i = q i ( x , y ) , (49) and (68) give
∣ Im η ∣ ∣ ∇ q i ∣ = ∣ η ′ ∣ ∣ ( v i − u i ) † Q u i ∣ . (69) |\operatorname{Im}\eta|\,|\nabla q_i|=|\eta'|\,|(\mathbf{v}_i-\mathbf{u}_i)^\dagger\mathcal{Q}\mathbf{u}_i|. \tag*{(69)} ∣ Im η ∣ ∣∇ q i ∣ = ∣ η ′ ∣ ∣ ( v i − u i ) † Q u i ∣. (69)
We bound ∣ ( v i − u i ) † Q u i ∣ |(\mathbf{v}_i-\mathbf{u}_i)^\dagger\mathcal{Q}\mathbf{u}_i| ∣ ( v i − u i ) † Q u i ∣ by comparing the eigenpairs of K γ \mathcal{K}_\gamma K γ with those of its Hermitian part
H γ : = K γ + K γ † 2 . (70) \mathcal{H}_\gamma:=\frac{\mathcal{K}_\gamma+\mathcal{K}_\gamma^\dagger}{2}. \tag*{(70)} H γ := 2 K γ + K γ † . (70)
Under the standing assumptions, (42) and 0 < Re η < 1 0<\operatorname{Re}\eta<1 0 < Re η < 1 give
H γ = K P − ( 1 − Re η ) Q ⪰ ( Re η ) K P ≻ 0. \mathcal{H}_\gamma=\mathcal{K}_{\mathcal{P}}-(1-\operatorname{Re}\eta)\mathcal{Q}\succeq(\operatorname{Re}\eta)\mathcal{K}_{\mathcal{P}}\succ0. H γ = K P − ( 1 − Re η ) Q ⪰ ( Re η ) K P ≻ 0.
We use an orthonormal eigenbasis { w j } \{\mathbf{w}_j\} { w j } with H γ w j = ν j w j \mathcal{H}_\gamma\mathbf{w}_j=\nu_j\mathbf{w}_j H γ w j = ν j w j and the ν j \nu_j ν j in nondecreasing order. The next proposition bounds the difference of μ i \mu_i μ i and ν i \nu_i ν i using the relative Bauer–Fike estimate [6 ] . For any HPD matrix H \mathcal{H} H and perturbation matrix E \mathcal{E} E , each eigenvalue λ ∈ σ ( H + E ) \lambda\in\sigma(\mathcal{H}+\mathcal{E}) λ ∈ σ ( H + E ) satisfies
min ν ∈ σ ( H ) ∣ 1 − λ ν ∣ ≤ ∥ H − 1 2 E H − 1 2 ∥ 2 . (71) \min_{\nu\in\sigma(\mathcal{H})}\left|1-\frac{\lambda}{\nu}\right|\le\left\|\mathcal{H}^{-\frac{1}{2}}\mathcal{E}\mathcal{H}^{-\frac{1}{2}}\right\|_2. \tag*{(71)} ν ∈ σ ( H ) min 1 − ν λ ≤ H − 2 1 E H − 2 1 2 . (71)
Indeed, I − λ H − 1 + H − 1 2 E H − 1 2 I-\lambda\mathcal{H}^{-1}+\mathcal{H}^{-\frac{1}{2}}\mathcal{E}\mathcal{H}^{-\frac{1}{2}} I − λ H − 1 + H − 2 1 E H − 2 1 is singular. The smallest singular value of the normal matrix I − λ H − 1 I-\lambda\mathcal{H}^{-1} I − λ H − 1 is therefore bounded by the perturbation norm, which gives (71) .
Proposition 4.5. We assume that ν i \nu_i ν i is simple and that its relative gap satisfies
Δ i : = min j ≠ i ∣ ν i − ν j ∣ ν i + ν j > ∣ Im η ∣ Re η . (72) \Delta_i := \min_{j\ne i}\frac{|\nu_i-\nu_j|}{\nu_i+\nu_j} > \frac{|\operatorname{Im}\eta|}{\operatorname{Re}\eta}. \tag*{(72)} Δ i := j = i min ν i + ν j ∣ ν i − ν j ∣ > Re η ∣ Im η ∣ . (72) Then the i i i -th eigenvalue μ i \mu_i μ i of K γ \mathcal{K}_\gamma K γ in order of increasing modulus is algebraically simple and satisfies
min j ∣ 1 − μ i ν j ∣ = ∣ 1 − μ i ν i ∣ ≤ ∣ Im η ∣ Re η . (73) \min_j\left|1-\frac{\mu_i}{\nu_j}\right|=\left|1-\frac{\mu_i}{\nu_i}\right|\leq\frac{|\operatorname{Im}\eta|}{\operatorname{Re}\eta}. \tag*{(73)} j min 1 − ν j μ i = 1 − ν i μ i ≤ Re η ∣ Im η ∣ . (73)
Proof. We set E : = K γ − H γ = i ( Im η ) Q \mathcal{E}:=\mathcal{K}_\gamma-\mathcal{H}_\gamma=\mathrm{i}(\operatorname{Im}\eta)Q E := K γ − H γ = i ( Im η ) Q and consider the homotopy H γ + t E \mathcal{H}_\gamma+t\mathcal{E} H γ + t E , t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] . Since H γ − ( Re η ) Q = K P − Q ⪰ 0 \mathcal{H}_\gamma-(\operatorname{Re}\eta)Q=\mathcal{K}_P-Q\succeq0 H γ − ( Re η ) Q = K P − Q ⪰ 0 and Q ⪰ 0 Q\succeq0 Q ⪰ 0 , (71) gives, for each eigenvalue λ ∈ σ ( H γ + t E ) \lambda\in\sigma(\mathcal{H}_\gamma+t\mathcal{E}) λ ∈ σ ( H γ + t E ) ,
min j ∣ 1 − λ ν j ∣ ≤ t ∣ Im η ∣ ∥ H γ − 1 2 Q H γ − 1 2 ∥ 2 ≤ t ∣ Im η ∣ Re η . (74) \min_j\left|1-\frac{\lambda}{\nu_j}\right|\leq t|\operatorname{Im}\eta|\left\|\mathcal{H}_\gamma^{-\frac{1}{2}}Q\mathcal{H}_\gamma^{-\frac{1}{2}}\right\|_2\leq\frac{t|\operatorname{Im}\eta|}{\operatorname{Re}\eta}. \tag*{(74)} j min 1 − ν j λ ≤ t ∣ Im η ∣ H γ − 2 1 Q H γ − 2 1 2 ≤ Re η t ∣ Im η ∣ . (74)
Since the ν j \nu_j ν j are positive, 0 < Δ i < 1 0<\Delta_i<1 0 < Δ i < 1 . The gap condition (72) gives ∣ ν i − ν j ∣ ≥ Δ i ( ν i + ν j ) |\nu_i-\nu_j|\geq\Delta_i(\nu_i+\nu_j) ∣ ν i − ν j ∣ ≥ Δ i ( ν i + ν j ) for j ≠ i j\ne i j = i . This yields
( 1 + Δ i ) ν j ≤ ( 1 − Δ i ) ν i ( j < i ) , ( 1 − Δ i ) ν j ≥ ( 1 + Δ i ) ν i ( j > i ) . (75) (1+\Delta_i)\nu_j\leq(1-\Delta_i)\nu_i\ (j<i),\qquad(1-\Delta_i)\nu_j\geq(1+\Delta_i)\nu_i\ (j>i). \tag*{(75)} ( 1 + Δ i ) ν j ≤ ( 1 − Δ i ) ν i ( j < i ) , ( 1 − Δ i ) ν j ≥ ( 1 + Δ i ) ν i ( j > i ) . (75)
For ∣ λ ∣ ∈ [ ( 1 − Δ i ) ν i , ( 1 + Δ i ) ν i ] |\lambda|\in[(1-\Delta_i)\nu_i,(1+\Delta_i)\nu_i] ∣ λ ∣ ∈ [( 1 − Δ i ) ν i , ( 1 + Δ i ) ν i ] , (75) implies ∣ λ ∣ / ν j ≥ 1 + Δ i |\lambda|/\nu_j\geq1+\Delta_i ∣ λ ∣/ ν j ≥ 1 + Δ i for j < i j<i j < i and ∣ λ ∣ / ν j ≤ 1 − Δ i |\lambda|/\nu_j\leq1-\Delta_i ∣ λ ∣/ ν j ≤ 1 − Δ i for j > i j>i j > i . Hence
∣ 1 − λ ν j ∣ ≥ ∣ 1 − ∣ λ ∣ ν j ∣ ≥ Δ i , j ≠ i . (76) \left|1-\frac{\lambda}{\nu_j}\right|\geq\left|1-\frac{|\lambda|}{\nu_j}\right|\geq\Delta_i,\qquad j\ne i. \tag*{(76)} 1 − ν j λ ≥ 1 − ν j ∣ λ ∣ ≥ Δ i , j = i . (76)
On either boundary circle, the same lower bound holds for j = i j=i j = i . The strict inequality in (72) therefore excludes homotopy eigenvalues on either circle.
At t = 0 t=0 t = 0 , the open disks bounded by the inner and outer circles contain i − 1 i-1 i − 1 and i i i eigenvalues, respectively, counted with algebraic multiplicity. By continuity of the eigenvalues, the counts remain constant for all t t t . The annulus therefore contains one algebraically simple eigenvalue μ i ( t ) \mu_i(t) μ i ( t ) , which is the i i i -th eigenvalue in order of increasing modulus. In particular,
( 1 − Δ i ) ν i < ∣ μ i ( t ) ∣ < ( 1 + Δ i ) ν i , t ∈ [ 0 , 1 ] . (77) (1-\Delta_i)\nu_i<|\mu_i(t)|<(1+\Delta_i)\nu_i,\qquad t\in[0,1]. \tag*{(77)} ( 1 − Δ i ) ν i < ∣ μ i ( t ) ∣ < ( 1 + Δ i ) ν i , t ∈ [ 0 , 1 ] . (77)
By (76) , the minimizing index in (74) is i i i along this branch. At t = 1 t=1 t = 1 , this gives (73) . □ \square □
Since ∥ u i ∥ 2 = 1 \|u_i\|_2=1 ∥ u i ∥ 2 = 1 and v i † u i = 1 v_i^\dagger u_i=1 v i † u i = 1 , we have
∥ v i − u i ∥ 2 2 = ∥ v i ∥ 2 2 − 1 , (78) \|v_i-u_i\|_2^2=\|v_i\|_2^2-1, \tag*{(78)} ∥ v i − u i ∥ 2 2 = ∥ v i ∥ 2 2 − 1 , (78)
so we bound ∥ v i ∥ 2 \|v_i\|_2 ∥ v i ∥ 2 through the components along w i w_i w i .
Proposition 4.6. If ν i \nu_i ν i is simple and (72) holds, then
∣ w i † x ∣ 2 > 2 + 3 4 , x ∈ { u i , v i ∥ v i ∥ 2 } . (79) |w_i^\dagger x|^2>\frac{2+\sqrt{3}}{4},\qquad x\in\left\{u_i,\frac{v_i}{\|v_i\|_2}\right\}. \tag*{(79)} ∣ w i † x ∣ 2 > 4 2 + 3 , x ∈ { u i , ∥ v i ∥ 2 v i } . (79)
Proof. We consider the defect ( x † H γ x ) ( x † H γ − 1 x ) − 1 (x^\dagger\mathcal{H}_\gamma x)(x^\dagger\mathcal{H}_\gamma^{-1}x)-1 ( x † H γ x ) ( x † H γ − 1 x ) − 1 . For either unit eigenvector, x † K γ x = μ i x^\dagger\mathcal{K}_\gamma x=\mu_i x † K γ x = μ i . Its real part gives x † H γ x = Re μ i x^\dagger\mathcal{H}_\gamma x=\operatorname{Re}\mu_i x † H γ x = Re μ i . If Im η ≠ 0 \operatorname{Im}\eta\ne0 Im η = 0 , its imaginary part gives x † Q x = q i x^\dagger Qx=q_i x † Q x = q i . If Im η = 0 \operatorname{Im}\eta=0 Im η = 0 , the matrix is Hermitian and the normalized left and right eigenvectors coincide by simplicity, so the same identity holds. The relation K γ = H γ + i ( Im η ) Q \mathcal{K}_\gamma=\mathcal{H}_\gamma+\mathrm{i}(\operatorname{Im}\eta)Q K γ = H γ + i ( Im η ) Q gives
K γ † H γ − 1 K γ = K γ H γ − 1 K γ † = H γ + ∣ Im η ∣ 2 Q H γ − 1 Q . \mathcal{K}_\gamma^\dagger\mathcal{H}_\gamma^{-1}\mathcal{K}_\gamma=\mathcal{K}_\gamma\mathcal{H}_\gamma^{-1}\mathcal{K}_\gamma^\dagger=\mathcal{H}_\gamma+|\operatorname{Im}\eta|^2Q\mathcal{H}_\gamma^{-1}Q. K γ † H γ − 1 K γ = K γ H γ − 1 K γ † = H γ + ∣ Im η ∣ 2 Q H γ − 1 Q .
When x = u i \mathbf{x}=\mathbf{u}_i x = u i , K γ x = μ i x \mathcal{K}_\gamma\mathbf{x}=\mu_i\mathbf{x} K γ x = μ i x gives
∣ μ i ∣ 2 x † H γ − 1 x = ( K γ x ) † H γ − 1 ( K γ x ) = Re μ i + ∣ Im η ∣ 2 x † Q H γ − 1 Q x . |\mu_i|^2\mathbf{x}^{\dagger}\mathcal{H}_\gamma^{-1}\mathbf{x}=(\mathcal{K}_\gamma\mathbf{x})^{\dagger}\mathcal{H}_\gamma^{-1}(\mathcal{K}_\gamma\mathbf{x})=\operatorname{Re}\mu_i+|\operatorname{Im}\eta|^2\mathbf{x}^{\dagger}\mathcal{Q}\mathcal{H}_\gamma^{-1}\mathcal{Q}\mathbf{x}. ∣ μ i ∣ 2 x † H γ − 1 x = ( K γ x ) † H γ − 1 ( K γ x ) = Re μ i + ∣ Im η ∣ 2 x † Q H γ − 1 Q x .
For the left eigenvector, K γ † x = μ i ‾ x \mathcal{K}_\gamma^\dagger\mathbf{x}=\overline{\mu_i}\mathbf{x} K γ † x = μ i x gives the same equality. We substitute x † H γ x = Re μ i \mathbf{x}^{\dagger}\mathcal{H}_\gamma\mathbf{x}=\operatorname{Re}\mu_i x † H γ x = Re μ i and q i = x † Q x q_i=\mathbf{x}^{\dagger}\mathcal{Q}\mathbf{x} q i = x † Q x to obtain the q i q_i q i -dependent defect bound
( Re μ i ) x † H γ − 1 x − 1 = ∣ Im η ∣ 2 ∣ μ i ∣ 2 ( ( Re μ i ) x † Q H γ − 1 Q x − q i 2 ) ≤ ∣ Im η ∣ 2 q i ( Re μ i − ( Re η ) q i ) ( Re η ) ∣ μ i ∣ 2 ≤ ∣ Im η ∣ 2 ∣ Re μ i ∣ 2 4 ( Re η ) 2 ∣ μ i ∣ 2 . \begin{aligned}
(\operatorname{Re}\mu_i)\mathbf{x}^{\dagger}\mathcal{H}_\gamma^{-1}\mathbf{x}-1
&=\frac{|\operatorname{Im}\eta|^2}{|\mu_i|^2}\left((\operatorname{Re}\mu_i)\mathbf{x}^{\dagger}\mathcal{Q}\mathcal{H}_\gamma^{-1}\mathcal{Q}\mathbf{x}-q_i^2\right)\\
&\le\frac{|\operatorname{Im}\eta|^2q_i\left(\operatorname{Re}\mu_i-(\operatorname{Re}\eta)q_i\right)}{(\operatorname{Re}\eta)|\mu_i|^2}\\
&\le\frac{|\operatorname{Im}\eta|^2|\operatorname{Re}\mu_i|^2}{4(\operatorname{Re}\eta)^2|\mu_i|^2}.
\end{aligned} ( Re μ i ) x † H γ − 1 x − 1 = ∣ μ i ∣ 2 ∣ Im η ∣ 2 ( ( Re μ i ) x † Q H γ − 1 Q x − q i 2 ) ≤ ( Re η ) ∣ μ i ∣ 2 ∣ Im η ∣ 2 q i ( Re μ i − ( Re η ) q i ) ≤ 4 ( Re η ) 2 ∣ μ i ∣ 2 ∣ Im η ∣ 2 ∣ Re μ i ∣ 2 .
where the first inequality uses Q H γ − 1 Q ⪯ Q / ( Re η ) \mathcal{Q}\mathcal{H}_\gamma^{-1}\mathcal{Q}\preceq\mathcal{Q}/(\operatorname{Re}\eta) Q H γ − 1 Q ⪯ Q / ( Re η ) , which follows from H γ ⪰ ( Re η ) Q \mathcal{H}_\gamma\succeq(\operatorname{Re}\eta)\mathcal{Q} H γ ⪰ ( Re η ) Q . The second uses the arithmetic–geometric mean inequality q i ( Re μ i − ( Re η ) q i ) ≤ ( Re μ i ) 2 / ( 4 Re η ) q_i(\operatorname{Re}\mu_i-(\operatorname{Re}\eta)q_i)\le(\operatorname{Re}\mu_i)^2/(4\operatorname{Re}\eta) q i ( Re μ i − ( Re η ) q i ) ≤ ( Re μ i ) 2 / ( 4 Re η ) . The defect therefore also satisfies
( Re μ i ) x † H γ − 1 x − 1 ≤ ∣ Im η ∣ 2 4 ( Re η ) 2 < Δ i 2 4 . (80) (\operatorname{Re}\mu_i)\mathbf{x}^{\dagger}\mathcal{H}_\gamma^{-1}\mathbf{x}-1\le\frac{|\operatorname{Im}\eta|^2}{4(\operatorname{Re}\eta)^2}<\frac{\Delta_i^2}{4}. \tag*{(80)} ( Re μ i ) x † H γ − 1 x − 1 ≤ 4 ( Re η ) 2 ∣ Im η ∣ 2 < 4 Δ i 2 . (80)
We expand x \mathbf{x} x in the eigenbasis { w j } \{\mathbf{w}_j\} { w j } , pair ( j , k ) (j,k) ( j , k ) with ( k , j ) (k,j) ( k , j ) , and retain the terms involving i i i to obtain
( Re μ i ) x † H γ − 1 x − 1 = ∑ j , k ( ν j ν k − 1 ) ∣ w j † x ∣ 2 ∣ w k † x ∣ 2 = ∑ j < k ( ν j − ν k ) 2 ν j ν k ∣ w j † x ∣ 2 ∣ w k † x ∣ 2 ≥ ∣ w i † x ∣ 2 ∑ j ≠ i ( ν j − ν i ) 2 ν j ν i ∣ w j † x ∣ 2 . \begin{aligned}
(\operatorname{Re}\mu_i)\mathbf{x}^{\dagger}\mathcal{H}_\gamma^{-1}\mathbf{x}-1
&=\sum_{j,k}\left(\frac{\nu_j}{\nu_k}-1\right)|\mathbf{w}_j^{\dagger}\mathbf{x}|^2|\mathbf{w}_k^{\dagger}\mathbf{x}|^2\\
&=\sum_{j<k}\frac{(\nu_j-\nu_k)^2}{\nu_j\nu_k}|\mathbf{w}_j^{\dagger}\mathbf{x}|^2|\mathbf{w}_k^{\dagger}\mathbf{x}|^2\\
&\ge|\mathbf{w}_i^{\dagger}\mathbf{x}|^2\sum_{j\ne i}\frac{(\nu_j-\nu_i)^2}{\nu_j\nu_i}|\mathbf{w}_j^{\dagger}\mathbf{x}|^2.
\end{aligned} ( Re μ i ) x † H γ − 1 x − 1 = j , k ∑ ( ν k ν j − 1 ) ∣ w j † x ∣ 2 ∣ w k † x ∣ 2 = j < k ∑ ν j ν k ( ν j − ν k ) 2 ∣ w j † x ∣ 2 ∣ w k † x ∣ 2 ≥ ∣ w i † x ∣ 2 j = i ∑ ν j ν i ( ν j − ν i ) 2 ∣ w j † x ∣ 2 .
where the last step keeps only the terms j = i j=i j = i or k = i k=i k = i , all of which are nonnegative. For j ≠ i j\ne i j = i , the assumption (72) gives
( ν j − ν i ) 2 ν j ν i ≥ Δ i 2 ( ν j + ν i ) 2 ν j ν i ≥ 4 Δ i 2 . \frac{(\nu_j-\nu_i)^2}{\nu_j\nu_i}\ge\Delta_i^2\frac{(\nu_j+\nu_i)^2}{\nu_j\nu_i}\ge4\Delta_i^2. ν j ν i ( ν j − ν i ) 2 ≥ Δ i 2 ν j ν i ( ν j + ν i ) 2 ≥ 4 Δ i 2 .
This coefficient bound implies
( Re μ i ) x † H γ − 1 x − 1 ≥ 4 Δ i 2 ∣ w i † x ∣ 2 ( 1 − ∣ w i † x ∣ 2 ) . (81) (\operatorname{Re}\mu_i)\mathbf{x}^{\dagger}\mathcal{H}_\gamma^{-1}\mathbf{x}-1\ge4\Delta_i^2|\mathbf{w}_i^{\dagger}\mathbf{x}|^2\left(1-|\mathbf{w}_i^{\dagger}\mathbf{x}|^2\right). \tag*{(81)} ( Re μ i ) x † H γ − 1 x − 1 ≥ 4 Δ i 2 ∣ w i † x ∣ 2 ( 1 − ∣ w i † x ∣ 2 ) . (81)
Together, (80) and (81) give
∣ w i † x ∣ 2 ( 1 − ∣ w i † x ∣ 2 ) < 1 16 . (82) |\mathbf{w}_i^{\dagger}\mathbf{x}|^2\left(1-|\mathbf{w}_i^{\dagger}\mathbf{x}|^2\right)<\frac{1}{16}. \tag*{(82)} ∣ w i † x ∣ 2 ( 1 − ∣ w i † x ∣ 2 ) < 16 1 . (82)
The relative bound (73) and the strict gap condition (72) give
∣ Re μ i − ν i ∣ ≤ ∣ μ i − ν i ∣ ≤ ν i ∣ Im η ∣ Re η < Δ i ν i . |\operatorname{Re}\mu_i-\nu_i|\le|\mu_i-\nu_i|\le\frac{\nu_i|\operatorname{Im}\eta|}{\operatorname{Re}\eta}<\Delta_i\nu_i. ∣ Re μ i − ν i ∣ ≤ ∣ μ i − ν i ∣ ≤ Re η ν i ∣ Im η ∣ < Δ i ν i .
The real-part localization and its spectral expansion are
( 1 − Δ i ) ν i < Re μ i < ( 1 + Δ i ) ν i , Re μ i = ∑ j ν j ∣ w j † x ∣ 2 . (83) (1-\Delta_i)\nu_i<\operatorname{Re}\mu_i<(1+\Delta_i)\nu_i,\qquad\operatorname{Re}\mu_i=\sum_j\nu_j|\mathbf{w}_j^{\dagger}\mathbf{x}|^2. \tag*{(83)} ( 1 − Δ i ) ν i < Re μ i < ( 1 + Δ i ) ν i , Re μ i = j ∑ ν j ∣ w j † x ∣ 2 . (83)
The defect also admits the expansion
( Re μ i ) x † H γ − 1 x − 1 = ∑ j ( Re μ i ν j − 1 ) ∣ w j † x ∣ 2 = ∑ j ( Re μ i ν j + ν j Re μ i − 2 ) ∣ w j † x ∣ 2 = ∑ j ( Re μ i − ν j ) 2 ( Re μ i ) ν j ∣ w j † x ∣ 2 . \begin{aligned}
(\operatorname{Re}\mu_i)\mathbf{x}^{\dagger}\mathcal{H}_{\gamma}^{-1}\mathbf{x}-1=\sum_j\left(\frac{\operatorname{Re}\mu_i}{\nu_j}-1\right)|\mathbf{w}_j^{\dagger}\mathbf{x}|^2 \\
&=\sum_j\left(\frac{\operatorname{Re}\mu_i}{\nu_j}+\frac{\nu_j}{\operatorname{Re}\mu_i}-2\right)|\mathbf{w}_j^{\dagger}\mathbf{x}|^2 \\
&=\sum_j\frac{(\operatorname{Re}\mu_i-\nu_j)^2}{(\operatorname{Re}\mu_i)\nu_j}|\mathbf{w}_j^{\dagger}\mathbf{x}|^2.
\end{aligned} ( Re μ i ) x † H γ − 1 x − 1 = j ∑ ( ν j Re μ i − 1 ) ∣ w j † x ∣ 2 = j ∑ ( ν j Re μ i + Re μ i ν j − 2 ) ∣ w j † x ∣ 2 = j ∑ ( Re μ i ) ν j ( Re μ i − ν j ) 2 ∣ w j † x ∣ 2 .
The real-part localization (83) and the separation (75) imply that ( Re μ i ) / ν j > 1 + Δ i (\operatorname{Re}\mu_i)/\nu_j>1+\Delta_i ( Re μ i ) / ν j > 1 + Δ i for j < i j<i j < i and ( Re μ i ) / ν j < 1 − Δ i (\operatorname{Re}\mu_i)/\nu_j<1-\Delta_i ( Re μ i ) / ν j < 1 − Δ i for j > i j>i j > i . Thus ∣ 1 − Re μ i ν j ∣ ≥ Δ i \left|1-\frac{\operatorname{Re}\mu_i}{\nu_j}\right|\ge\Delta_i 1 − ν j Re μ i ≥ Δ i for j ≠ i j\ne i j = i . The corresponding coefficient satisfies
( ν j − Re μ i ) 2 ( Re μ i ) ν j ≥ ∣ 1 − Re μ i ν j ∣ 2 1 + ∣ 1 − Re μ i ν j ∣ ≥ Δ i 2 1 + Δ i . \frac{(\nu_j-\operatorname{Re}\mu_i)^2}{(\operatorname{Re}\mu_i)\nu_j}\ge\frac{\left|1-\frac{\operatorname{Re}\mu_i}{\nu_j}\right|^2}{1+\left|1-\frac{\operatorname{Re}\mu_i}{\nu_j}\right|}\ge\frac{\Delta_i^2}{1+\Delta_i}. ( Re μ i ) ν j ( ν j − Re μ i ) 2 ≥ 1 + 1 − ν j Re μ i 1 − ν j Re μ i 2 ≥ 1 + Δ i Δ i 2 .
The j = i j=i j = i term in the spectral sum is nonnegative, and the weights for j ≠ i j\ne i j = i sum to 1 − ∣ w i † x ∣ 2 1-|\mathbf{w}_i^{\dagger}\mathbf{x}|^2 1 − ∣ w i † x ∣ 2 . The resulting lower bound, together with (80) and (72) , gives
Δ i 2 1 + Δ i ( 1 − ∣ w i † x ∣ 2 ) ≤ ( Re μ i ) x † H γ − 1 x − 1 < Δ i 2 4 , ⇒ ∣ w i † x ∣ 2 > 3 − Δ i 4 . \frac{\Delta_i^2}{1+\Delta_i}\left(1-|\mathbf{w}_i^{\dagger}\mathbf{x}|^2\right)\le(\operatorname{Re}\mu_i)\mathbf{x}^{\dagger}\mathcal{H}_{\gamma}^{-1}\mathbf{x}-1<\frac{\Delta_i^2}{4},\quad\Rightarrow\quad|\mathbf{w}_i^{\dagger}\mathbf{x}|^2>\frac{3-\Delta_i}{4}. 1 + Δ i Δ i 2 ( 1 − ∣ w i † x ∣ 2 ) ≤ ( Re μ i ) x † H γ − 1 x − 1 < 4 Δ i 2 , ⇒ ∣ w i † x ∣ 2 > 4 3 − Δ i .
Since Δ i < 1 \Delta_i<1 Δ i < 1 , the last inequality gives ∣ w i † x ∣ 2 > 1 / 2 |\mathbf{w}_i^{\dagger}\mathbf{x}|^2>1/2 ∣ w i † x ∣ 2 > 1/2 . Combining this bound with (82) proves (79) .
Proposition 4.7. If ν i \nu_i ν i is simple and (72) holds, the normalized left eigenvector satisfies
1 ∥ v i ∥ 2 2 ≥ 1 − ∣ Im η 2 Δ i Re η ∣ 2 . (84) \frac{1}{\|\mathbf{v}_i\|_2^2}\ge1-\left|\frac{\operatorname{Im}\eta}{2\Delta_i\operatorname{Re}\eta}\right|^2. \tag*{(84)} ∥ v i ∥ 2 2 1 ≥ 1 − 2 Δ i Re η Im η 2 . (84) For any x , y ∈ { u i , v i / ∥ v i ∥ 2 } \mathbf{x},\mathbf{y}\in\{\mathbf{u}_i,\mathbf{v}_i/\|\mathbf{v}_i\|_2\} x , y ∈ { u i , v i /∥ v i ∥ 2 } , the bilinear estimate is
∣ x † ( H γ − ν i I ) y ∣ ≤ ∣ Im η ∣ 2 q i 2 ( Re η ) ∥ v i ∥ 2 ( 1 + 1 Δ i ) . (85) |\mathbf{x}^{\dagger}(\mathcal{H}_{\gamma}-\nu_i I)\mathbf{y}|\le\frac{|\operatorname{Im}\eta|^2q_i}{2(\operatorname{Re}\eta)\|\mathbf{v}_i\|_2}\left(1+\frac{1}{\Delta_i}\right). \tag*{(85)} ∣ x † ( H γ − ν i I ) y ∣ ≤ 2 ( Re η ) ∥ v i ∥ 2 ∣ Im η ∣ 2 q i ( 1 + Δ i 1 ) . (85)
Proof. We set p : = min { ∣ w i † u i ∣ 2 , ∣ w i † v i ∣ 2 / ∥ v i ∥ 2 2 } p:=\min\{|\mathbf{w}_i^{\dagger}\mathbf{u}_i|^2,|\mathbf{w}_i^{\dagger}\mathbf{v}_i|^2/\|\mathbf{v}_i\|_2^2\} p := min { ∣ w i † u i ∣ 2 , ∣ w i † v i ∣ 2 /∥ v i ∥ 2 2 } . By (79) , we have p > 1 / 2 p>1/2 p > 1/2 . In the inner product of the two unit eigenvectors, the term from w i \mathbf{w}_i w i has modulus at least p p p . The sum of the other terms has modulus at most 1 − p 1-p 1 − p by Cauchy–Schwarz. Since v i † u i = 1 \mathbf{v}_i^{\dagger}\mathbf{u}_i=1 v i † u i = 1 , the reverse triangle inequality gives
1 ∥ v i ∥ 2 ≥ p − ( 1 − p ) = 2 p − 1. \frac{1}{\|\mathbf{v}_i\|_2}\ge p-(1-p)=2p-1. ∥ v i ∥ 2 1 ≥ p − ( 1 − p ) = 2 p − 1.
For the unit eigenvector attaining p p p , the bounds (80) and (81) give
4 p ( 1 − p ) ≤ ∣ Im η 2 Δ i Re η ∣ 2 . 4p(1-p)\le\left|\frac{\operatorname{Im}\eta}{2\Delta_i\operatorname{Re}\eta}\right|^2. 4 p ( 1 − p ) ≤ 2 Δ i Re η Im η 2 .
Thus the normalization bound (84) follows from
1 ∥ v i ∥ 2 2 ≥ ( 2 p − 1 ) 2 = 1 − 4 p ( 1 − p ) . \frac{1}{\|\mathbf{v}_i\|_2^2}\ge(2p-1)^2=1-4p(1-p). ∥ v i ∥ 2 2 1 ≥ ( 2 p − 1 ) 2 = 1 − 4 p ( 1 − p ) .
The weighted spectral estimate uses the first inequality in the defect estimate preceding (80) . For either unit eigenvector x \mathbf{x} x , this inequality and ∣ μ i ∣ 2 ≥ ( Re μ i ) 2 |\mu_i|^2 \ge(\operatorname{Re}\mu_i)^2 ∣ μ i ∣ 2 ≥ ( Re μ i ) 2 give
( Re μ i ) x † H γ − 1 x − 1 ≤ ∣ Im η ∣ 2 q i ( Re η ) ( Re μ i ) ( 1 − ( Re η ) q i Re μ i ) . (86) (\operatorname{Re}\mu_i)\mathbf{x}^{\dagger}\mathcal{H}_{\gamma}^{-1}\mathbf{x}-1 \le\frac{|\operatorname{Im}\eta|^2q_i}{(\operatorname{Re}\eta)(\operatorname{Re}\mu_i)}\left(1-\frac{(\operatorname{Re}\eta)q_i}{\operatorname{Re}\mu_i}\right). \tag*{(86)} ( Re μ i ) x † H γ − 1 x − 1 ≤ ( Re η ) ( Re μ i ) ∣ Im η ∣ 2 q i ( 1 − Re μ i ( Re η ) q i ) . (86)
By (72) and (67) , the ratio ∣ Im η ∣ / ( Δ i Re η ) |\operatorname{Im}\eta|/(\Delta_i\operatorname{Re}\eta) ∣ Im η ∣/ ( Δ i Re η ) and the factor 1 − ( Re η ) q i / Re μ i 1-(\operatorname{Re}\eta)q_i/\operatorname{Re}\mu_i 1 − ( Re η ) q i / Re μ i are at most one. Hence (86) and (81) , applied to the unit eigenvector attaining p p p , give 4 p ( 1 − p ) ≤ ( Re η ) q i / Re μ i 4p(1-p)\le(\operatorname{Re}\eta)q_i/\operatorname{Re}\mu_i 4 p ( 1 − p ) ≤ ( Re η ) q i / Re μ i . Since 2 p − 1 ≤ p 2 2p-1\le p^2 2 p − 1 ≤ p 2 and 2 p − 1 ≤ 1 / ∥ v i ∥ 2 2p-1\le1/\|\mathbf{v}_i\|_2 2 p − 1 ≤ 1/∥ v i ∥ 2 , we obtain
1 − ( Re η ) q i Re μ i ≤ ( 2 p − 1 ) 2 ≤ p 2 ∥ v i ∥ 2 2 . (87) 1-\frac{(\operatorname{Re}\eta)q_i}{\operatorname{Re}\mu_i}\le(2p-1)^2\le\frac{p^2}{\|\mathbf{v}_i\|_2^2}. \tag*{(87)} 1 − Re μ i ( Re η ) q i ≤ ( 2 p − 1 ) 2 ≤ ∥ v i ∥ 2 2 p 2 . (87)
For j ≠ i j\ne i j = i , the gap condition (72) gives ν i + ν j ≤ ∣ ν j − ν i ∣ / Δ i \nu_i+\nu_j\le|\nu_j-\nu_i|/\Delta_i ν i + ν j ≤ ∣ ν j − ν i ∣/ Δ i . Since 2 ν j ≤ ν i + ν j + ∣ ν j − ν i ∣ 2\nu_j\le\nu_i+\nu_j+|\nu_j-\nu_i| 2 ν j ≤ ν i + ν j + ∣ ν j − ν i ∣ , we have
∣ ν j − ν i ∣ ≤ 1 2 ( 1 + 1 Δ i ) ( ν j − ν i ) 2 ν j . |\nu_j-\nu_i|\le\frac{1}{2}\left(1+\frac{1}{\Delta_i}\right)\frac{(\nu_j-\nu_i)^2}{\nu_j}. ∣ ν j − ν i ∣ ≤ 2 1 ( 1 + Δ i 1 ) ν j ( ν j − ν i ) 2 .
The last inequality in the spectral expansion preceding (81) bounds the sum with weights ( ν j − ν i ) 2 / ν j (\nu_j-\nu_i)^2/\nu_j ( ν j − ν i ) 2 / ν j . This bound, the weight comparison above, and ν i ∣ w i ∗ ∣ 2 ≤ Re μ i \nu_i|\mathbf{w}_i^\ast|^2\le\operatorname{Re}\mu_i ν i ∣ w i ∗ ∣ 2 ≤ Re μ i give
∑ j ≠ i ∣ ν j − ν i ∣ ∣ w j ∗ x ∣ 2 ≤ 1 2 ( 1 + 1 Δ i ) ν i ∣ w i ∗ x ∣ 2 ( ( Re μ i ) x † H γ − 1 x − 1 ) ≤ 1 2 ( 1 + 1 Δ i ) Re μ i p 2 ( ( Re μ i ) x † H γ − 1 x − 1 ) ≤ ∣ Im η ∣ 2 q i 2 ( Re η ) ∥ v i ∥ 2 ( 1 + 1 Δ i ) . (88) \begin{aligned}
\sum_{j\ne i}|\nu_j-\nu_i||\mathbf{w}_j^\ast\mathbf{x}|^2
&\le\frac{1}{2}\left(1+\frac{1}{\Delta_i}\right)\frac{\nu_i}{|\mathbf{w}_i^\ast\mathbf{x}|^2}\left((\operatorname{Re}\mu_i)\mathbf{x}^\dagger\mathcal{H}_\gamma^{-1}\mathbf{x}-1\right)\\
&\le\frac{1}{2}\left(1+\frac{1}{\Delta_i}\right)\frac{\operatorname{Re}\mu_i}{p^2}\left((\operatorname{Re}\mu_i)\mathbf{x}^\dagger\mathcal{H}_\gamma^{-1}\mathbf{x}-1\right)\\
&\le\frac{|\operatorname{Im}\eta|^2q_i}{2(\operatorname{Re}\eta)\|\mathbf{v}_i\|_2}\left(1+\frac{1}{\Delta_i}\right). \tag*{(88)}
\end{aligned} j = i ∑ ∣ ν j − ν i ∣∣ w j ∗ x ∣ 2 ≤ 2 1 ( 1 + Δ i 1 ) ∣ w i ∗ x ∣ 2 ν i ( ( Re μ i ) x † H γ − 1 x − 1 ) ≤ 2 1 ( 1 + Δ i 1 ) p 2 Re μ i ( ( Re μ i ) x † H γ − 1 x − 1 ) ≤ 2 ( Re η ) ∥ v i ∥ 2 ∣ Im η ∣ 2 q i ( 1 + Δ i 1 ) . (88)
The last step uses (86) and (87) . In the eigenbasis of H γ \mathcal{H}_\gamma H γ , Cauchy–Schwarz with weights ∣ ν j − ν i ∣ |\nu_j-\nu_i| ∣ ν j − ν i ∣ bounds the modulus of the bilinear form by the geometric mean of the sums in (88) for x \mathbf{x} x and y \mathbf{y} y . This gives (85) .
Proposition 4.8. Under the hypotheses of Proposition 4.7, the material term in (69) satisfies
∣ ( v i − u i ) † Q u i ∣ ≤ ∣ Im η ∣ q i 2 Re η ( 1 + 1 Δ i ) ( 1 + 1 ∥ v i ∥ 2 ) . (89) \left|( \mathbf{v}_i-\mathbf{u}_i)^\dagger Q\mathbf{u}_i\right|\le\frac{|\operatorname{Im}\eta|q_i}{2\operatorname{Re}\eta}\left(1+\frac{1}{\Delta_i}\right)\left(1+\frac{1}{\|\mathbf{v}_i\|_2}\right). \tag*{(89)} ( v i − u i ) † Q u i ≤ 2 Re η ∣ Im η ∣ q i ( 1 + Δ i 1 ) ( 1 + ∥ v i ∥ 2 1 ) . (89)
Proof. If Im η = 0 \operatorname{Im}\eta=0 Im η = 0 , simplicity and normalization give v i = u i \mathbf{v}_i=\mathbf{u}_i v i = u i . Otherwise, the right eigenvalue equation and ( v i − u i ) † u i = 0 (\mathbf{v}_i-\mathbf{u}_i)^\dagger\mathbf{u}_i=0 ( v i − u i ) † u i = 0 give ( v i − u i ) † ( K γ − ν i I ) u i = 0 (\mathbf{v}_i-\mathbf{u}_i)^\dagger(\mathcal{K}_\gamma-\nu_iI)\mathbf{u}_i=0 ( v i − u i ) † ( K γ − ν i I ) u i = 0 . The splitting K γ = H γ + i ( Im η ) Q \mathcal{K}_\gamma=\mathcal{H}_\gamma+i(\operatorname{Im}\eta)Q K γ = H γ + i ( Im η ) Q then gives the equality below. The triangle inequality and (85) with y = u i \mathbf{y}=\mathbf{u}_i y = u i and x = v i / ∥ v i ∥ 2 \mathbf{x}=\mathbf{v}_i/\|\mathbf{v}_i\|_2 x = v i /∥ v i ∥ 2 or u i \mathbf{u}_i u i give the bound.
∣ Im η ∣ ∣ ( v i − u i ) † Q u i ∣ = ∣ ( v i − u i ) † ( H γ − ν i I ) u i ∣ ≤ ( ∥ v i ∥ 2 + 1 ) ∣ Im η ∣ 2 q i 2 ( Re η ) ∥ v i ∥ 2 ( 1 + 1 Δ i ) . \begin{aligned}
|\operatorname{Im}\eta|\left|(\mathbf{v}_i-\mathbf{u}_i)^\dagger Q\mathbf{u}_i\right|=\left|(\mathbf{v}_i-\mathbf{u}_i)^\dagger(\mathcal{H}_\gamma-\nu_iI)\mathbf{u}_i\right| \\
&\le(\|\mathbf{v}_i\|_2+1)\frac{|\operatorname{Im}\eta|^2q_i}{2(\operatorname{Re}\eta)\|\mathbf{v}_i\|_2}\left(1+\frac{1}{\Delta_i}\right).
\end{aligned} ∣ Im η ∣ ( v i − u i ) † Q u i = ( v i − u i ) † ( H γ − ν i I ) u i ≤ ( ∥ v i ∥ 2 + 1 ) 2 ( Re η ) ∥ v i ∥ 2 ∣ Im η ∣ 2 q i ( 1 + Δ i 1 ) .
The estimate (89) follows upon division by ∣ Im η ∣ |\operatorname{Im}\eta| ∣ Im η ∣ .
μ i ′ = q i η ′ \mu'_i=q_i\eta' μ i ′ = q i η ′ , so (4.10) is the exact Newton update and ρ i = 0 \rho_i=0 ρ i = 0 . Here the left–right derivative defect produces a linear error factor. For Re ω > 0 \operatorname{Re}\omega>0 Re ω > 0 and Re η ′ < 0 \operatorname{Re}\eta'<0 Re η ′ < 0 , (4.21), (4.15), and (4.45) give
∣ ρ i ∣ ≤ ∣ Im η ∣ ∣ η ′ ∣ q i 2 Re η ( 2 Re ω − ( Re η ′ ) q i ) ( 1 + 1 Δ i ) ( 1 + 1 ∥ v i ∥ 2 ) . (91) |\rho_i|\leq\frac{|\operatorname{Im}\eta|\,|\eta'|q_i}{2\operatorname{Re}\eta\left(2\operatorname{Re}\omega-(\operatorname{Re}\eta')q_i\right)}\left(1+\frac{1}{\Delta_i}\right)\left(1+\frac{1}{\lVert v_i\rVert_2}\right). \tag*{(91)} ∣ ρ i ∣ ≤ 2 Re η ( 2 Re ω − ( Re η ′ ) q i ) ∣ Im η ∣ ∣ η ′ ∣ q i ( 1 + Δ i 1 ) ( 1 + ∥ v i ∥ 2 1 ) . (91)
For exact inner eigenpairs, a value of the right-hand side below one at a simple root guarantees local contraction of the update (4.10) by (4.17).
Numerical Experiments
Parameters and Test Examples
We consider the simple cubic (SC), face centered cubic (FCC), and body centered cubic (BCC) lattices as in [17 ] . We use dimensionless coordinates and frequencies, with the conventional cubic lattice constant and the background wave speed normalized to one. The primitive lattice vectors are defined by
SC lattice: a 1 = ( 1 , 0 , 0 ) T , a 2 = ( 0 , 1 , 0 ) T , a 3 = ( 0 , 0 , 1 ) T , FCC lattice: a 1 = ( 0 , 1 2 , 1 2 ) T , a 2 = ( 1 2 , 0 , 1 2 ) T , a 3 = ( 1 2 , 1 2 , 0 ) T , BCC lattice: a 1 = ( − 1 2 , 1 2 , 1 2 ) T , a 2 = ( 1 2 , − 1 2 , 1 2 ) T , a 3 = ( 1 2 , 1 2 , − 1 2 ) T . (92) \begin{aligned}
\text{SC lattice:}\quad&\mathbf{a}_1=(1,0,0)^{\mathsf{T}},\quad\mathbf{a}_2=(0,1,0)^{\mathsf{T}},\quad\mathbf{a}_3=(0,0,1)^{\mathsf{T}},\\
\text{FCC lattice:}\quad&\mathbf{a}_1=\left(0,\frac{1}{2},\frac{1}{2}\right)^{\mathsf{T}},\quad\mathbf{a}_2=\left(\frac{1}{2},0,\frac{1}{2}\right)^{\mathsf{T}},\quad\mathbf{a}_3=\left(\frac{1}{2},\frac{1}{2},0\right)^{\mathsf{T}},\\
\text{BCC lattice:}\quad&\mathbf{a}_1=\left(-\frac{1}{2},\frac{1}{2},\frac{1}{2}\right)^{\mathsf{T}},\quad\mathbf{a}_2=\left(\frac{1}{2},-\frac{1}{2},\frac{1}{2}\right)^{\mathsf{T}},\quad\mathbf{a}_3=\left(\frac{1}{2},\frac{1}{2},-\frac{1}{2}\right)^{\mathsf{T}}. \tag*{(92)}
\end{aligned} SC lattice: FCC lattice: BCC lattice: a 1 = ( 1 , 0 , 0 ) T , a 2 = ( 0 , 1 , 0 ) T , a 3 = ( 0 , 0 , 1 ) T , a 1 = ( 0 , 2 1 , 2 1 ) T , a 2 = ( 2 1 , 0 , 2 1 ) T , a 3 = ( 2 1 , 2 1 , 0 ) T , a 1 = ( − 2 1 , 2 1 , 2 1 ) T , a 2 = ( 2 1 , − 2 1 , 2 1 ) T , a 3 = ( 2 1 , 2 1 , − 2 1 ) T . (92)
Their high-symmetry points are
SC lattice: K ( 0 , 0 , 0 ) , L ( π , 0 , 0 ) , M ( π , π , 0 ) , N ( π , π , π ) , FCC lattice: X ( 0 , 2 π , 0 ) , U ( π 2 , 2 π , π 2 ) , L ( π , π , π ) , Γ ( 0 , 0 , 0 ) , W ( π , 2 π , 0 ) , K ( 3 π 2 , 3 π 2 , 0 ) , BCC lattice: H ( 0 , 0 , 2 π ) , Γ ( 0 , 0 , 0 ) , P ( π , π , π ) , N ( π , 0 , π ) . (93) \begin{aligned}
\text{SC lattice:}\quad&K(0,0,0),\quad L(\pi,0,0),\quad M(\pi,\pi,0),\quad N(\pi,\pi,\pi),\\
\text{FCC lattice:}\quad&X(0,2\pi,0),\quad U\left(\frac{\pi}{2},2\pi,\frac{\pi}{2}\right),\quad L(\pi,\pi,\pi),\\
&\Gamma(0,0,0),\quad W(\pi,2\pi,0),\quad K\left(\frac{3\pi}{2},\frac{3\pi}{2},0\right),\\
\text{BCC lattice:}\quad&H(0,0,2\pi),\quad\Gamma(0,0,0),\quad P(\pi,\pi,\pi),\quad N(\pi,0,\pi). \tag*{(93)}
\end{aligned} SC lattice: FCC lattice: BCC lattice: K ( 0 , 0 , 0 ) , L ( π , 0 , 0 ) , M ( π , π , 0 ) , N ( π , π , π ) , X ( 0 , 2 π , 0 ) , U ( 2 π , 2 π , 2 π ) , L ( π , π , π ) , Γ ( 0 , 0 , 0 ) , W ( π , 2 π , 0 ) , K ( 2 3 π , 2 3 π , 0 ) , H ( 0 , 0 , 2 π ) , Γ ( 0 , 0 , 0 ) , P ( π , π , π ) , N ( π , 0 , π ) . (93)
The wave number vector follows K ⟶ L ⟶ M ⟶ N ⟶ K K\longrightarrow L\longrightarrow M\longrightarrow N\longrightarrow K K ⟶ L ⟶ M ⟶ N ⟶ K for the SC lattice and X ⟶ U ⟶ L ⟶ Γ ⟶ X ⟶ W ⟶ K X\longrightarrow U\longrightarrow L\longrightarrow\Gamma\longrightarrow X\longrightarrow W\longrightarrow K X ⟶ U ⟶ L ⟶ Γ ⟶ X ⟶ W ⟶ K for the FCC lattice. The BCC path is H ⟶ Γ ⟶ P ⟶ H ⟶ N ⟶ Γ ⟶ H ⟶ P ⟶ N H\longrightarrow\Gamma\longrightarrow P\longrightarrow H\longrightarrow N\longrightarrow\Gamma\longrightarrow H\longrightarrow P\longrightarrow N H ⟶ Γ ⟶ P ⟶ H ⟶ N ⟶ Γ ⟶ H ⟶ P ⟶ N . The first two occurrences of H H H denote ( 0 , 0 , 2 π ) (0,0,2\pi) ( 0 , 0 , 2 π ) , and the last denotes the symmetry-equivalent point ( 0 , 2 π , 0 ) (0,2\pi,0) ( 0 , 2 π , 0 ) . Each path segment contains 20 equally spaced samples, including its first endpoint and excluding its last endpoint. Therefore, one complete band calculation contains 80 wave number vectors for the SC lattice, 120 for the FCC lattice, and 160 for the BCC lattice.
We consider five material regions. The region SC_CURV consists of a central sphere of radius 0.345 and three cylinders of radius 0.11 [17 ] :
Ω S C _ C U R V = { ( x − 1 2 ) 2 + ( y − 1 2 ) 2 + ( z − 1 2 ) 2 ≤ 0.345 2 } ∪ { ( x − 1 2 ) 2 + ( y − 1 2 ) 2 ≤ 0.11 2 } ∪ { ( y − 1 2 ) 2 + ( z − 1 2 ) 2 ≤ 0.11 2 } ∪ { ( z − 1 2 ) 2 + ( x − 1 2 ) 2 ≤ 0.11 2 } . (94) \begin{aligned}
\Omega_{\mathrm{SC\_CURV}}={}&\left\{(x-\frac{1}{2})^2+(y-\frac{1}{2})^2+(z-\frac{1}{2})^2\leq0.345^2\right\}\\
&\cup\left\{(x-\frac{1}{2})^2+(y-\frac{1}{2})^2\leq0.11^2\right\}\cup\left\{(y-\frac{1}{2})^2+(z-\frac{1}{2})^2\leq0.11^2\right\}\\
&\cup\left\{(z-\frac{1}{2})^2+(x-\frac{1}{2})^2\leq0.11^2\right\}. \tag*{(94)}
\end{aligned} Ω SC_CURV = { ( x − 2 1 ) 2 + ( y − 2 1 ) 2 + ( z − 2 1 ) 2 ≤ 0.34 5 2 } ∪ { ( x − 2 1 ) 2 + ( y − 2 1 ) 2 ≤ 0.1 1 2 } ∪ { ( y − 2 1 ) 2 + ( z − 2 1 ) 2 ≤ 0.1 1 2 } ∪ { ( z − 2 1 ) 2 + ( x − 2 1 ) 2 ≤ 0.1 1 2 } . (94)
The region SC_FLAT is the following union of four cuboids:
Ω S C _ F L A T = [ 0 , 1 4 ] × [ 0 , 1 4 ] × [ 0 , 1 ] ∪ [ 0 , 1 4 ] × [ 0 , 1 ] × [ 1 4 , 1 2 ] ∪ [ 0 , 1 ] × [ 1 2 , 3 4 ] × [ 1 2 , 3 4 ] ∪ [ 1 2 , 3 4 ] × [ 0 , 1 ] × [ 3 4 , 1 ] . (95) \begin{aligned}
\Omega_{\mathrm{SC\_FLAT}}={}&[0,\frac{1}{4}]\times[0,\frac{1}{4}]\times[0,1]\ \cup\ [0,\frac{1}{4}]\times[0,1]\times[\frac{1}{4},\frac{1}{2}]\\
&\cup\ [0,1]\times[\frac{1}{2},\frac{3}{4}]\times[\frac{1}{2},\frac{3}{4}]\ \cup\ [\frac{1}{2},\frac{3}{4}]\times[0,1]\times[\frac{3}{4},1]. \tag*{(95)}
\end{aligned} Ω SC_FLAT = [ 0 , 4 1 ] × [ 0 , 4 1 ] × [ 0 , 1 ] ∪ [ 0 , 4 1 ] × [ 0 , 1 ] × [ 4 1 , 2 1 ] ∪ [ 0 , 1 ] × [ 2 1 , 4 3 ] × [ 2 1 , 4 3 ] ∪ [ 2 1 , 4 3 ] × [ 0 , 1 ] × [ 4 3 , 1 ] . (95)
The region FCC adopts the diamond-type configuration used in [10 , 17 ] . It consists of spheres of radius 0.12 and connecting spheroids with semi-minor axis 0.11. The foci of each spheroid are located at the centers of two neighboring spheres. The sphere centers are the FCC lattice sites and their translates by ( 1 4 , 1 4 , 1 4 ) T \left(\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)^{\mathsf{T}} ( 4 1 , 4 1 , 4 1 ) T , with periodic copies included.
The BCC-SG and BCC-DG regions use the single and double gyroid geometries in [17 , 18 ] . The double gyroid region is defined by
Ω B C C − D G = { ( x , y , z ) : ∣ sin ( 2 π x ) cos ( 2 π y ) + sin ( 2 π y ) cos ( 2 π z ) + sin ( 2 π z ) cos ( 2 π x ) ∣ > 1.1 } . (96) \Omega_{\mathrm{BCC-DG}}=\left\{(x,y,z):\left|\sin(2\pi x)\cos(2\pi y)+\sin(2\pi y)\cos(2\pi z)+\sin(2\pi z)\cos(2\pi x)\right|>1.1\right\}. \tag*{(96)} Ω BCC − DG = { ( x , y , z ) : ∣ sin ( 2 π x ) cos ( 2 π y ) + sin ( 2 π y ) cos ( 2 π z ) + sin ( 2 π z ) cos ( 2 π x ) ∣ > 1.1 } . (96)
The single gyroid BCC-SG retains the positive network, where the trigonometric sum in (96) is greater than 1.1. The FCC, BCC-SG, and BCC-DG examples use POL.
The implementation applies the inverse dielectric coefficient η ( ω ) = ε − 1 ( ω ) \eta(\omega)=\varepsilon^{-1}(\omega) η ( ω ) = ε − 1 ( ω ) . The SCAL and SiC models use the scalar Lorentz law [5 ] and the ionic Lorentz law for silicon carbide [4 ] , respectively. The POL and MIX models are artificial rational test functions. The POL form is motivated by the lossless GaAs phonon-polariton law [21 ] ; its complex quadratic coefficient is artificial. Table 2 lists the functions and parameters. The material parameters γ d \gamma_{\mathrm{d}} γ d and Γ \Gamma Γ in this table are independent of the kernel-compensation coefficient γ \gamma γ .
Table 2. The dielectric functions with normalized parameters used in our numerical examples.
The SiC parameters in Table 2 are rounded. The computations use ω 0 = 2 π ( 0.817 ) \omega_{0}=2\pi(0.817) ω 0 = 2 π ( 0.817 ) , ω p = 2 π 0.998 2 − 0.817 2 \omega_{\mathrm{p}}=2\pi\sqrt{0.998^{2}-0.817^{2}} ω p = 2 π 0.99 8 2 − 0.81 7 2 , and Γ = 2 π ( 0.004904 ) \Gamma=2\pi(0.004904) Γ = 2 π ( 0.004904 ) . The Lorentz damping terms follow the exp ( + i ω t ) \exp(+\mathrm{i}\omega t) exp ( + i ω t ) convention. Since ∣ exp ( + i ω t ) ∣ = exp ( − Im ω t ) |\exp(+\mathrm{i}\omega t)|=\exp(-\operatorname{Im}\omega\,t) ∣ exp ( + i ω t ) ∣ = exp ( − Im ω t ) , frequencies with positive imaginary part correspond to temporal decay. The negative imaginary parts in the POL results reflect its artificial material law.
The band and tolerance experiments use N = 120 N=120 N = 120 and compute the first n e v = 10 \mathrm{nev}=10 nev = 10 eigenpairs at each wave number vector. The Generalized Davidson method limits the search dimension to four times the retained block size and allows at most 2000 inner iterations, except for the SC_CURV/SCAL band run and the tolerance experiments, which allow 500. The quasi-Newton iteration allows at most 1000 outer iterations. The complete bands use outer and inner residual tolerances of 10 − 5 10^{-5} 1 0 − 5 and 9 × 10 − 6 9\times10^{-6} 9 × 1 0 − 6 , respectively. In the tolerance experiments, the inner tolerance is 0.9 times the outer tolerance.
Each run starts with a random block. At each subsequent Bloch wave vector, the solver reuses the previously computed vectors and fills the remaining columns with random vectors. The SiC and SC_CURV/MIX band calculations start with 13 vectors. The other band calculations start with four vectors and enlarge the block to 13 as additional frequencies are computed. The first frequency is initialized at ω ρ 1 ( 0 ) ( 0 ) = 0 \omega_{\rho_{1}^{(0)}}^{(0)}=0 ω ρ 1 ( 0 ) ( 0 ) = 0 , so its first update is a fixed-point step. The implementations used for the convergence histories and ρ λ i \rho_{\lambda}^{i} ρ λ i diagnostics additionally halve an inadmissible fallback step toward the preceding frequency, up to 32 times, and retain the preceding frequency if it is admissible and these trials fail.
The band and tolerance runtimes are obtained with the C++ CUDA implementation in complex double precision, using CUDA 12.4, cuBLAS, and cuFFT on one NVIDIA GeForce RTX 4090D GPU with 24 GiB of device memory. The timing experiments do not perform the optional adjoint-eigenvector postprocessing.
Figures of Complete Band
The upper and lower panels show ∣ Re ω ∣ 2 π \frac{|\operatorname{Re}\omega|}{2\pi} 2 π ∣ Re ω ∣ and Im ω 2 π \frac{\operatorname{Im}\omega}{2\pi} 2 π Im ω , respectively. Unconnected markers are used because no mode matching is applied between adjacent wave number vectors.
A sampled bandgap is determined from the absolute real parts of the computed frequencies along each path. Its ratio is defined by
bandgap ratio = 2 ω u p − ω l o w ω u p + ω l o w . (97) \text{bandgap ratio} = 2\frac{\omega_{\mathrm{up}}-\omega_{\mathrm{low}}}{\omega_{\mathrm{up}}+\omega_{\mathrm{low}}}. \tag*{(97)} bandgap ratio = 2 ω up + ω low ω up − ω low . (97)
Here, ω l o w \omega_{\mathrm{low}} ω low is the largest frequency below the gap, and ω u p \omega_{\mathrm{up}} ω up is the smallest frequency above the gap. Shading marks gaps along the sampled paths; it does not establish spectral exclusion throughout the Brillouin zone. The detection criterion uses the 95th percentile of changes between adjacent wave number samples, after sorting the absolute real parts at each sample, as an estimate of the sampling resolution. We retain intervals whose lower edge is at least one quarter of the largest displayed frequency, whose width exceeds 1.5 times this resolution, and whose ratio is at least 0.05. The widest retained interval is reported.
Figures 1 and 2 compare the SC examples. For the fixed SC_CURV geometry, SCAL has no detected sampled gap, while POL and SiC give ratios of 0.218 and 0.096, respectively. For POL, changing the material region from SC_CURV to SC_FLAT reduces the ratio to 0.109. These comparisons show the dependence of the sampled gaps on both the material law and the material geometry.
Figure 1. (a) The SC_CURV/SCAL example has no detected sampled bandgap. (b) The SC_FLAT/POL example has bandgap ratio 0.109. Complete complex bands for the two SC examples.
Figure 2. (a) The POL example has sampled bandgap ratio 0.218. (b) The SiC example has sampled bandgap ratio 0.096. Complete complex bands for the SC_CURV/POL and SC_CURV/SiC examples.
Figure 3 shows a sampled gap ratio of 0.168 for SC_CURV/MIX and 0.418 for FCC/POL. The latter is the largest ratio among the ten examples.
Figure 3. The bands for the SC_CURV/MIX and FCC/POL examples are shown.
Figure 4 shows no detected sampled gap for either SiC or MIX on SC_FLAT. Both laws give gaps on SC_CURV, so a change of geometry alone changes whether a gap is detected along the corresponding sampled path.
Figure 4. Complete complex bands for the SC_FLAT/SiC and SC_FLAT/MIX examples.
Figure 5 compares two BCC material regions with the same POL law. The single gyroid has a sampled gap ratio of 0.399, whereas no sampled gap is detected for the double gyroid. The different outcomes on the same lattice further illustrate the effect of the material geometry.
Figure 5. The BCC-SG/POL and BCC-DG/POL bands are compared.
Figures 1–5 show the ten complex band diagrams. Table 3 summarizes the runtimes of the ten complete calculations.
Table 3. Mean and population standard deviation of runtime (s) per wave number vector at tolerance 10 − 5 10^{-5} 1 0 − 5 , including initialization.
Runtime and Performance
Runtime includes initialization and the quasi-Newton solve for the first ten frequencies, with GPU synchronization; file output is excluded. Common initialization times are summed and divided equally among all sampled wave number vectors. Table 3 reports the mean and population standard deviation along each path.
We use the SC_CURV/SCAL example at k = ( π 2 , π , π 5 ) \mathbf{k} = \left(\frac{\pi}{2}, \pi, \frac{\pi}{5}\right) k = ( 2 π , π , 5 π ) to compare the outer tolerances 10 − 4 10^{-4} 1 0 − 4 , 10 − 5 10^{-5} 1 0 − 5 , 10 − 6 10^{-6} 1 0 − 6 , and 10 − 7 10^{-7} 1 0 − 7 . Table 4 reports the runtimes and the maximum absolute differences in the first ten normalized complex frequencies ω 2 π \frac{\omega}{2\pi} 2 π ω from the matched 10 − 7 10^{-7} 1 0 − 7 results. The runtimes include initialization and are taken from the first run.
Table 4. Runtime and maximum normalized frequency difference from the result at tolerance 1e-7.
The maximum difference over all tolerances is 7.778 × 10 − 11 7.778 \times10^{-11} 7.778 × 1 0 − 11 . Thus, 10 − 4 10^{-4} 1 0 − 4 is sufficient for the frequency accuracy observed in this fixed-grid example.
We compare the CPU and GPU implementations for the SC_CURV/SiC example at k = ( π , 0 , 0 ) \mathbf{k} = (\pi, 0, 0) k = ( π , 0 , 0 ) , with ten frequencies and outer tolerance 10 − 5 10^{-5} 1 0 − 5 . The CPU implementation uses one Intel Xeon Gold 6530 core and one thread with serial FFTW 3.3.10 and Eigen 3.4. The GPU implementation uses one RTX 4090D with cuFFT and cuBLAS. Both implementations use complex double precision and the same random initial block. The Generalized Davidson method limits the search dimension to four times the retained block size for N = 64 N = 64 N = 64 , 80, 96, 112 and three times the retained block size for N = 128 N = 128 N = 128 . Each configuration is timed once. Table 5 reports the initialization and quasi-Newton solve times.
Table 5. CPU and GPU runtimes including initialization for the SC_CURV/SiC example.
We fit the runtime in seconds against the number of degrees of freedom, 3 N 3 3N^3 3 N 3 , by linear least squares. The dimensionless coefficients of determination are R 2 = 0.9934 R^2 = 0.9934 R 2 = 0.9934 for the CPU and R ^ 2 = 0.9935 \widehat{R}^2 = 0.9935 R 2 = 0.9935 for the GPU. These values are close to one and indicate approximately linear growth over the five tested grid sizes, 64 ≤ N ≤ 128 64 \le N \le128 64 ≤ N ≤ 128 . The fitted slopes are 4.4894 × 10 − 3 4.4894 \times10^{-3} 4.4894 × 1 0 − 3 and 6.4175 × 10 − 5 6.4175 \times10^{-5} 6.4175 × 1 0 − 5 seconds per degree of freedom for the CPU and GPU, respectively. These fits describe the measured total runtimes over this range; a single matrix-free block application has the O ( m N 3 log N ) O(mN^{3}\log N) O ( m N 3 log N ) cost given in § 2 .
Convergence Histories
We compute the first ten frequencies with N = 120 N = 120 N = 120 at k = ( π 2 , π , π 5 ) \mathbf{k} = \left(\frac{\pi}{2}, \pi, \frac{\pi}{5}\right) k = ( 2 π , π , 5 π ) , using outer and inner tolerances 10 − 9 10^{-9} 1 0 − 9 and 10 − 10 10^{-10} 1 0 − 10 , respectively. Figure 6 shows the quasi-Newton residual histories for four examples.
Figure 6. Quasi-Newton residual histories for the first ten frequencies. The examples are SC_FLAT/POL, SC_CURV/SCAL, BCC-DG/POL, and FCC/POL, in row order.
All forty frequencies converge within two to four iterations, with final residuals below 7.64 × 10 − 10 7.64 \times10^{-10} 7.64 × 1 0 − 10 .
We evaluate ρ i ∗ \rho_i^* ρ i ∗ from (63) for the SC_CURV/SCAL example with N = 120 N = 120 N = 120 and k = ( π 2 , π , π 5 ) \mathbf{k} = \left(\frac{\pi}{2}, \pi, \frac{\pi}{5}\right) k = ( 2 π , π , 5 π ) . The outer and inner tolerances are 10 − 9 10^{-9} 1 0 − 9 and 10 − 10 10^{-10} 1 0 − 10 , respectively. The left eigenvectors are computed at the converged frequencies, with ∥ u i ∥ 2 = 1 \lVert\mathbf{u}_i \rVert_2 = 1 ∥ u i ∥ 2 = 1 and v i ∗ u i = 1 \mathbf{v}_i^* \mathbf{u}_i = 1 v i ∗ u i = 1 . Table 6 reports the moduli ∣ ρ i ∗ ∣ \lvert\rho_i^* \rvert ∣ ρ i ∗ ∣ to three significant digits.
Table 6. The moduli ∣ ρ i ∗ ∣ \lvert\rho_i^* \rvert ∣ ρ i ∗ ∣ evaluated from (4.18) for the SC_CURV/SCAL example with N = 120 N = 120 N = 120 and k = ( π 2 , π , π 5 ) \mathbf{k} = \left(\frac{\pi}{2}, \pi, \frac{\pi}{5}\right) k = ( 2 π , π , 5 π ) .
Conclusion
We have extended the kernel compensation framework to nonlinear, non-Hermitian Maxwell eigenproblems with an isotropic dispersive material law. The fixed discrete curl, divergence, and harmonic spaces give an exact unitary block diagonalization. Under the stated penalty condition, this decomposition proves that compensation preserves the eigenpairs of the original constrained nonlinear problem. The complex-coefficient preconditioning analysis gives a normal two-sided form, a line-segment spectral inclusion, and a condition-number bound independent of the grid size. These results justify the use of the inherited mimetic and DFT operators beyond the Hermitian setting.
The right Generalized Davidson solver supplies the eigenpair used in each frequency update. The derivative approximation uses the normalized right eigenvector and avoids an additional adjoint eigensolve. With exact inner eigenpairs, the iteration is locally linearly convergent when its error factor has modulus between zero and one. It is at least quadratic when the derivative defect vanishes at the root. We express this factor through the gradient of the material Rayleigh quotient and bound it using the relative gap of the Hermitian part.
The experiments demonstrate the complete matrix-free method for ten complex band calculations across five material geometries and three lattice types. In the four convergence tests, all forty frequencies converge within two to four outer iterations. The measured linear factors in the reported test are small, consistent with rapid convergence at the computed accuracy. For the specified SC_CURV/SiC comparison, the GPU implementation achieves speedups of 69.6–73.0 over the single-core, single-thread CPU implementation for 64 ≤ N ≤ 128 64 \le N \le128 64 ≤ N ≤ 128 . These results support the practical use of kernel compensation and the right-Rayleigh quasi-Newton update for large three-dimensional dispersive band calculations. An extension of the local analysis to multiple eigenvalues requires an invariant-subspace formulation.
Declaration of competing interest
The authors declare that they have no known competing financial interests or personal relationships that could have influenced the work reported in this paper.
Data availability
The data and code supporting this study are available from the corresponding author upon reasonable request.
Declaration of generative AI and AI-assisted technologies in the manuscript preparation process
During the preparation of this manuscript, the authors used OpenAI Codex to assist with manuscript revision, mathematical exposition, notation checks, and LaTeX preparation. The authors direct and review the revisions and take full responsibility for the content of the manuscript.