An Improved Arc Algorithm for Detecting Definite Hermitian Pairs
An Improved Arc Algorithm for Detecting Definite Hermitian Pairs
复制标题
DOI：
10.1137/08074218x
复制
发表时间：
2009-08
期刊：
影响因子：
--
通讯作者：
Chun-Hua Guo;N. Higham;F. Tisseur
中科院分区：
文献类型：
--
作者：
Chun-Hua Guo;N. Higham;F. Tisseur
Crawford和Moon的一个25年前的算法试图通过探索函数f（x）= x^*（A+ i B）x /（A，B）的范围来确定给定的Hermitian矩阵对$（A，B）$是否是确定的。|x^*（A+iB）x| $，它是单位圆的子集。我们重新审视的算法，并表明，适当的修改和仔细注意执行细节，它提供了一个可靠和有效的手段测试的明确性。一个更清晰的推导的基本算法，强调弧扩展的观点，并没有假设的明确性对。证明了算法对任意$（A，B$）（定值或非定值）的收敛性。结果表明，适当处理的三个细节的算法是至关重要的效率和可靠性：如何计算的弧的中点，是否允许收缩的弧，以及如何计算的负曲率的方向。对于后者，几个变种的Cholesky因式分解与完整的枢轴进行了探讨和枢轴证明的好处。我们改进算法的总成本通常只是几个Cholesky因子分解。该算法有三个应用：检验Hermitian二次矩阵多项式的双曲性，构造鞍点形式的稀疏线性方程组的共轭梯度法，以及通过一个拟凸单变量极小化问题计算方程对$（A，B）$的Crawford数.
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. Three applications of the algorithm are described: 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.