Search

In this article, we propose the Fast Algorithms for Maxwell’s Equations (FAME) package for solving Maxwell’s equations for modeling three-dimensional photonic crystals. FAME combines the null-space free method with fast Fourier transform (FFT)-based matrix-vector multiplications to solve the generalized eigenvalue problems (GEPs) arising from Yee’s discretization. The GEPs are transformed into a null-space free standard eigenvalue problem with a Hermitian positive-definite coefficient matrix. The computation times for FFT-based matrix-vector multiplications with matrices of dimension 7 million are only 0.33 and 3.6 × 10 − 3 seconds using MATLAB with an Intel Xeon CPU and CUDA C++ programming with a single NVIDIA Tesla P100 GPU, respectively. Such multiplications significantly reduce the computational costs of the conjugate gradient method for solving linear systems. We successfully use FAME on a single P100 GPU to solve a set of GEPs with matrices of dimension more than 19 million, in 127 to 191 seconds per problem. These results demonstrate the potential of our proposed package to enable large-scale numerical simulations for novel physical discoveries and engineering applications of photonic crystals.

Utilizing the optimal mass transportation (OMT) technique to convert an irregular 3D brain image into a cube, a required input format for the U-net algorithm, is a brand new idea for medical imaging research. We develop a cubic volume-measure-preserving OMT (V-OMT) model for the implementation of this conversion. The contrast-enhanced histogram equalization grayscale of fluid attenuated inversion recovery (FLAIR) in a brain image creates the corresponding density function. We then propose an effective two-phase U-net algorithm combined with the V-OMT algorithm for training and validation. First, we use the U-net and V-OMT algorithms to precisely predict the whole tumor (WT) region. Second, we expand this predicted WT region with dilation and create a smooth function by convoluting the step-like function associated with the WT region in the brain image with a 5×5×5 blur tensor. Then, a new V-OMT algorithm with mesh refinement is constructed to allow the U-net algorithm to effectively train Net1--Net3 models. Finally, we propose ensemble voting postprocessing to validate the final labels of brain images. We randomly choose 1000 and 251 brain samples from theBraTS 2021 training dataset, which contains 1251 samples, for training and validation, respectively. The Dice scores of the WT, tumor core (TC) and enhanced tumor (ET) regions for validation computed by Net1--Net3 were 0.93705, 0.90617 and 0.87470, respectively. A significant improvement in brain tumor detection and segmentation with higher accuracy is achieved.

Optimal mass transportation has been widely applied in various fields, such as data compression, generative adversarial networks, and image processing. In this paper, we adopt the projected gradient method, combined with the homotopy technique, to find a minimal volume-measure-preserving solution for a 3-manifold optimal mass transportation problem. The proposed projected gradient method is shown to be sublinearly convergent at a rate of O(1/k). Several numerical experiments indicate that our algorithms can significantly reduce transportation costs. Some applications of the optimal mass transportation maps—to deformations and canonical normalizations between brains and solid balls—are demonstrated to show the robustness of our proposed algorithms.

The standard Yee's scheme for the Maxwell eigenvalue problem places the discrete electric field variable at the midpoints of the edges of the grid cells. It performs well when the permittivity is a scalar field. However, when the permittivity is a Hermitian full tensor field it would generate un-physical complex eigenvalues or frequencies. In this paper, we propose a finite element method which can be interpreted as a modified Yee's scheme to overcome this difficulty. This interpretation enables us to create a fast FFT eigensolver that can compute very effectively the band structure of the anisotropic photonic crystal with SC and FCC lattices. Furthermore, we overcome the usual large null space associated with the Maxwell eigenvalue problem by deriving a null-space free discrete eigenvalue problem which involves a crucial Hermitian positive definite linear system to be solved in each of the iteration steps. It is demonstrated that the CG method without preconditioning converges in 37 iterations even when the dimension of a matrix is as large as 5 , 184 , 000 .

