Browsing by Author "Li, Ren-Cang"

Now showing 1 - 5 of 5

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 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 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.
Backward perturbation analysis and residual-based error bounds for the linear response eigenvalue problem
(2015-09-01)
Zhang, Lei-Hong
;
Lin, Wen-Wei
;
Li, Ren-Cang
;
應用數學系
;
Department of Applied Mathematics
The numerical solution of a large scale linear response eigenvalue problem is often accomplished by computing a pair of deflating subspaces associated with the interesting part of the spectrum. This paper is concerned with the backward perturbation analysis for a given pair of approximate deflating subspaces or an approximate eigenquadruple. Various optimal backward perturbation bounds are obtained, as well as bounds for approximate eigenvalues computed through the pair of approximate deflating subspaces or approximate eigenquadruple. These results are reminiscent of many existing classical ones for the standard eigenvalue problem.
Structured backward error for palindromic polynomial eigenvalue problems
(2010-07-01)
Li, Ren-Cang
;
Lin, Wen-Wei
;
Wang, Chern-Shuh
;
應用數學系
;
Department of Applied Mathematics
A detailed structured backward error analysis for four kinds of palindromic polynomial eigenvalue problems (PPEP) (Sigma(d)(l=0)A(l)lambda(l)) x = 0, A(d-l) = epsilon A(l)(star) for l = 0, 1, ..., left perpendiculard/2right perpendicular, where star is one of the two actions: transpose and conjugate transpose, and epsilon is an element of {+/- 1}. Each of them has its application background with the case star taking transpose and epsilon = 1 attracting a great deal of attention lately because of its application in the fast train modeling. Computable formulas and bounds for the structured backward errors are obtained. The analysis reveals distinctive features of PPEP from general polynomial eigenvalue problems (PEP) investigated by Tisseur (Linear Algebra Appl 309: 339-361, 2000) and by Liu and Wang (Appl Math Comput 165: 405-417, 2005).