Browsing by Author "Lin, Wen-Wei"

Now showing 1 - 20 of 80

A FAST ALGORITHM FOR FAST TRAIN PALINDROMIC QUADRATIC EIGENVALUE PROBLEMS
(2016-01-01)
Lu, Linzhang
;
Wang, Teng
;
Kuo, Yueh-Cheng
;
Li, Ren-Cang
;
Lin, Wen-Wei
In the vibration analysis of high speed trains arises such a palindromic quadratic eigenvalue problem (PQEP) (lambda(2) A(T)+ lambda Q + A)z = 0, where A;Q is an element of C-nxn have special structures: both Q and A are m x m block matrices with each block being k x k (thus n = m x k), and Q is complex symmetric and tridiagonal block-Toeplitz, and A has only one nonzero block in the (1, m)th block position which is the same as the subdiagonal block of Q. This PQEP has eigenvalues 0 and infinity each of multiplicity (m - 1) k just by examining A, but it is its remaining 2k eigenvalues, usually nonzero and finite but with an extreme wide range in magnitude, that are of interest. The problem is notoriously difficult numerically. Earlier methods that seek to deflate eigenvalues 0 and infinity first often produce eigenvalues that are too inaccurate to be useful due to the large errors introduced in the deflation process. The solvent approach proposed by Guo and Lin in 2010 changed the situation because it can deliver sufficiently accurate eigenvalues. In this paper, we propose a fast algorithm along the line of the solvent approach. The theoretical foundation of our algorithm is the connection we establish here between this fast train PQEP and a k x k PQEP defined by the subblocks of A and Q without any computational work. This connection lends itself to a fast algorithm: solve the k x k PQEP and then use its eigenpairs to recover the eigenpairs for the original fast train PQEP. The so-called alpha-structured backward error analysis that preserves all possible structures in the fast train PQEP to the extreme is studied. Finally numerical examples are presented to show the effectiveness of the new fast algorithm.
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 FRACTIONAL STEP IMMERSED BOUNDARY METHOD FOR STOKES FLOW WITH AN INEXTENSIBLE INTERFACE ENCLOSING A SOLID PARTICLE
(2012)
Lai, Ming-Chih
;
Hu, Wei-Fan
;
Lin, Wen-Wei
;
應用數學系
;
數學建模與科學計算所(含中心)
In this paper, we develop a fractional step method based on the immersed boundary (IB) formulation for Stokes flow with an inextensible (incompressible) interface enclosing a solid particle. In addition to solving for the fluid variables such as the velocity and pressure, the present problem involves finding an extra unknown elastic tension such that the surface divergence of the velocity is zero along the interface, and an extra unknown particle surface force such that the velocity satisfies the no-slip boundary condition along the particle surface. While the interface moves with local fluid velocity, the enclosed particle hereby undergoes a rigid body motion, and the system is closed by the force-free and torque-free conditions along the particle surface. The equations are then discretized by standard centered difference schemes on a staggered grid, and the interactions between the interface and particle with the fluid are discretized using a discrete delta function as in the IB method. The resultant linear system of equations is symmetric and can be solved by fractional steps so that only fast Poisson solvers are involved. The present method can be extended to Navier-Stokes flow with moderate Reynolds number by treating the nonlinear advection terms explicitly for the time integration. The convergent tests for a Stokes solver with or without an inextensible interface are performed and confirm the desired accuracy. The tank-treading to tumbling motion for an inextensible interface enclosing a solid particle with different filling fractions under a simple shear flow has been studied extensively, and the results here are in good agreement with those obtained in literature.
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 hyperplane-constrained continuation method for near singularity in coupled nonlinear Schrodinger equations
(2010-05-01)
Kuo, Yueh-Cheng
;
Lin, Wen-Wei
;
Shieh, Shih-Feng
;
Wang, Weichung
;
應用數學系
The continuation method is a useful numerical tool for solving differential equations to obtain multiform solutions and allow bifurcation analysis. However, when a standard continuation method is used to solve a type of time-independent m-coupled nonlinear Schrodinger (NLS) equations that can be used to model nonlinear optics, nearly singular systems arise in the computations of prediction and correction search directions and detections of bifurcations. To overcome the stability and efficiency problems that exist in standard continuation methods, we propose a new hyperplane-constrained continuation method by adding additional constraints to prevent the singularities while tracking the solution curves. Aimed at the 3-coupled DNLS equations, we conduct theoretical analysis to the solutions and bifurcations on the primal stalk solution curve. The proposed algorithms have been implemented successfully to demonstrate numerical solution profiles, energies, and bifurcation diagrams in various settings. (C) 2010 IMACS. Published by Elsevier B.V. All rights reserved.
A minimal energy tracking method for non-radially symmetric solutions of coupled nonlinear Schrodinger equations
(2009-11-01)
Kuo, Yueh-Cheng
;
Lin, Wen-Wei
;
Shieh, Shih-Feng
;
Wang, Weichung
;
應用數學系
We aim at developing methods to track minimal energy solutions of time-independent m-component coupled discrete nonlinear Schrodinger (DNLS) equations. We first propose a method to find energy minimizers of the 1-component DNLS equation and use it as the initial point of the m-component DNLS equations in a continuation scheme. We then show that the change of local optimality occurs only at the bifurcation points. The fact leads to a minimal energy tracking method that guides the choice of bifurcation branch corresponding to the minimal energy solution curve. By combining all these techniques with a parameter-switching scheme, we successfully compute a non-radially symmetric energy minimizer that can not be computed by existing numerical schemes straightforwardly. (C) 2009 Elsevier Inc. All rights reserved.
A modified Newton iteration for finding nonnegative Z-eigenpairs of a nonnegative tensor
(2019-02-01)
Guo, Chun-Hua
;
Lin, Wen-Wei
;
Liu, Ching-Sung
;
應用數學系
;
Department of Applied Mathematics
We propose a modified Newton iteration for finding some nonnegative Z-eigenpairs of a nonnegative tensor. When the tensor is irreducible, all nonnegative eigenpairs are known to be positive. We prove local quadratic convergence of the new iteration to any positive eigenpair of a nonnegative tensor, under the usual assumption guaranteeing the local quadratic convergence of the original Newton iteration. A big advantage of the modified Newton iteration is that it seems capable of finding a nonnegative eigenpair starting with any positive unit vector. Special attention is paid to transition probability tensors.
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 NOTE ON GOLDEN MEANS, NONLINEAR MATRIX EQUATIONS AND STRUCTURED DOUBLING ALGORITHMS
(2010-06-01)
Chiang, Chun-Yueh
;
Chu, Eric King-Wah
;
Lin, Wen-Wei
;
應用數學系
;
Department of Applied Mathematics
Several beautiful formulae for the solutions of some nonlinear matrix equations were proposed by Yongdo Lim in 2007, in terms of the matrix golden means. Numerically, these formulae will not be applicable when some matrices involved are ill-conditioned. In this note, we propose to partially fill in this gap of applicability with the structured doubling algorithm, under some favourable conditions. We also discuss how some pre-processing or scaling procedures can be applied to the matrix equations, to improve their condition. More generally, we also explore the possibility of computing the matrix golden mean using structured doubling algorithms. Some numerical examples will be presented for illustrative purposes.
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 Novel Stretch Energy Minimization Algorithm for Equiareal Parameterizations
(2019-03-01)
Yueh, Mei-Heng
;
Lin, Wen-Wei
;
Wu, Chin-Tien
;
Yau, Shing-Tung
;
應用數學系
Surface parameterizations have been widely applied to computer graphics and digital geometry processing. In this paper, we propose a novel stretch energy minimization (SEM) algorithm for the computation of equiareal parameterizations of simply connected open surfaces with very small area distortions and highly improved computational efficiencies. In addition, the existence of nontrivial limit points of the SEM algorithm is guaranteed under some mild assumptions of the mesh quality. Numerical experiments indicate that the accuracy, effectiveness, and robustness of the proposed SEM algorithm outperform the other state-of-the-art algorithms. Applications of the SEM on surface remeshing, registration and morphing for simply connected open surfaces are demonstrated thereafter. Thanks to the SEM algorithm, the computation for these applications can be carried out efficiently and reliably.
A Novel Symmetric Skew-Hamiltonian Isotropic Lanczos Algorithm for Spectral Conformal Parameterizations
(2014-12-01)
Huang, Wei-Qiang
;
Gu, Xianfeng David
;
Lin, Wen-Wei
;
Yau, Shing-Tung
;
應用數學系
In the past decades, many methods for computing conformal mesh parameterizations have been developed in response to demand of numerous applications in the field of geometry processing. Spectral conformal parameterization (SCP) (Mullen et al. in Proceedings of the symposium on geometry processing, SGP \'08. Eurographics Association, Aire-la-Ville, Switzerland, pp 1487-1494, 2008) is one of these methods used to compute a quality conformal parameterization based on the spectral techniques. SCP focuses on a generalized eigenvalue problem (GEP) whose eigenvector(s) associated with the smallest positive eigenvalue(s) provide the conformal parameterization result. This paper is devoted to studying a novel eigensolver for this GEP. Based on structures of the matrix pair , we show that this GEP can be transformed into a small-scale compressed and deflated standard eigenvalue problem with a symmetric positive definite skew-Hamiltonian operator. We then propose a symmetric skew-Hamiltonian isotropic Lanczos algorithm (HILA) to solve the reduced problem. Numerical experiments show that our compressed deflating technique can exclude the impact of convergence from the kernel of and transform the original problem to a more robust system. The novel HILA method can effectively avoid the disturbance of duplicate eigenvalues. As a result, based on the spectral model of SCP, our numerical eigensolver can compute the conformal parameterization accurately and efficiently.
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 positivity preserving inexact Noda iteration for computing the smallest eigenpair of a large irreducible M-matrix
(2015-08-01)
Jia, Zhongxiao
;
Lin, Wen-Wei
;
Liu, Ching-Sung
;
應用數學系
;
Department of Applied Mathematics
In this paper, based on the Noda iteration, we present inexact Noda iterations (INI), to find the smallest eigenvalue and the associated positive eigenvector of a large irreducible nonsingular -matrix. The positivity of approximations is critical in applications, and if the approximations lose the positivity then they may be meaningless and could not be interpreted. We propose two different inner tolerance strategies for solving the inner linear systems involved, and prove that the convergence of resulting INI algorithms is globally linear and superlinear with the convergence order , respectively. The proposed INI algorithms are structure preserving and maintains the positivity of approximate eigenvectors. We also revisit the exact Noda iteration and establish a new quadratic convergence result. All the above is first done for the problem of computing the Perron root and the positive Perron vector of an irreducible nonnegative matrix and is then adapted to computing the smallest eigenpair of the irreducible nonsingular -matrix. Numerical examples illustrate that the proposed INI algorithms are practical, and they always preserve the positivity of approximate eigenvectors. We compare them with the Jacobi-Davidson method, the implicitly restarted Arnoldi method and the explicitly restarted Krylov-Schur method, all of which cannot guarantee the positivity of approximate eigenvectors, and illustrate that the overall efficiency of the INI algorithms is competitive with and can be considerably higher than the latter three methods.
A POSITIVITY PRESERVING INVERSE ITERATION FOR FINDING THE PERRON PAIR OF AN IRREDUCIBLE NONNEGATIVE THIRD ORDER TENSOR
(2016-01-01)
Liu, Ching-Sung
;
Guo, Chun-Hua
;
Lin, Wen-Wei
;
應用數學系
;
Department of Applied Mathematics
We propose an inverse iterative method for computing the Perron pair of an irreducible nonnegative third order tensor. The method involves the selection of a parameter theta(k) in the kth iteration. For every positive starting vector, the method converges quadratically and is positivity preserving in the sense that the vectors approximating the Perron vector are strictly positive in each iteration. It is also shown that theta(k) - 1 near convergence. The computational work for each iteration of the proposed method is less than four times (three times if the tensor is symmetric in modes two and three, and twice if we also take the parameter to be 1 directly) that for each iteration of the Ng-Qi-Zhou algorithm, which is linearly convergent for essentially positive tensors.
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.
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 structure preserving flow for computing Hamiltonian matrix exponential
(2019-11-01)
Kuo, Yueh-Cheng
;
Lin, Wen-Wei
;
Shieh, Shih-Feng
;
應用數學系
;
Department of Applied Mathematics
This article focuses on computing Hamiltonian matrix exponential. Given a Hamiltonian matrix H, it is well-known that the matrix exponential e(H) is a symplectic matrix and its eigenvalues form reciprocal (lambda, 1/(lambda) over bar). It is important to take care of the symplectic structure for computing e(H). Based on the structure-preserving flow proposed by Kuo et al. (SIAM J Matrix Anal Appl 37:976-1001, 2016), we develop a numerical method for computing the symplectic matrix pair (M, L) which represents e(H).
A structure-preserving doubling algorithm for quadratic eigenvalue problems arising from time-delay systems
(2010-02-15)
Li, Tie-Xiang
;
Chu, Eric King-wah
;
Lin, Wen-Wei
;
應用數學系
;
Department of Applied Mathematics
We propose a structure-preserving doubling algorithm for a quadratic eigenvalue problem arising from the stability analysis of time-delay systems. We are particularly interested in the eigenvalues oil the unit circle, which are difficult to estimate. The convergence and backward error of the algorithm are analyzed and three numerical examples are presented. Our experience shows that Our algorithm is efficient in comparison to the few existing approaches for small to medium size problems. (C) 2009 Elsevier B.V. All rights reserved.