This article focuses on numerically studying the eigenstructure behavior of generalized eigenvalue problems (GEPs) arising in three dimensional (3D) source-free Maxwell's equations with magnetoelectric coupling effects which model 3D reciprocal chiral media. It is challenging to solve such a large-scale GEP efficiently. We combine the null-space free method with the inexact shift-invert residual Arnoldi method and MINRES linear solver to solve the GEP with a matrix dimension as large as 5,308,416. The eigenstructure is heavily determined by the chirality parameter γ . We show that all the eigenvalues are real and finite for a small chirality γ . For a critical value γ = γ ⁎ , the GEP has 2 × 2 Jordan blocks at infinity eigenvalues. Numerical results demonstrate that when γ increases from γ ⁎ , the 2 × 2 Jordan block will first split into a complex conjugate eigenpair, then rapidly collide with the real axis and bifurcate into positive (resonance) and negative eigenvalues with modulus smaller than the other existing positive eigenvalues. The resonance band also exhibits an anticrossing interaction. Moreover, the electric and magnetic fields of the resonance modes are localized inside the structure, with only a slight amount of field leaking into the background (dielectric) material.

This paper focuses on studying the bifurcation analysis of the eigenstructure of the $\gamma$-parameterized generalized eigenvalue problem ($\gamma$-GEP) arising in three-dimensional (3D) source-free Maxwell's equations with Pasteur media, where $\gamma$ is the magnetoelectric chirality parameter. For the weakly coupled case, namely, $\gamma < \gamma_{*} \equiv$ critical value, the $\gamma$-GEP is positive definite, which has been well-studied by Chern et.\ al, 2015. For the strongly coupled case, namely, $\gamma > \gamma_{*}$, the $\gamma$-GEP is no longer positive definite, introducing a totally different and complicated structure. For the critical strongly coupled case, numerical computations for electromagnetic fields have been presented by Huang et.\ al, 2018. In this paper, we build several theoretical results on the eigenstructure behavior of the $\gamma$-GEPs. We prove that the $\gamma$-GEP is regular for any $\gamma > 0$, and the $\gamma$-GEP has $2 \times 2$ Jordan blocks of infinite eigenvalues at the critical value $\gamma_{*}$. Then, we show that the $2 \times 2$ Jordan block will split into a complex conjugate eigenvalue pair that rapidly goes down and up and then collides at some real point near the origin. Next, it will bifurcate into two real eigenvalues, with one moving toward the left and the other to the right along the real axis as $\gamma$ increases. A newly formed state whose energy is smaller than the ground state can be created as $\gamma$ is larger than the critical value. This stunning feature of the physical phenomenon would be very helpful in practical applications. Therefore, the purpose of this paper is to clarify the corresponding theoretical eigenstructure of 3D Maxwell's equations with Pasteur media., Comment: 26 pages, 5 figures

This work is devoted to the numerical computation of complex band structure $$\mathbf {k}=\mathbf {k}(\omega )\in {\mathbb {C}}^3$$, with $$\omega $$ being positive frequencies, of three dimensional isotropic dispersive or non-dispersive photonic crystals from the perspective of structured quadratic eigenvalue problems (QEPs). Our basic strategy is to fix two degrees of freedom in $$\mathbf {k}$$ and to view the remaining one as the eigenvalue of a complex gyroscopic QEP which stems from Maxwell’s equations discretized by Yee’s scheme. We reformulate this gyroscopic QEP into a $$\top $$-palindromic QEP, which is further transformed into a structured generalized eigenvalue problem for which we have established a structure-preserving shift-and-invert Arnoldi algorithm. Moreover, to accelerate the inner iterations of the shift-and-invert Arnoldi algorithm, we propose an efficient preconditioner which makes most of the fast Fourier transforms. The advantage of our method is discussed in detail and corroborated by several numerical results.

