numpy 100 × 100矩阵左特征向量和特征值的确定

kninwzqo  于 2023-06-29  发布在  其他
关注(0)|答案(1)|浏览(165)

我试图确定一个100 × 100矩阵的(真实的)左特征向量和特征值。矩阵T的元素是从0到1的概率。矩阵T的每一行总和为1.0(100%概率)。列的总和不一定是任何特定的值。
scipy和numpy库返回复数-这显然是由于无法将特征多项式求解为真实的或算法被优化来做到这一点。我转向sympy库,它也返回复数作为解决方案。
使用sympy在这里描述是有意义的:Is it possible somehow to find complex eigenvalues using SymPy?
我的理解是,这将迫使答案为真实的。
下面是我的代码:

import numpy as np
from sympy import *

T = np.loadtxt('rep10_T_ij.dat', delimiter=' ')

T = np.asmatrix(T)
T = Matrix(T)

lam = symbols('\lambda')
char_poly = det(lam * eye(T.rows) - T)
roots_char_poly = solve(char_poly, lam)
display(char_poly)
display(roots(poly(char_poly, domain=CC)))
display([N(r) for r in roots_char_poly])

然而,这并没有在12小时内输出答案,任何数量的硬件都扔在它上面。
我在这里读到:https://github.com/sympy/sympy/issues/7200
100 × 100矩阵是否太贵?我可以在集群上向它扔更多的硬件,但还没能尝试这个。有解决办法吗?

qgzx9mmu

qgzx9mmu1#

在这种情况下,使用SymPy而不是NumPy或SciPy的优势在于,如果您想要精确或符号化地执行计算。确定特征值是精确真实的通常需要精确的算术。精确或符号计算比固定精度浮点要慢得多,所以与使用NumPy或SciPy相比,你应该期待事情会慢很多。如果你的初始矩阵是一个浮点数矩阵,那么它已经是近似的,在这种情况下,使用SymPy很有可能没有好处。
在任何情况下,这里有一些代码可以显示如何使用SymPy更有效地获得矩阵的确切真实的特征值。这通常只在你的原始矩阵有精确的有理数(不是浮点数)时才值得做,但它应该精确地获得真实的特征值:

from sympy import *

def make_matrix(N):
    """Random matrix of rational numbers with all integer eigenvalues"""
    V = randMatrix(N)._rep.to_field()
    eigs = randMatrix(1, N)
    D = diag(*eigs)._rep
    Vinv = V.inv()
    M = V*D*Vinv
    return M.to_Matrix()

def eigenvals(M):
    x = symbols('x')
    p = M._rep.charpoly()
    return Poly(p, x).real_roots()

这使用Berkowicz算法来计算特征多项式,这是操作中最慢的部分(charpoly方法)。这比使用行列式找到特征多项式要有效得多,但对于大型矩阵仍然很慢。对于N x N稠密矩阵,如果底层系数字段具有O(1)算术成本,则以这种方式找到特征多项式大致为O(N**4)。不幸的是,精确有理数没有O(1)的算术成本,所以实际上,当你扩展到更大的矩阵时,复杂度明显比O(N**4)差。
您可以了解不同大小所涉及的时间:

In [80]: M = make_matrix(5)

In [81]: M
Out[81]: 
⎡-23268248970   17481165584  6611878976  21688404260  -332363048 ⎤
⎢─────────────  ───────────  ──────────  ───────────  ───────────⎥
⎢   6173287       6173287     6173287      6173287      6173287  ⎥
⎢                                                                ⎥
⎢-11620321902   8914715596   3291699676  10654796030  -168333588 ⎥
⎢─────────────  ──────────   ──────────  ───────────  ───────────⎥
⎢   6173287      6173287      6173287      6173287      6173287  ⎥
⎢                                                                ⎥
⎢-17978224844   13433529668  5243135950  16686586148  -354021332 ⎥
⎢─────────────  ───────────  ──────────  ───────────  ───────────⎥
⎢   6173287       6173287     6173287      6173287      6173287  ⎥
⎢                                                                ⎥
⎢-10824267464   8003053808   3040726208  10253515930  -120066032 ⎥
⎢─────────────  ──────────   ──────────  ───────────  ───────────⎥
⎢   6173287      6173287      6173287      6173287      6173287  ⎥
⎢                                                                ⎥
⎢-2998114302    2232013094   828083788   2727588566    239697782 ⎥
⎢────────────   ──────────   ─────────   ──────────    ───────── ⎥
⎣  6173287       6173287      6173287     6173287       6173287  ⎦

In [82]: %time eigenvals(M)
CPU times: user 43.8 ms, sys: 4 ms, total: 47.8 ms
Wall time: 46.6 ms
Out[82]: [14, 26, 46, 56, 82]

In [83]: M = make_matrix(10)

In [84]: %time eigenvals(M)
CPU times: user 82.7 ms, sys: 10 µs, total: 82.7 ms
Wall time: 81.8 ms
Out[84]: [8, 18, 27, 39, 58, 67, 85, 95, 96, 98]

In [85]: M = make_matrix(20)

In [86]: %time eigenvals(M)
CPU times: user 652 ms, sys: 2 µs, total: 652 ms
Wall time: 651 ms
Out[86]: [9, 15, 21, 22, 26, 26, 36, 37, 38, 40, 52, 57, 63, 64, 65, 66, 69, 70, 80, 96]

In [87]: M = make_matrix(30)

In [88]: %time eigenvals(M)
CPU times: user 6.1 s, sys: 0 ns, total: 6.1 s
Wall time: 6.1 s
Out[88]: 
[7, 8, 10, 13, 15, 18, 26, 33, 34, 35, 36, 42, 42, 43, 43, 47, 49, 50, 52, 54, 56, 62, 72, 79, 85, 
87, 89, 92, 98, 98]

In [89]: M = make_matrix(40)

In [90]: %time eigenvals(M)
CPU times: user 37.8 s, sys: 12 µs, total: 37.8 s
Wall time: 37.9 s
Out[90]: 
[1, 7, 13, 14, 15, 17, 17, 20, 26, 26, 27, 28, 29, 32, 33, 35, 37, 43, 43, 44, 44, 46, 50, 50, 52, 
52, 53, 55, 58, 64, 67, 70, 71, 72, 79, 83, 83, 88, 88, 99]

因此,已经找到40 x40矩阵的确切整数特征值需要30秒。扩展到100 x100会很慢,但可能是可能的。如果你想这样做,我建议安装gmpy2,因为它可以让SymPy中的精确有理数更快。
最有可能的是,像这样计算精确的特征值并不是你想要做的,你应该使用NumPy/SciPy。如果它们给予的本征值虚部很小,那么你可以丢弃那些,如果你知道本征值应该是真实的。否则,只要初始矩阵仅是近似的(即,浮点数),那么上面所示的那种缓慢的精确计算可能是不值得的。

相关问题