Лучший способ вычислить фундаментальную матрицу поглощающей цепи Маркова?
=========================================================================

У меня очень большая поглощающая цепь Маркова (масштабируется до размера задачи - от 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 - единичная матрица. Это может позволить мне использовать некоторые стандартные разреженные матричные решатели для вычисления обратного ... Я должен убежать, поэтому не стесняйтесь завершать мой ход мыслей, который, как я начинаю думать, может потребовать только действительно элементарной матрицы имущество...

Предполагая, что вы пытаетесь сделать это,[ожидаемое количество шагов до поглощения](https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expected_number_of_steps)уравнение из «конечных цепей Маркова»; (Кемени и Снелл), который воспроизводится в Википедии:

![t=N1](/imgs/qaNZt.png)

Или расширение фундаментальной матрицы

![t=(I-Q)^-1 1](/imgs/4Vfqd.png)

Перегруппировка:

![(I-Q) t = 1](/imgs/vI1YC.png)

Который в стандартном формате для использования функций для решения систем линейных уравнений

![A x = b](/imgs/0R0fM.png) 

Применение этого на практике, чтобы продемонстрировать разницу в производительности (даже для систем гораздо меньшего размера, чем те, которые вы описываете).

Представление двух альтернативных подходов для расчета количества ожидаемых шагов.

Выбираем пример, который является достаточно большим, чтобы продемонстрировать типы проблем, которые возникают при вычислении фундаментальной матрицы:

Производит следующие тайминги:

А также:

Дальнейшие эксперименты необходимы для проверки влияния производительности на разреженные матрицы, но ясно, что вычисление обратного гораздо медленнее, чем вы могли ожидать.

Подход, аналогичный представленному здесь, также можно использовать для дисперсии числа шагов



Причина, по которой вы получаете совет не использовать обратные матрицы для решения уравнений, заключается в численной устойчивости. Когда ваша матрица имеет собственные значения, которые равны нулю или близки к нулю, у вас возникают проблемы либо из-за отсутствия обратной (если ноль), либо из-за числовой устойчивости (если она близка к нулю). Таким образом, способ решения проблемы состоит в использовании алгоритма, который не требует наличия обратного. Решение заключается в использовании[Гауссово исключение](https://en.wikipedia.org/wiki/Gaussian_elimination), Это не обеспечивает полного обратного, а скорее приводит вас к форме ряд-эшелон, обобщению верхней треугольной формы. Если матрица обратима, то последняя строка матрицы результата содержит строку, обратную. Так что просто сделайте так, чтобы последний ряд, который вы исключаете, был желаемым.

Я оставлю это вам, чтобы понять, почему`I-Q` всегда обратим.