Department of Mathematics & Statistics
http://hdl.handle.net/10294/339
Wed, 25 Feb 2015 07:36:30 GMT2015-02-25T07:36:30ZA note on the fixed-point iteration for the matrix equations $X\pm A^*X^{-1}A=I$
http://hdl.handle.net/10294/5271
A note on the fixed-point iteration for the matrix equations $X\pm A^*X^{-1}A=I$
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.
Tue, 01 Jan 2008 00:00:00 GMThttp://hdl.handle.net/10294/52712008-01-01T00:00:00ZDetecting and solving hyperbolic quadratic eigenvalue problems
http://hdl.handle.net/10294/5270
Detecting and solving hyperbolic quadratic eigenvalue problems
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.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/10294/52702009-01-01T00:00:00ZConvergence Analysis of the Doubling Algorithm for Several Nonlinear Matrix Equations in the Critical Case
http://hdl.handle.net/10294/5269
Convergence Analysis of the Doubling Algorithm for Several Nonlinear Matrix Equations in the Critical Case
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.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/10294/52692009-01-01T00:00:00ZAn Improved Arc Algorithm for Detecting Definite Hermitian Pairs
http://hdl.handle.net/10294/5268
An Improved Arc Algorithm for Detecting Definite Hermitian Pairs
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.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/10294/52682009-01-01T00:00:00Z