Full spectrum of a large sparse ⊤-palindromic quadratic eigenvalue problem (⊤-PQEP) is considered arguably for the first time in this article. Such a problem is posed by calculation of surface Green's functions (SGFs) of mesoscopic transistors with a tremendous non-periodic cross-section. For this problem, general purpose eigensolvers are not efficient, nor is advisable to resort to the decimation method etc. to obtain the Wiener–Hopf factorization. After reviewing some rigorous understanding of SGF calculation from the perspective of ⊤-PQEP and nonlinear matrix equation, we present our new approach to this problem. In a nutshell, the unit disk where the spectrum of interest lies is broken down adaptively into pieces small enough that they each can be locally tackled by the generalized ⊤-skew-Hamiltonian implicitly restarted shift-and-invert Arnoldi (G⊤SHIRA) algorithm with suitable shifts and other parameters, and the eigenvalues missed by this divide-and-conquer strategy can be recovered thanks to the accurate estimation provided by our newly developed scheme. Notably the novel non-equivalence deflation is proposed to avoid as much as possible duplication of nearby known eigenvalues when a new shift of G⊤SHIRA is determined. We demonstrate our new approach by calculating the SGF of a realistic nanowire whose unit cell is described by a matrix of size 4000 × 4000 at the density functional tight binding level, corresponding to a 8 × 8 nm 2 cross-section. We believe that quantum transport simulation of realistic nano-devices in the mesoscopic regime will greatly benefit from this work.

In this paper, we consider the two-dimensional Maxwell's equations with the TM mode in pseudo-chiral media. The system can be reduced to the acoustic equation with a negative index of refraction. We first study the transmission eigenvalue problem (TEP) for this equation. By the continuous finite element method, we discretize the reduced equation and transform the study of TEP to a quadratic eigenvalue problem by deflating all nonphysical zeros. We then estimate half of the eigenvalues are negative with order of \begin{document}$O(1)$\end{document} and the other half of eigenvalues are positive with order of \begin{document}$O(10^2)$\end{document} . In the second part of the paper, we present a practical numerical method to reconstruct the support of the inhomogeneity by the near-field measurements, i.e., Cauchy data. Based on the linear sampling method, we propose the truncated singular value decomposition to solve the ill-posed near-field integral equation, at one wave number which is not a transmission eigenvalue. By carefully chosen an indicator function, this method produce different jumps for the sampling points inside and outside the support. Numerical results show that our method is able to reconstruct the support reliably.

Numerical simulations play a significant role in studying the properties of dispersive metallic photonic crystals. The dispersive photonic crystals are modeled by the Maxwell equations, and the equations are then discretized by the widely-used Yee’s scheme. After applying certain similarity transformations to the discretized system, the original simulation problem becomes a non-Hermitian eigenvalue problem with clustered eigenvalues. An efficient contour integral (CI) based eigensolver is developed to overcome the difficulties of applying existing methods to solve eigenvalues in designated regions. This efficient method combines the contour integral, the fast matrix–vector multiplication, and efficient linear system solver. The numerical results illustrate the efficiency of our algorithm.

This paper focuses on studying the eigenstructure of generalized eigenvalue problems (GEPs) arising in the three-dimensional source-free Maxwell equations for bi-anisotropic complex media with a 3-by-3 permittivity tensor e > 0 , a permeability tensor μ > 0 , and scalar magnetoelectric coupling constants ξ = ζ = i γ . The bi-Lebedev scheme is appealing because it preserves the symmetry inherent to the Maxwell eigenvalue problem exactly and because full degrees of freedom of electromagnetic fields at each grid point are taken into account in the discretization. The resulting GEP has eigenvalues appearing in quadruples { ± ω , ± ω } . We consider two main scenarios, where γ γ ∗ and γ > γ ∗ with γ ∗ as a critical value. In the former case, all the eigenvalues are real. In the latter case, the GEP has complex eigenvalues, and we particularly focus on the bifurcation of the eigenstructure of the GEPs. Numerical results demonstrate that the newborn ground state has occurred after γ = γ > γ ∗ , and the associated eigenvector has an exotic phenomenon of localization. Moreover, the Poynting vectors of the newborn eigenvector not only are concentrated in the material but also display exciting patterns.

Summary Numerical solution of nonlinear eigenvalue problems (NEPs) is frequently encountered in computational science and engineering. The applicability of most existing methods is limited by the matrix structures, properties of the eigen-solutions, sizes of the problems, etc. This paper aims to remove those limitations and develop robust and universal NEP solvers for large-scale engineering applications. The novelty lies in two aspects. First, a rational interpolation approach (RIA) is proposed based on the Keldysh theorem for holomorphic matrix functions. Comparing with the existing contour integral approach, the RIA provides the possibility to select sampling points in more general regions and has advantages in improving the accuracy and reducing the computational cost. Second, a resolvent sampling scheme using the RIA is proposed to construct reliable search spaces for the Rayleigh-Ritz procedure, based on which a robust eigen-solver, called RSRR, is developed for solving general NEPs. The RSRR can be easily implemented and parallelized. The advantages of the RIA and the performance of the RSRR are demonstrated by a variety of benchmark and application examples. This article is protected by copyright. All rights reserved.

