Computing All or Some Eigenvalues of Symmetric H-Matrices
Computing All or Some Eigenvalues of Symmetric H-Matrices
复制标题
计算对称 H 矩阵的全部或部分特征值
DOI：
10.1137/100815323
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
T. Mach
中科院分区：
文献类型：
--
作者：
P. Benner;T. Mach
我们使用二分法[B]。Parlett，对称特征值问题，Prentice-Hall, Englewood Cliffs， NJ, 1980, p. 51]计算对称$\mathcal{H}_{\ell}$ -矩阵的特征值$M$。通过$M-\mu I$的LDL $^T$因子分解计算$M-\mu I$的负特征值的数目。对于密集矩阵，LDL $^T$分解成本太高，通常无法产生有效的特征值算法，但对于$\mathcal{H}_{\ell}$ -矩阵则不然。在$\mathcal{H}_{\ell}$ -矩阵的特殊结构中，存在一个具有线性-多对数复杂性的LDL - $^T$分解。二分法只需要与矩阵大小无关的多次迭代就可以找到达到所需精度的特征值，从而可以在线性多对数时间内找到特征值。对于所有$n$特征值，需要$\mathcal{O}(n^{2}(\log n )^{4}\log( \Vert {M}\Vert_{2}/\epsilon_{\text{ev}}))$ flops以$\epsilon_{\text{ev}}$的精度计算所有特征值。也可以只计算特定区间或$j$最小区间内的特征值。数值实验证明了该算法的有效性，特别是在需要一些内部特征值的情况下。（本文附有更正后的PDF版本。）
We use a bisection method [B. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, NJ, 1980, p. 51] to compute the eigenvalues of a symmetric $\mathcal{H}_{\ell}$-matrix $M$. The number of negative eigenvalues of $M-\mu I$ is computed via the LDL$^T$ factorization of $M-\mu I$. For dense matrices, the LDL$^T$ factorization is too expensive to yield an efficient eigenvalue algorithm in general, but not so for $\mathcal{H}_{\ell}$-matrices. In the special structure of $\mathcal{H}_{\ell}$-matrices there is an LDL$^T$ factorization with linear-polylogarithmic complexity. The bisection method requires only matrix-size independent many iterations to find an eigenvalue up to the desired accuracy, so that an eigenvalue can be found in linear-polylogarithmic time. For all $n$ eigenvalues, $\mathcal{O}(n^{2}(\log n )^{4}\log( \Vert {M}\Vert_{2}/\epsilon_{\text{ev}}))$ flops are needed to compute all eigenvalues with an accuracy $\epsilon_{\text{ev}}$. It is also possible to compute only eigenvalues in a specific interval or the $j$th smallest one. Numerical experiments demonstrate the efficiency of the algorithm, in particular for the case when some interior eigenvalues are required. (A corrected PDF is attached to this article.)