Browsing by Author "Huang, Tsung-Ming"

Now showing 1 - 20 of 25

A finite element based fast eigensolver for three dimensional anisotropic photonic crystals
(2019-06-01)
Chou, So-Hsiang
;
Huang, Tsung-Ming
;
Li, Tiexiang
;
Lin, Jia-Wei
;
Lin, Wen-Wei
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. (C) 2019 Elsevier Inc. All rights reserved.
A hybrid Jacobi-Davidson method for interior cluster eigenvalues with large null-space in three dimensional lossless Drude dispersive metallic photonic crystals
(2016-10)
Huang, Tsung-Ming
;
Lin, Wen-Wei
;
Wang, Weichung
;
應用數學系
;
Department of Applied Mathematics
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. (C) 2016 Elsevier B.V. All rights reserved.
A new two-phase structure-preserving doubling algorithm for critically singular M-matrix algebraic Riccati equations
(2016-03)
Huang, Tsung-Ming
;
Huang, Wei-Qiang
;
Li, Ren-Cang
;
Lin, Wen-Wei
;
應用數學系
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 (c) 2015 John Wiley & Sons, Ltd.
A NEWTON-TYPE METHOD WITH NONEQUIVALENCE DEFLATION FOR NONLINEAR EIGENVALUE PROBLEMS ARISING IN PHOTONIC CRYSTAL MODELING
(2016-01-01)
Huang, Tsung-Ming
;
Lin, Wen-Wei
;
Mehrmann, Volker
;
應用數學系
;
Department of Applied Mathematics
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 clustering eigenvalues. Numerical results illustrate that the proposed method is robust even for the case of computing many clustering eigenvalues in very large problems.
A NULL SPACE FREE JACOBI-DAVIDSON ITERATION FOR MAXWELL'S OPERATOR
(2015-01-01)
Huang, Yin-Liang
;
Huang, Tsung-Ming
;
Lin, Wen-Wei
;
Wang, Wei-Cheng
;
應用數學系
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.
A ROBUST NUMERICAL ALGORITHM FOR COMPUTING MAXWELL'S TRANSMISSION EIGENVALUE PROBLEMS
(2015-01-01)
Huang, Tsung-Ming
;
Huang, Wei-Qiang
;
Lin, Wen-Wei
;
應用數學系
;
丘成桐中心
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 eigenvalues.
An efficient numerical algorithm for computing densely distributed positive interior transmission eigenvalues
(2017-03-01)
Li, Tiexiang
;
Huang, Tsung-Ming
;
Lin, Wen-Wei
;
Wang, Jenn-Nan
;
應用數學系
We propose an efficient eigensolver for computing densely distributed spectra of the two-dimensional transmission eigenvalue problem (TEP), which is derived from Maxwell's equations with Tellegen media and the transverse magnetic mode. The governing equations, when discretized by the standard piecewise linear finite element method, give rise to a large-scale quadratic eigenvalue problem (QEP). Our numerical simulation shows that half of the positive eigenvalues of the QEP are densely distributed in some interval near the origin. The quadratic Jacobi-Davidson method with a so-called non-equivalence deflation technique is proposed to compute the dense spectrum of the QEP. Extensive numerical simulations show that our proposed method processes the convergence efficiently, even when it needs to compute more than 5000 desired eigenpairs. Numerical results also illustrate that the computed eigenvalue curves can be approximated by nonlinear functions, which can be applied to estimate the denseness of the eigenvalues for the TEP.
Computing the full spectrum of large sparse palindromic quadratic eigenvalue problems arising from surface Green's function calculations
(2018-03-01)
Huang, Tsung-Ming
;
Lin, Wen-Wei
;
Tian, Heng
;
Chen, Guan-Hua
;
應用數學系
Full spectrum of a large sparse inverted perpendicular-palindromic quadratic eigenvalue problem inverted perpendicular-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 inverted perpendicular-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 inverted perpendicular-skew-Hamiltonian implicitly restarted shift-and-invert Arnoldi G inverted perpendicular 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 inverted perpendicular 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 x 4000 at the density functional tight binding level, corresponding to a 8 x 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. (c) 2017 Elsevier Inc. All rights reserved.
CONVERGENCE ANALYSIS OF THE DOUBLING ALGORITHM FOR SEVERAL NONLINEAR MATRIX EQUATIONS IN THE CRITICAL CASE
(2009)
Chiang, Chun-Yueh
;
Chu, Eric King-Wah
;
Guo, Chun-Hua
;
Huang, Tsung-Ming
;
Lin, Wen-Wei
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.
Efficient Arnoldi-type algorithms for rational eigenvalue problems arising in fluid-solid systems
(2011-03-01)
Chou, So-Hsiang
;
Huang, Tsung-Ming
;
Huang, Wei-Qiang
;
Lin, Wen-Wei
;
應用數學系
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 = lambda"ss"x. For solving the GEP we apply Arnoldi algorithm to two different types of single matrices "ss"-1A and A"ss"-1. Numerical accuracy shows that the application of Arnoldi on A"ss"(-1) is better than that on "ss"(-1)A. (C) 2010 Elsevier Inc. All rights reserved.
EIGENDECOMPOSITION OF THE DISCRETE DOUBLE-CURL OPERATOR WITH APPLICATION TO FAST EIGENSOLVER FOR THREE-DIMENSIONAL PHOTONIC CRYSTALS
(2013)
Huang, Tsung-Ming
;
Hsieh, Han-En
;
Lin, Wen-Wei
;
Wang, Weichung
;
應用數學系
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 preconditioner. We also demonstrate how two forms of matrix-vector multiplications, which are the most costly part of the inverse Lanczos method, can be computed by fast Fourier transformation due to the eigendecomposition to significantly reduce the computation cost. Integrating all of these findings and techniques, we obtain a fast eigenvalue solver. The solver has been implemented by MATLAB and successfully solves each of a set of 5.184 million dimension eigenvalue problems within 50 to 104 minutes on a workstation with two Intel Quad-Core Xeon X5687 3.6 GHz CPUs.
Eigenvalue solvers for three dimensional photonic crystals with face-centered cubic lattice
(2014-12-15)
Huang, Tsung-Ming
;
Hsieh, Han-En
;
Lin, Wen-Wei
;
Wang, Weichung
;
應用數學系
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. (C) 2014 Elsevier B.V. All rights reserved.
Eigenvalue solvers for three dimensional photonic crystals with face-centered cubic lattice
(2014-12-15)
Huang, Tsung-Ming
;
Hsieh, Han-En
;
Lin, Wen-Wei
;
Wang, Weichung
;
應用數學系
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. (C) 2014 Elsevier B.V. All rights reserved.
Electromagnetic field behavior of 3D Maxwell's equations for chiral media
(2019-02-15)
Huang, Tsung-Ming
;
Li, Tiexiang
;
Chern, Ruey-Lin
;
Lin, Wen-Wei
;
應用數學系
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 gamma. We show that all the eigenvalues are real and finite for a small chirality gamma. For a critical value gamma = gamma*, the GEP has 2 x 2 Jordan blocks at infinity eigenvalues. Numerical results demonstrate that when gamma increases from gamma*, the 2 x 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. (C) 2018 Elsevier Inc. All rights reserved.
Highly efficient GPU eigensolver for three-dimensional photonic crystal band structures with any Bravais lattice
(2019-12-01)
Huang, Tsung-Ming
;
Lin, Wen-Wei
;
Tsai, Hsinhan
;
Wang, Weichung
;
應用數學系
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. (C) 2019 Elsevier B.V. All rights reserved.
Matrix representation of the double-curl operator for simulating three dimensional photonic crystals
(2013-07-01)
Huang, Tsung-Ming
;
Hsieh, Han-En
;
Lin, Wen-Wei
;
Wang, Weichung
;
應用數學系
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. (C) 2012 Elsevier Ltd. All rights reserved.
Numerical studies on structure-preserving algorithms for surface acoustic wave simulations
(2013-05-15)
Huang, Tsung-Ming
;
Li, Tiexiang
;
Lin, Wen-Wei
;
Wu, Chin-Tien
;
應用數學系
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. (c) 2012 Elsevier B.V. All rights reserved.
On the convergence of Ritz pairs and refined Ritz vectors for quadratic eigenvalue problems
(2013-12-01)
Huang, Tsung-Ming
;
Jia, Zhongxiao
;
Lin, Wen-Wei
;
應用數學系
;
Department of Applied Mathematics
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.
ON THE TRANSMISSION EIGENVALUE PROBLEM FOR THE ACOUSTIC EQUATION WITH A NEGATIVE INDEX OF REFRACTION AND A PRACTICAL NUMERICAL RECONSTRUCTION METHOD
(2018-08-01)
Li, Tiexiang
;
Huang, Tsung-Ming
;
Lin, Wen-Wei
;
Wang, Jenn-Nan
;
應用數學系
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 O(1) and the other half of eigenvalues are positive with order of O(10(2)). 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.
PALINDROMIC EIGENVALUE PROBLEMS: A BRIEF SURVEY
(2010-06-01)
Chu, Eric King-wah
;
Huang, Tsung-Ming
;
Lin, Wen-Wei
;
Wu, Chin-Tien
;
應用數學系
The T-palindromic quadratic eigenvalue problem (lambda(2)B + lambda C + A)x = 0, with A, B,C is an element of C(nxn), 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.