We study how to efficiently solve the eigenvalue problems in computing band structure of three-dimensional dispersive metallic photonic crystals with face-centered cubic lattices based on the lossless Drude model. The discretized Maxwell equations result in large-scale standard eigenvalue problems whose spectrum contains many zero and cluster eigenvalues, both prevent existed eigenvalue solver from being efficient. To tackle this computational difficulties, we propose a hybrid Jacobi–Davidson method (hHybrid) that integrates harmonic Rayleigh–Ritz extraction, a new and hybrid way to compute the correction vectors, and a FFT-based preconditioner. Intensive numerical experiments show that the hHybrid outperforms existed eigenvalue solvers in terms of timing and convergence behaviors.

The numerical simulation of the band structure of three-dimensional dispersive metallic photonic crystals with face-centered cubic lattices leads to large-scale nonlinear eigenvalue problems, which are very challenging due to a high-dimensional subspace associated with the eigenvalue zero and the fact that the desired eigenvalues (with smallest real part) cluster and are close to the zero eigenvalues. For the solution of the nonlinear eigenvalue problem, a Newton-type iterative method is proposed and the nullspace-free method is applied to exclude the zero eigenvalues from the associated generalized eigenvalue problem. To find the successive eigenvalue/eigenvector pairs, we propose a new nonequivalence deflation method to transform converged eigenvalues to infinity, while all other eigenvalues remain unchanged. The deflated problem is then solved by the same Newton-type method, which is used as a hybrid method that combines with the Jacobi--Davidson and the nonlinear Arnoldi methods to compute the cluster...

A null-space free method with the FFT-based matrix–vector multiplications was proposed to solve the Maxwell equations that model the three-dimensional photonic crystals. The most time-consuming parts of this method were the FFT-based matrix–vector multiplications. In this article, we propose new mathematical formulas to compute the FFT-based matrix–vector multiplications and derive highly efficient algorithms on top of the NVIDIA GPU architecture. The resulting algorithms are approximately two- to threefold faster than the previous algorithms. We have successfully used a single NVIDIA Tesla P100 GPU to solve a set of generalized eigenvalue problems of 5 , 184 , 000 dimensions in 17 to 22 seconds for each problem. Furthermore, we ported the codes to a GPU cluster and achieved near linear scalability. To our knowledge, these GPU implementations of the proposed algorithms are the fastest implementations. The schemes can be applied to simulate a three-dimensional photonic crystal with all 14 Bravais lattices. These highly efficient schemes and codes raise possibilities for large-scale and near real-time numerical simulations for novel physical discoveries and engineering applications of photonic crystals.

Summary Among numerous iterative methods for solving the minimal nonnegative solution of an M-matrix algebraic Riccati equation, the structure-preserving doubling algorithm (SDA) stands out owing to its overall efficiency as well as accuracy. SDA is globally convergent and its convergence is quadratic, except for the critical case for which it converges linearly with the linear rate 1/2. In this paper, we first undertake a delineatory convergence analysis that reveals that the approximations by SDA can be decomposed into two components: the stable component that converges quadratically and the rank-one component that converges linearly with the linear rate 1/2. Our analysis also shows that as soon as the stable component is fully converged, the rank-one component can be accurately recovered. We then propose an efficient hybrid method, called the two-phase SDA, for which the SDA iteration is stopped as soon as it is determined that the stable component is fully converged. Therefore, this two-phase SDA saves those SDA iterative steps that previously have to have for the rank-one component to be computed accurately, and thus essentially, it can be regarded as a quadratically convergent method. Numerical results confirm our analysis and demonstrate the efficiency of the new two-phase SDA. Copyright © 2015 John Wiley & Sons, Ltd.

