Chun-Hua Guo

Permanent URI for this collection

https://hdl.handle.net/10294/5255

Office: CW 307.10
E-mail: Chun-Hua.Guo@uregina.ca
Phone: 306-585-4423
Website: http://uregina.ca/~chguo/

Current Classes
Math 103 (Calculus for Social Science & Management)

Research Interests
Matrix analysis, scientific computing, applications

Browse

Now showing 1 - 16 of 16

Open Access
A note on the fixed-point iteration for the matrix equations $X\pm A^*X^{-1}A=I$
(Elsevier, 2008) Fital, Sandra; Guo, Chun-Hua
The fixed-point iteration is a simple method for finding the maximal Hermitian positive definite solutions of the matrix equations $X\pm A^*X^{-1}A=I$ (the plus/minus equations). The convergence of this method may be very slow if the initial matrix is not chosen carefully. A strategy for choosing better initial matrices has been recently proposed by Ivanov, Hasanov and Uhlig. They proved that this strategy can improve the convergence in general and observed from numerical experiments that dramatic improvement happens for the plus equation with some matrices $A$. It turns out that the matrices $A$ are normal for those examples. In this note we prove a result that explains the dramatic improvement in convergence for normal (and thus nearly normal) matrices for the plus equation. A similar result is also proved for the minus equation.
Open Access
Detecting and solving hyperbolic quadratic eigenvalue problems
(SIAM, 2009) Guo, Chun-Hua; Higham, Nicholas J.; Tisseur, Francoise
Hyperbolic quadratic matrix polynomials $Q(\lambda) = \lambda^2 A + \lambda B + C$ are an important class of Hermitian matrix polynomials with real eigenvalues, among which the overdamped quadratics are those with nonpositive eigenvalues. Neither the definition of overdamped nor any of the standard characterizations provides an efficient way to test if a given $Q$ has this property. We show that a quadratically convergent matrix iteration based on cyclic reduction, previously studied by Guo and Lancaster, provides necessary and sufficient conditions for $Q$ to be overdamped. For weakly overdamped $Q$ the iteration is shown to be generically linearly convergent with constant at worst 1/2, which implies that the convergence of the iteration is reasonably fast in almost all cases of practical interest. We show that the matrix iteration can be implemented in such a way that when overdamping is detected a scalar $\mu < 0$ is provided that lies in the gap between the $n$ largest and $n$ smallest eigenvalues of the $n \times n$ quadratic eigenvalue problem (QEP) $Q(\lambda)x = 0$. Once such a $\mu$ is known, the QEP can be solved by linearizing to a definite pencil that can be reduced, using already available Cholesky factorizations, to a standard Hermitian eigenproblem. By incorporating an initial preprocessing stage that shifts a hyperbolic $Q$ so that it is overdamped, we obtain an efficient algorithm that identifies and solves a hyperbolic or overdamped QEP maintaining symmetry throughout and guaranteeing real computed eigenvalues.
Open Access
Convergence Analysis of the Doubling Algorithm for Several Nonlinear Matrix Equations in the Critical Case
(SIAM, 2009) Chiang, Chun-Yueh; Chu, Eric King-Wah; Guo, Chun-Hua; Huang, Tsung-Ming; Lin, Wen-Wei; Xu, Shu-Fang
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.
Open Access
An Improved Arc Algorithm for Detecting Definite Hermitian Pairs
(SIAM, 2009) Guo, Chun-Hua; Higham, Nicholas J.; Tisseur, Francoise
A 25-year old and somewhat neglected algorithm of Crawford and Moon attempts to determine whether a given Hermitian matrix pair $(A,B)$ is definite by exploring the range of the function $f(x) = x^*(A + iB)x/|x^*(A + iB)x|$, which is a subset of the unit circle. We revisit the algorithm and show that with suitable modifications and careful attention to implementation details it provides a reliable and efficient means of testing definiteness. A clearer derivation of the basic algorithm is given that emphasizes an arc expansion viewpoint and makes no assumptions about the definiteness of the pair. Convergence of the algorithm is proved for all $(A,B)$, definite or not. It is shown that proper handling of three details of the algorithm is crucial to the efficiency and reliability: how the midpoint of an arc is computed, whether shrinkage of an arc is permitted, and how directions of negative curvature are computed. For the latter, several variants of Cholesky factorization with complete pivoting are explored and the benefits of pivoting demonstrated. The overall cost of our improved algorithm is typically just a few Cholesky factorizations. Applications of the algorithm are described to testing the hyperbolicity of a Hermitian quadratic matrix polynomial, constructing conjugate gradient methods for sparse linear systems in saddle point form, and computing the Crawford number of the pair $(A,B)$ via a quasiconvex univariate minimization problem.
Open Access
On Newton's method and Halley's method for the principal $p$th root of a matrix
(Elsevier, 2010) Guo, Chun-Hua
If $A$ is a matrix with no negative real eigenvalues and all zero eigenvalues of $A$ are semisimple, the principal $p$th root of $A$ can be computed by Newton's method or Halley's method, with a preprocessing procedure if necessary. We prove a new convergence result for Newton's method, and discover an interesting property of Newton's method and Halley's method in terms of series expansions. We explain how the convergence of Newton's method and Halley's method can be improved when the eigenvalues of $A$ are known or when $A$ is a singular matrix. We also prove new results on $p$th roots of $M$-matrices and $H$-matrices, and consider the application of Newton's method and Halley's method to find the principal $p$th roots of these special matrices.
Open Access
Convergence rates of some iterative methods for nonsymmetric algebraic Riccati equations arising in transport theory
(Elsevier, 2010) Guo, Chun-Hua; Lin, Wen-Wei
We determine and compare the convergence rates of various fixed-point iterations for finding the minimal positive solution of a class of nonsymmetric algebraic Riccati equations arising in transport theory.
Open Access
The matrix equation $X+A^TX^{-1}A=Q$ and its application in nano research
(SIAM, 2010) Guo, Chun-Hua; Lin, Wen-Wei
The matrix equation $X+A^TX^{-1}A=Q$ has been studied extensively when $A$ and $Q$ are real square matrices and $Q$ is symmetric positive definite. The equation has positive definite solutions under suitable conditions, and in that case the solution of interest is the maximal positive definite solution. The same matrix equation plays an important role in Green's function calculations in nano research, but the matrix $Q$ there is usually indefinite (so the matrix equation has no positive definite solutions) and one is interested in the case where the matrix equation has no positive definite solutions even when $Q$ is positive definite. The solution of interest in this nano application is a special weakly stabilizing complex symmetric solution. In this paper we show how a doubling algorithm can be used to find good approximations to the desired solution efficiently and reliably.
Open Access
Solving a structured quadratic eigenvalue problem by a structure-preserving doubling algorithm
(SIAM, 2010) Guo, Chun-Hua; Lin, Wen-Wei
In studying the vibration of fast trains, we encounter a palindromic quadratic eigenvalue problem (QEP) $(\lambda^2 A^T + \lambda Q + A)z = 0$, where $A, Q \in \mathbb{C}^{n \times n}$ and $Q^T = Q$. Moreover, the matrix $Q$ is block tridiagonal and block Toeplitz, and the matrix $A$ has only one nonzero block in the upper-right corner. So most of the eigenvalues of the QEP are zero or infinity. In a linearization approach, one typically starts with deflating these known eigenvalues, for the sake of efficiency. However, this initial deflation process involves the inverses of two potentially ill-conditioned matrices. As a result, large error might be introduced into the data for the reduced problem. In this paper we propose using the solvent approach directly on the original QEP, without any deflation process. We apply a structure-preserving doubling algorithm to compute the stabilizing solution of the matrix equation $X+A^TX^{-1}A=Q$, whose existence is guaranteed by a result on the Wiener--Hopf factorization of rational matrix functions associated with semi-infinite block Toeplitz matrices and a generalization of Bendixson's theorem to bounded linear operators on Hilbert spaces. The doubling algorithm is shown to be well defined and quadratically convergent. The complexity of the doubling algorithm is drastically reduced by using the Sherman--Morrison--Woodbury formula and the special structures of the problem. Once the stabilizing solution is obtained, all nonzero finite eigenvalues of the QEP can be found efficiently and with the automatic reciprocal relationship, while the known eigenvalues at zero or infinity remain intact.
Open Access
Complex symmetric stabilizing solution of the matrix equation $X+A^{T}X^{-1}A=Q$
(Elsevier, 2011) Guo, Chun-Hua; Kuo, Yueh-Cheng; Lin, Wen-Wei
We study the matrix equation $X+A^{T}X^{-1}A=Q$, where $A$ is a complex square matrix and $Q$ is complex symmetric. Special cases of this equation appear in Green's function calculation in nano research and also in the vibration analysis of fast trains. In those applications, the existence of a unique complex symmetric stabilizing solution has been proved using advanced results on linear operators. The stabilizing solution is the solution of practical interest. In this paper we provide an elementary proof of the existence for the general matrix equation, under an assumption that is satisfied for the two special applications. Moreover, our new approach here reveals that the unique complex symmetric stabilizing solution has a positive definite imaginary part. The unique stabilizing solution can be computed efficiently by the doubling algorithm.
Open Access
On a nonlinear matrix equation arising in nano research
(SIAM, 2012) Guo, Chun-Hua; Kuo, Yueh-Cheng; Lin, Wen-Wei
The matrix equation $X+A^{T}X^{-1}A=Q$ arises in Green's function calculations in nano research, where $A$ is a real square matrix and $Q$ is a real symmetric matrix dependent on a parameter and is usually indefinite. In practice one is mainly interested in those values of the parameter for which the matrix equation has no stabilizing solutions. The solution of interest in this case is a special weakly stabilizing complex symmetric solution $X_*$, which is the limit of the unique stabilizing solution $X_{\eta}$ of the perturbed equation $X+A^{T}X^{-1}A=Q+i\eta I$, as $\eta\to 0^+$. It has been shown that a doubling algorithm can be used to compute $X_{\eta}$ efficiently even for very small values of $\eta$, thus providing good approximations to $X_*$. It has been observed by nano scientists that a modified fixed-point method can sometimes be quite useful, particularly for computing $X_{\eta}$ for many different values of the parameter. We provide a rigorous analysis of this modified fixed-point method and its variant, and of their generalizations. We also show that the imaginary part $X_I$ of the matrix $X_*$ is positive semi-definite and determine the rank of $X_I$ in terms of the number of unimodular eigenvalues of the quadratic pencil $\lambda^2 A^{T}-\lambda Q+A$. Finally we present a new structure-preserving algorithm that is applied directly on the equation $X+A^{T}X^{-1}A=Q$. In doing so, we work with real arithmetic most of the time.
Open Access
Numerical solution of nonlinear matrix equations arising from Green's function calculations in nano research
(Elsevier, 2012) Guo, Chun-Hua; Kuo, Yueh-Cheng; Lin, Wen-Wei
The Green's function approach for treating quantum transport in nano devices requires the solution of nonlinear matrix equations of the form $X+(C^*+{\rm i} \eta D^*)X^{-1}(C+{\rm i} \eta D)=R+{\rm i}\eta P$, where $R$ and $P$ are Hermitian, $P+\lambda D^*+\lambda^{-1} D$ is positive definite for all $\lambda$ on the unit circle, and $\eta \to 0^+$. For each fixed $\eta>0$, we show that the required solution is the unique stabilizing solution $X_{\eta}$. Then $X_*=\lim_{\eta\to 0^+} X_{\eta}$ is a particular weakly stabilizing solution of the matrix equation $X+C^*X^{-1}C=R$. In nano applications, the matrices $R$ and $C$ are dependent on a parameter, which is the system energy $\mathcal E$. In practice one is mainly interested in those values of $\mathcal E$ for which the equation $X+C^*X^{-1}C=R$ has no stabilizing solutions or, equivalently, the quadratic matrix polynomial $P(\lambda)=\lambda^2 C^*-\lambda R+ C$ has eigenvalues on the unit circle. We point out that a doubling algorithm can be used to compute $X_{\eta}$ efficiently even for very small values of $\eta$, thus providing good approximations to $X_*$. We also explain how the solution $X_*$ can be computed directly using subspace methods such as the QZ algorithm by determining which unimodular eigenvalues of $P(\lambda)$ should be included in the computation. In some applications the matrices $C, D, R, P$ have very special sparsity structures. We show how these special structures can be expoited to drastically reduce the complexity of the doubling algorithm for computing $X_{\eta}$.
Open Access
Iterative methods for a linearly perturbed algebraic matrix Riccati equation arising in stochastic control
(Taylor & Francis, 2013) Guo, Chun-Hua
We start with a discussion of coupled algebraic Riccati equations arising in the study of linear-quadratic optimal control problem for Markov jump linear systems. Under suitable assumptions, this system of equations has a unique positive semidefinite solution, which is the solution of practical interest. The coupled equations can be rewritten as a single linearly perturbed matrix Riccati equation with special structures. We study the linearly perturbed Riccati equation in a more general setting and obtain a class of iterative methods from different splittings of a positive operator involved in the Riccati equation. We prove some special properties of the sequences generated by these methods, and determine and compare the convergence rates of these methods. Our results are then applied to the coupled Riccati equations of jump linear systems. We obtain linear convergence of the Lyapunov iteration and the modified Lyapunov iteration, and confirm that the modified Lyapunov iteration indeed has faster convergence than the original Lyapunov iteration.
Open Access
Monotone convergence of Newton-like methods for M-matrix algebraic Riccati equations
(Springer, 2013) Guo, Chun-Hua
For the algebraic Riccati equation whose four coefficient matrices form a nonsingular $M$-matrix or an irreducible singular $M$-matrix $K$, the minimal nonnegative solution can be found by Newton's method and the doubling algorithm. When the two diagonal blocks of the matrix $K$ have both large and small diagonal entries, the doubling algorithm often requires many more iterations than Newton's method. In those cases, Newton's method may be more efficient than the doubling algorithm. This has motivated us to study Newton-like methods that have higher-order convergence and are not much more expensive each iteration. We find that the Chebyshev method of order three and a two-step modified Chebyshev method of order four can be more efficient than Newton's method. For the Riccati equation, these two Newton-like methods are actually special cases of the Newton-Shamanskii method. We show that, starting with zero initial guess or some other suitable initial guess, the sequence generated by the Newton--Shamanskii method converges monotonically to the minimal nonnegative solution. We also explain that the Newton-like methods can be used to great advantage when solving some Riccati equations involving a parameter.
Open Access
On algebraic Riccati equations associated with M-matrices
(Elsevier, 2013) Guo, Chun-Hua
We consider the algebraic Riccati equation for which the four coefficient matrices form an $M$-matrix $K$. When $K$ is a nonsingular $M$-matrix or an irreducible singular $M$-matrix, the Riccati equation is known to have a minimal nonnegative solution and several efficient methods are available to find this solution. In this paper we are mainly interested in the case where $K$ is a reducible singular $M$-matrix. Under a regularity assumption on the $M$-matrix $K$, we show that the Riccati equation still has a minimal nonnegative solution. We also study the properties of this particular solution and explain how the solution can be found by existing methods.
Open Access
Performance enhancement of doubling algorithms for a class of complex nonsymmetric algebraic Riccati equations
(Oxford University Press, 2014) Guo, Chun-Hua; Liu, Changli; Xue, Jungong
A new class of complex nonsymmetric algebraic Riccati equations has been studied by Liu and Xue (SIAM J. Matrix Anal. Appl., 33 (2012), 569-596), which is related to the M-matrix algebraic Riccati equations. Doubling algorithms, with properly chosen parameters, are used there for equations in this new class. It is pointed out that the number of iterations for the doubling algorithms may be relatively large in some situations. In this paper, we show that the performance of the doubling algorithms can often be improved significantly if a proper preprocessing procedure is used on the given Riccati equation. There are some difficult cases for which the preprocessing procedure does not help much by itself. We then propose new strategies for choosing parameters for doubling algorithms after using the preprocessing procedure. Numerical experiments show that our preprocessing procedure and the new parameter strategies are very effective.
Open Access
A convergence result for matrix Riccati differential equations associated with M-matrices
(2014-04-22) Guo, Chun-Hua; Yu, Bo
The initial value problem for a matrix Riccati differential equation associated with an $M$-matrix is known to have a global solution $X(t)$ on $[0, \infty)$ when $X(0)$ takes values from a suitable set of nonnegative matrices. It is also known, except for the critical case, that as $t$ goes to infinity $X(t)$ converges to the minimal nonnegative solution of the corresponding algebraic Riccati equation. In this paper we present a new approach for proving the convergence, which is based on the doubling procedure and is also valid for the critical case. The approach also provides a way for solving the initial value problem and a new doubling algorithm for computing the minimal nonnegative solution of the algebraic Riccati equation.

Browse

Recent Submissions