利用向量拟合可以在电路系统的信号完整性检验等方面建立出非常精确的模型,然而,为了确保计算出的该模型是无源的,必须进行完整地无源性检验.通过Hamilton矩阵的纯虚特征值的存在性,就可以判断出该系统是否有源.然而,由于这个矩阵的维数相当高,可以达到百万阶,如何求解这样一个大型矩阵的特征值,在时间和空间上都是一个很大的考验,因为传统的特征值求解方法时间复杂度为O（n,3）,空间复杂度为O（n2）. 文章[26]中给出了一种时间复杂度O（c·d·n）,空间复杂O（n）的算法,其中c是与具体的矩阵特征值分布有关的常数,d为矩阵虚特征值的个数.其实,我们关心的只是那些虚特征值.由于实际电路本身是无源的,该电路的高精度近似,也即通过向量拟合得到的模拟模型,虽然有可能不是完全无源,但无源性的破坏点往往是很少的,也就是说d《m这一点在实际例子中也得到了验证.因此,把计算的精力都集中在这特少数的虚特征值求解上,以大大地节省时间,避免浪费.但是,正像作者在[26]中指出的那样,该算法的时间复杂度是与矩阵的特征值分布有关,因此在有些情况下,由于常数c变得非常大,该方法的效率就受到了很大的影响. 事实上,当Hamilton矩阵的特征值在虚轴附近密集分布时,这个常数c就会变得非常大.因此,如果能够使得那些虚轴附近的特征值远离虚轴,就能期望该算法的效率可以得到提高.本文通过分式线性变换得到一个中间矩阵,然后对该矩阵进行操作,实现了使得原先在虚轴附近紧密分布的特征值远离虚轴的效果. 首先我们引入如下分式线性变换： 命题0.1如果1不是矩阵H的特征值,则应通过映射C←（H+I）/（H-I）,矩阵H的虚特征值一一地对应着矩阵C在单位圆上的特征值. 文中给出了特殊处理,使得该命题可以应该用于我们的Hamilton矩阵.实际上,只要我们先求解出H的按模最大特征值λ,令H←1/（|λ|+ε）H,其中ε为正数,则矩阵H的所有特征值的模都小于1,也即不可能含有特征值1. 由于变换后的矩阵C在单位圆上的特征值就对应着Hamilton矩阵H的虚特征值,我们可以转而求C在单位圆上的特征值. 此时,矩阵H在虚轴附近稠密分布的特征值就稠密分布在C的单位圆内外了.下面我们指出,通过矩阵乘幂可以使得C在单位圆内外两侧的特征值远离单位圆. 命题0.2当q→∞时,矩阵Cq的特征值只分布在单位圆|C|=1、原点及无穷远点上. 这个命题说明,当q充分大时,求解矩阵Cq在单位圆|C|=1上的特征值,将不再受单位圆附近特征值的干扰.我们可以先求解Cq在单位圆|C|=1上的特征值,然后利用这些特征值可以恢复出H的虚特征值.当然,在实际计算中,不可能要求q无限大,我们通过下面的命题给出q的具体取值. 命题0.3计算H的完全覆盖邻域的时间复杂度与计算Cq的完全覆盖邻域的时间复杂度与之比为： 这个比例跟随q的增大而增大,最高可达7倍.当q=8时,δ≈10.所以,q=8是个不错的选择,利用C8可以达到十倍的加速. 还需指出的是,矩阵的平衡化对于降低计算机浮点舍入误差对非对称矩阵特征值求解的影响时非常大的[37, 38],一个稳定的特征值求解系统,必须首先对输入矩阵进行平衡化.然而,一般的平衡化方法时间复杂度为O（n2）,显然,对于一个时间复杂度为O（c·d·n）的算法,这样的的预处理速度是不能接受的.本文首先给出了一个命题,基于此命题,我们设计出了时间复杂度为O（n）的快速平衡化方法. 至此,我们得到了完整的加速算法: 算法0.1求解Hamilton矩阵虚特征值算法的加速： Input:Hamilton矩阵H Output:矩阵H的虚特征值 stepl：对Hamilton矩阵H进行快速平衡化. step2：求解H的按模最大特征值λ,令H←1/（|λ|+ε）H,其中ε为正数. step3：构造C←（H+I）/（H-I）, step4:利用特征邻域方法求解C8的在单位圆上的特征值{γm}. step5：从C8的特征值{γm}恢复矩阵H的特征值{入m}.则{（|λ|十ε）·入m}就是待求的Hamilton矩阵H的所有虚特征值.