У меня очень большая поглощающая цепь Маркова (масштабируется до размера задачи - от 10 штатов до миллионов), которая очень разрежена (большинство штатов может реагировать только на 4 или 5 других штатов).

Мне нужно рассчитать одну строку фундаментальной матрицы этой цепочки (средняя частота каждого состояния дана для одного исходного состояния).

Обычно я делаю это путем вычисления(I - Q)^(-1), но я не смог найти хорошую библиотеку, в которой реализован обратный алгоритм разреженной матрицы! Я видел несколько работ, большинство из которых P.h.D. уровень работы.

Большинство моих результатов в Google указывают мне на сообщения о том, что нельзя использовать матрицу, обратную при решении линейных (или нелинейных) систем уравнений ... Я не считаю это особенно полезным. Похоже ли вычисление фундаментальной матрицы на решение системы уравнений, и я просто не знаю, как выразить одно в форме другого?

Итак, я задаю два конкретных вопроса:

What's the best way to calculate a row (or all the rows) of the inverse of a sparse matrix?

ИЛИ ЖЕ

What's the best way to calculate a row of the fundamental matrix of a large absorbing Markov chain?

Решение на Python было бы замечательно (так как мой проект все еще является проверкой концепции), но если бы мне пришлось испачкать руки хорошим старым приложением. Fortran или C, это не проблема.

Редактировать: я только что понял, что обратная B матрицы A может быть определена как AB = I, где I - единичная матрица. Это может позволить мне использовать некоторые стандартные разреженные матричные решатели для вычисления обратного ... Я должен убежать, поэтому не стесняйтесь завершать мой ход мыслей, который, как я начинаю думать, может потребовать только действительно элементарной матрицы имущество...