We study a robust and efficient eigensolver for computing a few smallest positive eigenvalues of the three-dimensional Maxwell's transmission eigenvalue problem. The discretized governing equations by the Nedelec edge element result in a large-scale quadratic eigenvalue problem (QEP) for which the spectrum contains many zero eigenvalues and the coefficient matrices consist of patterns in the matrix form $XY^{-1}Z$, both of which prevent existing eigenvalue solvers from being efficient. To remedy these difficulties, we rewrite the QEP as a particular nonlinear eigenvalue problem and develop a secant-type iteration, together with an indefinite locally optimal block preconditioned conjugate gradient (LOBPCG) method, to sequentially compute the desired positive eigenvalues. Furthermore, we propose a novel method to solve the linear systems in each iteration of LOBPCG. Intensive numerical experiments show that our proposed method is robust, although the desired real eigenvalues are surrounded by complex eigenv...

We present an efficient null space free Jacobi--Davidson method to compute the positive eigenvalues of time harmonic Maxwell's equations. We focus on a class of spatial discretizations that guarantee the existence of discrete vector potentials, such as Yee's scheme and the edge elements. During the Jacobi--Davidson iteration, the correction process is applied to the vector potential instead. The correction equation is solved approximately as in the standard Jacobi--Davidson approach. The computational cost of the transformation from the vector potential to the corrector is negligible. As a consequence, the expanding subspace automatically stays out of the null space and no extra projection step is needed. Numerical evidence confirms that the proposed scheme indeed outperforms the standard and projection-based Jacobi--Davidson methods by a significant margin.

To numerically determine the band structure of three-dimensional photonic crystals with face-centered cubic lattices, we study how the associated large-scale generalized eigenvalue problem (GEP) can be solved efficiently. The main computational challenge is due to the complexity of the coefficient matrix and the fact that the desired eigenvalues are interior. For solving the GEP by the shift-and-invert Lanczos method, we propose a preconditioning for the associated linear system therein. Recently, a way to reformat the GEP to the null space free eigenvalue problem (NFEP) is proposed. For solving the NFEP, we analyze potential advantages and disadvantages of the null space free inverse Lanczos method, the shift-invert residual Arnoldi method, and the Jacobi-Davidson method from theoretical viewpoints. These four approaches are compared numerically to find out their properties. The numerical results suggest that the shift-invert residual Arnoldi method with an initialization scheme is the fastest and the most robust eigensolver for the target eigenvalue problems. Our findings promise to play an essential role in simulating photonic crystals.

For a given subspace, the Rayleigh-Ritz method projects the large quadratic eigenvalue problem (QEP) onto it and produces a small sized dense QEP. Similar to the Rayleigh-Ritz method for the linear eigenvalue problem, the Rayleigh-Ritz method defines the Ritz values and the Ritz vectors of the QEP with respect to the projection subspace. We analyze the convergence of the method when the angle between the subspace and the desired eigenvector converges to zero. We prove that there is a Ritz value that converges to the desired eigenvalue unconditionally but the Ritz vector converges conditionally and may fail to converge. To remedy the drawback of possible non-convergence of the Ritz vector, we propose a refined Ritz vector that is mathematically different from the Ritz vector and is proved to converge unconditionally. We construct examples to illustrate our theory., Comment: 20 pages

a b s t r a c t Three dimensional photonic crystals can be modeled by the Maxwell equations as a generalized eigenvalue problem (GEVP). Simulations based on the numerical solutions of the GEVP are used to reveal physical properties and boost innovative applications of photonic crystals. However, to solve these GEVP remains a computational challenge in both timing and accuracy. The GEVP corresponding to the photonic crystals with face centered cubic (FCC) lattice is one of the challenging eigenvalue problems. From a viewpoint of matrix computation, we demonstrate how such obstacles can be overcome. Our main contribution is an explicit matrix representation of the double-curl operator associated with the photonic crystal with FCC lattice. This particular matrix represents the degenerate coefficient matrix of the discrete GEVP obtained by Yee's scheme. The explicit matrix leads to an eigendecomposition of the degenerate coefficient matrix and then a fast eigenvalue solver. Promising numerical results in terms of timing and accuracy are reported for solving the discrete GEVP arising in three dimensional photonic crystals with various geometric parameters.

