Calcular el polinomio característico de la matriz dispersa real

Dada una matriz dispersa genérica con m << n (corrección: m ≪ n 2 ) elementos distintos de cero (típicamente m ∈ O ( n ) ). A es genérico en el sentido de que no tiene propiedades específicas (por ejemplo, definición positiva), y no se supone ninguna estructura (por ejemplo, bandas).$A \in \mathbb{R}^{n\times n}$$m \ll n^2$$m \in {\cal O}(n)$$A$

¿Cuáles son algunos de los buenos métodos numéricos para calcular el polinomio característico o el polinomio mínimo de ?$A$

Si la complejidad de no es un obstáculo, es posible que desee ver el método Danilevskii. Es bastante conocido en la literatura rusa sobre álgebra lineal numérica, pero no hay mucha información en inglés. Puedes comenzar desde este enlace .$O(n^3)$

La idea es bastante directa: la matriz se reduce gradualmente a la forma normal de Frobenius mediante transformaciones de similitud "de eliminación gaussiana". Si no encuentra la información, puedo hacer que el algoritmo sea más elaborado.

Puede usar un método numérico como Factorización QR o Método de potencia y sus realives (potencia inversa, etc.) para calcular los valores propios de su matriz genérica. Después de eso, puede calcular su polinomio característico por factorización como: (λ-λ1) (λ-λ2) ... (λ-λn) = 0 donde λi son los valores propios calculados. Aquí hay una breve presentación sobre el poder y los métodos QR:

QR-Power

$m \ll O(n^2)$$m \ll O(n)$$n$$O(m)$