Browsing by Author "Li, Tiexiang"

Now showing 1 - 17 of 17

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 Novel Algorithm for Volume-Preserving Parameterizations of 3-Manifolds
(2019-01-01)
Yueh, Mei-Heng
;
Li, Tiexiang
;
Lin, Wen-Wei
;
Yau, Shing-Tung
;
應用數學系
Manifold parameterizations have been applied to various fields of commercial industries. Several efficient algorithms for the computation of triangular surface mesh parameterizations have been proposed in recent years. However, the computation of tetrahedral volumetric mesh parameterizations is more challenging due to the fact that the number of mesh points would become enormously large when the higher-resolution mesh is considered and the bijectivity of parameterizations is more difficult to guarantee. In this paper, we develop a novel volumetric stretch energy minimization algorithm for volume-preserving parameterizations of simply connected 3-manifolds with a single boundary under the restriction that the boundary is a spherical area-preserving mapping. In addition, our algorithm can also be applied to compute spherical angle- and area-preserving parameterizations of genus-zero closed surfaces, respectively. Several numerical experiments indicate that the developed algorithms are more efficient and reliable compared to other existing algorithms. Numerical results on applications of the manifold partition and the mesh processing for three-dimensional printing are demonstrated thereafter to show the robustness of the proposed algorithm.
A semiorthogonal generalized Arnoldi method and its variations for quadratic eigenvalue problems
(2013-03-01)
Huang, Wei-Qiang
;
Li, Tiexiang
;
Li, Yung-Ta
;
Lin, Wen-Wei
;
應用數學系
In this paper, we are concerned with the computation of a few eigenpairs with smallest eigenvalues in absolute value of quadratic eigenvalue problems. We first develop a semiorthogonal generalized Arnoldi method where the name comes from the application of a pseudo inner product in the construction of a generalized Arnoldi reduction for a generalized eigenvalue problem. The method applies the RayleighRitz orthogonal projection technique on the quadratic eigenvalue problem. Consequently, it preserves the spectral properties of the original quadratic eigenvalue problem. Furthermore, we propose a refinement scheme to improve the accuracy of the Ritz vectors for the quadratic eigenvalue problem. Given shifts, we also show how to restart the method by implicitly updating the starting vector and constructing better projection subspace. We combine the ideas of the refinement and the restart by selecting shifts upon the information of refined Ritz vectors. Finally, an implicitly restarted refined semiorthogonal generalized Arnoldi method is developed. Numerical examples demonstrate that the implicitly restarted semiorthogonal generalized Arnoldi method with or without refinement has superior convergence behaviors than the implicitly restarted Arnoldi method applied to the linearized quadratic eigenvalue problem. Copyright (c) 2012 John Wiley & Sons, Ltd.
A symmetric structure-preserving FQR algorithm for linear response eigenvalue problems
(2017-05-01)
Li, Tiexiang
;
Li, Ren-Cang
;
Lin, Wen-Wei
;
應用數學系
;
Department of Applied Mathematics
In this paper, we present an efficient PQR algorithm for solving the linear response eigenvalue problem H-x = lambda(x) , where H is Pi(-)-symmetric with respect to Gamma(0) = diag(I-n,-I-n). Based on newly introduced Gamma-orthogonal transformations, the PQR algorithm preserves the Pi(-)-symmetric structure of H throughout the whole process, and thus guarantees the computed eigenvalues to appear pairwise (lambda, -lambda) as they should. With the help of a newly established implicit Gamma-orthogonality theorem, we incorporate the implicit multi-shift technique to accelerate the convergence of the Gamma QR algorithm. Numerical experiments are given to show the effectiveness of the algorithm.(C) 2017 Elsevier Inc. All rights reserved.
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.
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.
Large-scale Stein and Lyapunov equations, Smith method, and applications
(2013-08-01)
Li, Tiexiang
;
Weng, Peter Chang-Yi
;
Chu, Eric King-wah
;
Lin, Wen-Wei
;
應用數學系
We consider the solution of large-scale Lyapunov and Stein equations. For Stein equations, the well-known Smith method will be adapted, with A(k) = A(2k) not explicitly computed but in the recursive form A(k) = A(k-1)(2), and the fast growing but diminishing components in the approximate solutions truncated. Lyapunov equations will be first treated with the Cayley transform before the Smith method is applied. For algebraic equations with numerically low-ranked solutions of dimension n, the resulting algorithms are of an efficient O(n) computational complexity and memory requirement per iteration and converge essentially quadratically. An application in the estimation of a lower bound of the condition number for continuous-time algebraic Riccati equations is presented, as well as some numerical results.
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 Spectral Analysis and a Novel Algorithm for Transmission Eigenvalue Problems
(2015-07-01)
Li, Tiexiang
;
Huang, Wei-Qiang
;
Lin, Wen-Wei
;
Liu, Jijun
;
應用數學系
The transmission eigenvalue problem, besides its critical role in inverse scattering problems, deserves special interest of its own due to the fact that the corresponding differential operator is neither elliptic nor self-adjoint. In this paper, we provide a spectral analysis and propose a novel iterative algorithm for the computation of a few positive real eigenvalues and the corresponding eigenfunctions of the transmission eigenvalue problem. Based on approximation using continuous finite elements, we first derive an associated symmetric quadratic eigenvalue problem (QEP) for the transmission eigenvalue problem to eliminate the nonphysical zero eigenvalues while preserve all nonzero ones. In addition, the derived QEP enables us to consider more refined discretization to overcome the limitation on the number of degrees of freedom. We then transform the QEP to a parameterized symmetric definite generalized eigenvalue problem (GEP) and develop a secant-type iteration for solving the resulting GEPs. Moreover, we carry out spectral analysis for various existence intervals of desired positive real eigenvalues, since a few lowest positive real transmission eigenvalues are of practical interest in the estimation and the reconstruction of the index of refraction. Numerical experiments show that the proposed method can find those desired smallest positive real transmission eigenvalues accurately, efficiently, and robustly.
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.
Solution of a nonsymmetric algebraic Riccati equation from a one-dimensional multistate transport model
(2011-10-01)
Li, Tiexiang
;
Chu, Eric King-Wah
;
Juang, Jong
;
Lin, Wen-Wei
;
應用數學系
For the steady-state solution of a differential equation from a one-dimensional multistate model in transport theory, we shall derive and study a nonsymmetric algebraic Riccati equation B(-) -XF(-) -F(+) X + XB(+)X = 0, where F(+/-) = (I -F) D(+/-) and B(+/-) = BD(+/-) with positive diagonal matrices D(+/-) and possibly low-ranked matrices F and B. We prove the existence of the minimal positive solution X* under a set of physically reasonable assumptions and study its numerical computation by fixed-point iteration, Newton's method and the doubling algorithm. We shall also study several special cases. For example when B and F are low ranked then X* = Gamma circle(Sigma(r)(i=1)U(i)V(i)(T)) with low-ranked U(i) and V(i) that can be computed using more efficient iterative processes. Numerical examples will be given to illustrate our theoretical results.
Solving large-scale continuous-time algebraic Riccati equations by doubling
(2013-01-01)
Li, Tiexiang
;
Chu, Eric King-wah
;
Lin, Wen-Wei
;
Weng, Peter Chang-Yi
;
應用數學系
We consider the solution of large-scale algebraic Riccati equations with numerically low-ranked solutions. For the discrete-time case, the structure-preserving doubling algorithm has been adapted, with the iterates for A not explicitly computed but in the recursive form A(k) = A(k-1)(2) - (DkSk-1)-S-(1)[D-k((2))](T), with D-k((1)) and D-k((2)) being low-ranked and S-k(-1) being small in dimension. For the continuous-time case, the algebraic Riccati equation will be first treated with the Cayley transform before doubling is applied. With n being the dimension of the algebraic equations, the resulting algorithms are of an efficient O(n) computational complexity per iteration, without the need for any inner iterations, and essentially converge quadratically. Some numerical results will be presented. For instance in Section 5.2, Example 3, of dimension n = 20 209 with 204 million variables in the solution X, was solved using MATLAB on a MacBook Pro within 45 s to a machine accuracy of O(10(-16)). (C) 2012 Elsevier B.V. All rights reserved.
SOLVING LARGE-SCALE NONSYMMETRIC ALGEBRAIC RICCATI EQUATIONS BY DOUBLING
(2013)
Li, Tiexiang
;
Chu, Eric King-Wah
;
Kuo, Yueh-Cheng
;
Lin, Wen-Wei
;
應用數學系
We consider the solution of the large-scale nonsymmetric algebraic Riccati equation XCX - XD - AX + B = 0, with M = [D, -C; -B, A] is an element of R(n perpendicular to+n2)x(n perpendicular to +n2) being a nonsingular M-matrix. In addition, A and D are sparselike, with the products A(-1)u, A(-T)u, D(-1)v, and D(-T)v computable in O(n) complexity (with n = max{n(1), n(2)}), for some vectors u and v, and B, C are low ranked. The structure-preserving doubling algorithms (SDA) by Guo, Lin, and Xu [Numer. Math., 103 (2006), pp. 392-412] is adapted, with the appropriate applications of the Sherman-Morrison-Woodbury formula and the sparse-plus-low-rank representations of various iterates. The resulting large-scale doubling algorithm has an O(n) computational complexity and memory requirement per iteration and converges essentially quadratically. A detailed error analysis, on the effects of truncation of iterates with an explicit forward error bound for the approximate solution from the SDA, and some numerical results will be presented.
Structure-preserving Gamma QR and Gamma-Lanczos algorithms for Bethe-Salpeter eigenvalue problems
(2018-10-15)
Guo, Zhen-Chen
;
Li, Tiexiang
;
Zhou, Ying-Ying
;
應用數學系
;
Department of Applied Mathematics
To solve the Bethe-Salpeter eigenvalue problem with distinct sizes, two efficient methods, called Gamma QR algorithm and Gamma-Lanczos algorithm, are proposed in this paper. Both algorithms preserve the special structure of the initial matrix. H = [(-(B) over bar) (A) (-(A) over bar) (B)], resulting the computed eigenvalues and the associated eigenvectors still hold the properties similar to those of dr. Theorems are given to demonstrate the validity of the proposed two algorithms in theory. Numerical results are presented to illustrate the superiorities of our methods. (C) 2018 Elsevier B.V. All rights reserved.
Structure-Preserving Methods for Computing Complex Band Structures of Three Dimensional Photonic Crystals
(2020-05-06)
Huang, Tsung-Ming
;
Li, Tiexiang
;
Lin, Jia-Wei
;
Lin, Wen-Wei
;
Tian, Heng
This work is devoted to the numerical computation of complex band structure k=k(omega)is an element of C3, 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 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 T-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.
The palindromic generalized eigenvalue problem A*x = lambda Ax: Numerical solution and applications
(2011-06-01)
Li, Tiexiang
;
Chiang, Chun-Yueh
;
Chu, Eric King-wah
;
Lin, Wen-Wei
;
應用數學系
In this paper, we propose the palindromic doubling algorithm (PDA) for the palindromic generalized eigenvalue problem (PGEP) A*x = lambda Ax. We establish a complete convergence theory of the PDA for PGEPs without unimodular eigenvalues, or with unimodular eigenvalues of partial multiplicities two (one or two for eigenvalue 1). Some important applications from the vibration analysis and the optimal control for singular descriptor linear systems will be presented to illustrate the feasibility and efficiency of the PDA. (C) 2009 Elsevier Inc. All rights reserved.
The Rayleigh-Ritz method, refinement and Arnoldi process for periodic matrix pairs
(2011-02-15)
Chu, Eric King-Wah
;
Fan, Hung-Yuan
;
Jia, Zhongxiao
;
Li, Tiexiang
;
Lin, Wen-Wei
We extend the Rayleigh-Ritz method to the eigen-problem of periodic matrix pairs. Assuming that the deviations of the desired periodic eigenvectors from the corresponding periodic subspaces tend to zero, we show that there exist periodic Ritz values that converge to the desired periodic eigenvalues unconditionally, yet the periodic Ritz vectors may fail to converge. To overcome this potential problem, we minimize residuals formed with periodic Ritz values to produce the refined periodic Ritz vectors, which converge under the same assumption. These results generalize the corresponding well-known ones for Rayleigh-Ritz approximations and their refinement for non-periodic eigen-problems. In addition, we consider a periodic Arnoldi process which is particularly efficient when coupled with the Rayleigh-Ritz method with refinement. The numerical results illustrate that the refinement procedure produces excellent approximations to the original periodic eigenvectors. (C) 2010 Elsevier B.V. All rights reserved.