We study the generalized eigenvalue problems (GEPs) that arise from modeling leaky surface wave propagation in an acoustic resonator with an infinite amount of periodically arranged interdigital transducers. The constitutive equations are discretized by finite element methods with mesh refinements along the electrode interfaces and corners. The nonzero eigenvalues of the resulting GEP appear in reciprocal pairs (@l,1/@l). We transform the GEP into a T-palindromic quadratic eigenvalue problem (TPQEP) to reveal the important reciprocal relationships of the eigenvalues. The TPQEP is then solved by a structure-preserving algorithm incorporating a generalized T-skew-Hamiltonian implicitly restarted Arnoldi method so that the reciprocal relationship of the eigenvalues may be automatically preserved. Compared with applying the Arnoldi method to solve the GEPs, our numerical results show that the eigenpairs produced by the proposed structure-preserving method not only preserve the reciprocal property but also possess high efficiency and accuracy.

We study the generalized eigenvalue problems (GEPs) derived from modeling the surface acoustic wave in piezoelectric materials with periodic inhomogeneity. The eigenvalues appear in the reciprocal pairs due to periodic boundary conditions in the modeling. By transforming the GEP into a T-palindromic quadratic eigenvalue problem (TPQEP), the reciprocal relationship of the eigenvalues can be maintained. In this paper, we outline four recently developed structure-preserving algorithms, SA, SDA, TSHIRA and GTSHIRA, for solving the TPQEP. Numerical comparisons on the accuracy and the computational costs of these algorithm are presented. The eigenvalues close to unit circle on the complex plane are of interest in the area of filter and sensor designs. Our numerical results show that the Arnoldi-type structure-preserving algorithms TSHIRA and GTSHIRA with ''re-symplectic'' and ''re-bi-isotropic'' processes, respectively, are as accurate as the SA and SDA algorithms, and more efficient in finding these eigenvalues.

This article focuses on the discrete double-curl operator arising in the Maxwell equation that models three-dimensional photonic crystals with face-centered cubic lattice. The discrete double-curl operator is the degenerate coefficient matrix of the generalized eigenvalue problems (GEVP) due to the Maxwell equation. We derive an eigendecomposition of the degenerate coefficient matrix and explore an explicit form of orthogonal basis for the range and null spaces of this matrix. To solve the GEVP, we apply these theoretical results to project the GEVP to a standard eigenvalue problem (SEVP), which involves only the eigenspace associated with the nonzero eigenvalues of the GEVP, and therefore the zero eigenvalues are excluded and will not degrade the computational efficiency. This projected SEVP can be solved efficiently by the inverse Lanczos method. The linear systems within the inverse Lanczos method are well-conditioned and can be solved efficiently by the conjugate gradient method without using a precon...

The band structures of three-dimensional photonic crystals can be determined numerically by solving a sequence of generalized eigenvalue problems. However, not all of the spectral structures of these eigenvalue problems are well-understood, and not all of these eigenvalue problems can be solved efficiently. This article focuses on the eigenvalue problems corresponding to wave vectors that are close to the center of the Brillouin zone of a three dimensional, simple cubic photonic crystal. For these eigenvalue problems, there are (i) many zero eigenvalues, (ii) a couple of near-zero eigenvalues, and (iii) several larger eigenvalues. As the desired eigenvalues are the smallest positive eigenvalues, these particular spectral structures prevent regular eigenvalue solvers from efficiently computing the desired eigenvalues. We study these eigenvalue problems from the perspective of both theory and computation. On the theoretical side, the structures of the null spaces are analyzed to explicitly determine the number of zero eigenvalues of the target eigenvalue problems. On the computational side, the Krylov-Schur and Jacobi-Davidson methods are used to compute the smallest, positive, interior eigenvalues that are of interest. Intensive numerical experiments disclose how the shift values, conditioning numbers, and initial vectors affect the performance of the tested eigenvalue solvers and suggest the most efficient eigenvalue solvers.

