×

An improved arc algorithm for detecting definite Hermitian pairs. (English) Zbl 1202.65054

A pair \((A,B)\) of Hermitian matrices \(A, B \in \mathbb{C}^{n \times n}\) is said to be a definite pair if \(x^{\ast} (A + i B) x \neq 0\) for all \(x \in \mathbb{C}^n\), otherwise it is indefinite. The question is, how one can decide whether a given Hermitian matrix pair \((A,B)\) is definite.
The values of the function \(f(x) = x^{\ast} (A + i B) x / |x^{\ast} (A + i B) x|\), \(x \neq 0\), form an arc \(\{z = \alpha a + \beta b\), \(|z| = 1\), \(\alpha, \beta \geq 0 \}\) of the unit circle in the complex plane with the central angle \(\Theta (a,b)\). For \((a + b)/|a + b| = \cos(t) + i\sin(t)\) the matrix \(B(t) = A\cos(t) + B\sin(t)\) is positive definite. That is a result of Y.-H. Au-Yeung [Proc. Am. Soc. 20, 545–548 (1969; Zbl 0186.05903)] and G. W. Stewart [Linear Algebra Appl. 23, 69–85 (1979; Zbl 0407.15012)].
Required is an algorithm that finds for a given Hermitian pair \((A,B)\) a real number \(t\) such that \(B(t)\) is positive definite or shows that no such \(t\) exists. C. R. Crawford and Y. S. Moon [Linear Algebra Appl. 51, 37–48 (1983; Zbl 0516.15021)] developed an algorithm for this problem, which is now revisited, improved and new derived in the present paper.
In contrast to the original algorithm the authors makes no assumptions about the definiteness of the pair. Their procedure is better suited to the floating point arithmetic. The convergence of the algorithm is proved for all pairs \((A,B)\), definite or not. A backward error analysis is given. The computation of the midpoints of an arc, of the angles, of the directions of negative curvature, and the initializing, termination, and reliability of the algorithm are improved. It is shown that the Cholesky decomposition with complete pivoting has advantages. These and other modifications improve the Crawford-Moon algorithm, in general halving the number of iterations. The computational costs are the costs for a few Cholesky factorizations. The modifications are described in detail.
Definite pairs arise in generalized eigenvalue problems. In this paper the modified algorithm is validated testing the hyperbolicity of Hermitian quadratics, treating a linear system in saddle point form, and computing the Crawford number of an pair \((A,B)\).

MSC:

65F30 Other matrix algorithms (MSC2010)
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
15B57 Hermitian, skew-Hermitian, and related matrices
PDFBibTeX XMLCite
Full Text: DOI