计算n阶Hermitian矩阵最大特征值及对应特征向量的时间复杂度是多少

问题描述 #

对称方阵全特征分解的时间复杂度为O(n³)，如果仅需要计算n阶Hermitian方阵的最大特征值及对应特征向量，时间复杂度是多少？目前的实现方案会先计算所有特征值再排序筛选，存在性能冗余，需要更优的解决方法。

复杂度结论 #

仅求解单个最大特征对的复杂度确实远低于O(n³)，具体数值和所用算法相关：

• 基础幂迭代法：稠密矩阵下单次迭代的矩阵向量乘法复杂度为O(n²)，迭代次数通常为和矩阵规模无关的小常数（常规精度需求下仅需几十次迭代），整体复杂度为*O(n²)*量级。
• Lanczos算法：针对Hermitian矩阵优化的Krylov子空间迭代方法，收敛速度更快，稠密矩阵下整体复杂度仍为O(n²)量级；如果是稀疏Hermitian矩阵，矩阵向量乘法复杂度可降到和非零元数量同阶，多数场景下为O(n)，整体复杂度可低至线性量级。

优化实现 #

你当前用eig做全特征分解再筛选的方式确实存在大量冗余计算，矩阵规模越大性能浪费越严重。Matlab内置的eigs函数专门用于求解指定数量的特征对，内部默认用迭代算法实现，不需要做全特征分解，非常适合你的需求，优化后的代码如下：

% 构造3阶随机Hermitian矩阵
A = 2.*rand(3,3) - ones(3,3) + 1i*(2.*rand(3,3) - ones(3,3));
H = A + A';
% 直接求解最大的1个实特征值及对应特征向量，'la'代表取最大实特征值
[v, e] = eigs(H, 1, 'la');
% 直接输出结果，无需额外排序
e
v

内容的提问来源于stack exchange，提问作者Lee