We consider a rational algebraic large sparse eigenvalue problem arising in the discretization of the finite element method for the dissipative acoustic model in the pressure formulation. The presence of nonlinearity due to the frequency-dependent impedance poses a challenge in developing an efficient numerical algorithm for solving such eigenvalue problems. In this article, we reformulate the rational eigenvalue problem as a cubic eigenvalue problem and then solve the resulting cubic eigenvalue problem by a parallel restricted additive Schwarz preconditioned Jacobi–Davidson algorithm (ASPJD). To validate the ASPJD-based eigensolver, we numerically demonstrate the optimal convergence rate of our discretization scheme and show that ASPJD converges successfully to all target eigenvalues. The extraneous root introduced by the problem reformulation does not cause any observed side effect that produces an undesirable oscillatory convergence behavior. By performing intensive numerical experiments, we identify an efficient correction-equation solver, an effective algorithmic parameter setting, and an optimal mesh partitioning. Furthermore, the numerical results suggest that the ASPJD-based eigensolver with an optimal mesh partitioning results in superlinear scalability on a distributed and parallel computing cluster scaling up to 192 processors.

We develop and analyze efficient methods for computing damped vibration modes of an acoustic fluid confined in a cavity with absorbing walls capable of dissipating acoustic energy. The discretization in terms of pressure nodal finite elements gives rise to a rational eigenvalue problem. Numerical evidence shows that there are no spurious eigenmodes for such discretization and also confirms that the discretization based on nodal pressures is much more efficient than that based on Raviart-Thomas finite elements for the displacement field. The trimmed linearization method is used to linearize the associated rational eigenvalue problem into a generalized eigenvalue problem (GEP) of the form Ax=@lBx. For solving the GEP we apply Arnoldi algorithm to two different types of single matrices B^-^1A and AB^-^1. Numerical accuracy shows that the application of Arnoldi on AB^-^1 is better than that on B^-^1A.

To explore band structures of three-dimensional photonic crystals numerically, we need to solve the eigenvalue problems derived from the governing Maxwell equations. The solutions of these eigenvalue problems cannot be computed effectively unless a suitable combination of eigenvalue solver and preconditioner is chosen. Taking eigenvalue problems due to Yee's scheme as examples, we propose using Krylov-Schur method and Jacobi-Davidson method to solve the resulting eigenvalue problems. For preconditioning, we derive several novel preconditioning schemes based on various preconditioners, including a preconditioner that can be solved by Fast Fourier Transform efficiently. We then conduct intensive numerical experiments for various combinations of eigenvalue solvers and preconditioning schemes. We find that the Krylov-Schur method associated with the Fast Fourier Transform based preconditioner is very efficient. It remarkably outperforms all other eigenvalue solvers with common preconditioners like Jacobi, Symmetric Successive Over Relaxation, and incomplete factorizations. This promising solver can benefit applications like photonic crystal structure optimization.

We develop a parallel Jacobi-Davidson approach for finding a partial set of eigenpairs of large sparse polynomial eigenvalue problems with application in quantum dot simulation. A Jacobi-Davidson eigenvalue solver is implemented based on the Portable, Extensible Toolkit for Scientific Computation (PETSc). The eigensolver thus inherits PETSc's efficient and various parallel operations, linear solvers, preconditioning schemes, and easy usages. The parallel eigenvalue solver is then used to solve higher degree polynomial eigenvalue problems arising in numerical simulations of three dimensional quantum dots governed by Schrodinger's equations. We find that the parallel restricted additive Schwarz preconditioner in conjunction with a parallel Krylov subspace method (e.g. GMRES) can solve the correction equations, the most costly step in the Jacobi-Davidson algorithm, very efficiently in parallel. Besides, the overall performance is quite satisfactory. We have observed near perfect superlinear speedup by using up to 320 processors. The parallel eigensolver can find all target interior eigenpairs of a quintic polynomial eigenvalue problem with more than 32 million variables within 12 minutes by using 272 Intel 3.0GHz processors.

In this paper, based on Patel's algorithm (1993), we propose a structure-preserving algorithm for solving palindromic quadratic eigenvalue problems (QEPs). We also show the relationship between the structure-preserving algorithm and the URV-based structure-preserving algorithm by Schroder (2007). For large sparse palindromic QEPs, we develop a generalized $\top$-skew-Hamiltonian implicitly restarted shift-and-invert Arnoldi algorithm for solving the resulting $\top$-skew-Hamiltonian pencils. Numerical experiments show that our proposed structure-preserving algorithms perform well on the palindromic QEP arising from a finite element model of high-speed trains and rails.

