Browsing by Author "Huang, Wei-Qiang"

Now showing 1 - 7 of 7

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 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 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.
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.
iSIRA: Integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data
(2019-01-15)
Huang, Wei-Qiang
;
Lin, Wen-Wei
;
Lu, Henry Horng-Shing
;
Yau, Shing-Tung
;
交大名義發表
The eigenvalue problem of a graph Laplacian matrix L arising from a simple, connected and undirected graph has been given more attention due to its extensive applications, such as spectral clustering, community detection, complex network, image processing and so on. The associated matrix L is symmetric, positive semi-definite, and is usually large and sparse. It is often of interest for finding some smallest positive eigenvalues and corresponding eigenvectors. However, the singularity of L makes the classical eigensolvers inefficient since we need to factorize L for the purpose of solving large and sparse linear systems exactly. The next difficulty is that it is usually prohibitive to factorize L generated by real network problems from big data such as social media transactional databases, and sensor systems because there is in general not only local connections. In this paper, we propose a trimming to cure the singularity of L according to its special property: zero row/column sum. This remedy technique leads us to solve a positive definite linear system reduced in one dimension and then recover the result to get a suitable solution of the original system involved in an eigensolver. Besides, we apply a deflating approach to exclude the influence of converged eigenvalues. We show how to apply the idea of trimming to the graph Laplacian eigenvalue problem together with a deflated term and a target shift. Accordingly, based on the inexact residual Arnoldi (Lee, 2007; Lee and Stewart, 2007) method, we propose an integrated eigensolver for this kind of L combining with the implicit remedy of the singularity, an effective deflation for convergent eigenvalues and the shift-invert enhancement. Numerical experiments reveal that the integrated eigensolver outperforms the classical Arnoldi/Lanczos method for computing some smallest positive eigeninformation especially when the LU factorization is not available. (C) 2018 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.