Вычисление характеристического многочлена вещественной разреженной матрицы

Учитывая общую разреженную матрицу $A \in \mathbb{R}^{n\times n}$с m << n (поправка:$m \ll n^2$ненулевые элементы (обычно $m \in {\cal O}(n)$). $A$ является общим в том смысле, что не имеет специфических свойств (например, положительной определенности), и не предполагается никакой структуры (например, полосатости).

Каковы некоторые из хороших численных методов для вычисления либо характеристического полинома, либо минимального полинома$A$?

Если $O(n^3)$сложность не является пробкой, тогда вы можете взглянуть на метод Данилевского. Он довольно хорошо известен в русской литературе по числовой линейной алгебре, но на английском языке не так много информации. Вы можете начать с этой ссылки .

Идея довольно проста: матрица постепенно сводится к нормальной форме Фробениуса с помощью «подобного элиминации» преобразования подобия. Если вы не найдете информацию, я могу сделать алгоритм более сложным.

Вы можете использовать численный метод, такой как QR Factorization или Power Method и его действительные значения (обратная мощность и т. Д.), Чтобы вычислить собственные значения вашей общей матрицы. После этого вы можете вычислить свой характеристический полином с помощью факторизации следующим образом: (λ-λ1) (λ-λ2) ... (λ-λn) = 0, где λi - вычисленные собственные значения. Вот краткая презентация о силе и методах QR:

QR-Power

Кстати: вы хотели сказать, что у вас есть $m \ll O(n^2)$записи? Если действительно $m \ll O(n)$ тогда большинство строк и столбцов будут полностью пустыми, и вполне вероятно, что характеристический полином на самом деле не имеет степени $n$ но степени $O(m)$,