This article focuses on solving the generalized eigenvalue problems (GEP) arising in the source-free Maxwell equation with magnetoelectric coupling effects that models three-dimensional complex media. The goal is to compute the smallest positive eigenvalues, and the main challenge is that the coefficient matrix in the discrete Maxwell equation is indefinite and degenerate. To overcome this difficulty, we derive a singular value decomposition (SVD) of the discrete single-curl operator and then explicitly express the basis of the invariant subspace corresponding to the nonzero eigenvalues of the GEP. Consequently, we reduce the GEP to a null space free standard eigenvalue problem (NFSEP) that contains only the nonzero (complex) eigenvalues of the GEP and can be solved by the shift-and-invert Arnoldi method without being disturbed by the null space. Furthermore, the basis of the eigendecomposition is chosen carefully so that we can apply fast Fourier transformation (FFT)-based matrix vector multiplication to solve the embedded linear systems efficiently by an iterative method. For chiral and pseudochiral complex media, which are of great interest in magnetoelectric applications, the NFSEP can be further transformed to a null space free generalized eigenvalue problem whose coefficient matrices are Hermitian and Hermitian positive definite (HHPD-NFGEP). This HHPD-NFGEP can be solved by using the invert Lanczos method without shifting. Furthermore, the embedded linear system can be solved efficiently by using the conjugate gradient method without preconditioning and the FFT-based matrix vector multiplications. Numerical results are presented to demonstrate the efficiency of the proposed methods.

The Jacobi-Davidson (JD) algorithm recently has gained popularity for finding a few selected interior eigenvalues of large sparse polynomial eigenvalue problems, which commonly appear in many computational science and engineering PDE based applications. As other inner–outer algorithms like Newton type method, the bottleneck of the JD algorithm is to solve approximately the inner correction equation. In the previous work, [Hwang, Wei, Huang, and Wang, A Parallel Additive Schwarz Preconditioned Jacobi-Davidson (ASPJD) Algorithm for Polynomial Eigenvalue Problems in Quantum Dot (QD) Simulation, Journal of Computational Physics (2010)], the authors proposed a parallel restricted additive Schwarz preconditioner in conjunction with a parallel Krylov subspace method to accelerate the convergence of the JD algorithm. Based on the previous computational experiences on the algorithmic parameter tuning for the ASPJD algorithm, we further investigate the parallel performance of a PETSc based ASPJD eigensolver on the Blue Gene/P, and a QD quintic eigenvalue problem is used as an example to demonstrate its scalability by showing the excellent strong scaling up to 2,048 cores.

The T-palindromic quadratic eigenvalue problem $(\lambda^2 B + \lambda C + A)x = 0$, with $A,B,C \in \mathbb{C}^{n \times n}$, $C^T = C$ and $B^T = A$, governs the vibration behaviour of trains. Other palindromic eigenvalue problems, quadratic or higher order, arise from applications in surface acoustic wave filters, optimal control of discrete-time systems and crack modelling. Numerical solution of palindromic eigenvalue problems is challenging, with unacceptably low accuracy from the basic linearization approach. In this survey paper, we shall talk about the history of palindromic eigenvalue problems, in terms of their history, applications, numerical solution and generalization. We shall also speculate on some future directions of research.

Nano-scale quantum dot simulations result in large-scale polynomial eigenvalue problems. It remains unclear how these problems can be solved efficiently. We fill this gap in capability partially by proposing a polynomial Jacobi-Davidson method framework, including several varied schemes for solving the associated correction equations. We investigate the performance of the proposed Jacobi-Davidson methods for solving the polynomial eigenvalue problems and several Krylov subspace methods for solving the linear eigenvalue problems with the use of various linear solvers and preconditioning schemes. This study finds the most efficient scheme combinations for different types of target problems.

In this paper, we review two types of doubling algorithm and some techniques for analyzing them. We then use the techniques to study the doubling algorithm for three different nonlinear matrix equations in the critical case. We show that the convergence of the doubling algorithm is at least linear with rate 1/2. As compared to earlier work on this topic, the results we present here are more general, and the analysis here is much simpler. NSERC, NSC (Taiwan), NCTS (Taiwan) Faculty yes