Какой самый быстрый алгоритм для вычисления обратной матрицы и ее определителя для положительно определенных симметричных матриц?

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

Высокая точность и скорость действительно необходимы. (выполняются миллионы матриц)
Определитель необходим. В каждом расчете требуется только один элемент обратной матрицы. Спасибо!

algorithms matrix заказы
источник

Нужно ли инвертировать миллионы таких матриц? В противном случае скорость не должна быть проблемой.

Вольфганг Бангерт

Я отредактировал ваш заголовок и вопрос для ясности. Если я допустил какие-либо ошибки, пожалуйста, дайте мне знать.

Джефф Оксберри

@Wolfgang Bangerth Да, скорость должна быть рассмотрена.

Заказы

Знаете ли вы, какой элемент обратной матрицы необходим? Или это может быть случайная запись?

Воспоминание

@ Заказы Ваш комментарий и редактирование кажутся противоречивыми: вам нужен один элемент обратного или все они?

Федерико Полони

Для задач, которые меня интересуют, размер матрицы равен 30 или меньше.

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

Учитывая положительно определенную симметричную матрицу, каков самый быстрый алгоритм вычисления обратной матрицы и ее определителя?

Если скорость является проблемой, вы должны ответить на следующие вопросы:

Тебе действительно нужно все обратное? (Многие приложения не должны формировать явное обратное.)
Вам действительно нужен определитель? (Детерминанты встречаются редко, но, безусловно, не случайно в вычислительной науке.)
Вам нужна либо высокая точность? (Алгоритмы низкой точности, как правило, быстрее.)
Достаточно ли вероятностного приближения? (Вероятностные алгоритмы имеют тенденцию быть быстрее.)

Стандартным ответом на вашу проблему обращения небольшой положительно определенной матрицы и вычисления ее детерминанта будет разложение Холецкого. Если $A = LL^{T}$ , тогда $\det(A) = \prod_{i=1}^{n}l_{ii}^{2}$ и . $\det(A^{-1}) = \prod_{i=1}^{n}l_{ii}^{-2}$

Предполагая, что равно на , разложение Холецкого можно вычислить примерно за флопов, что составляет примерно половину стоимости разложения LU. Однако такой алгоритм не будет считаться «быстрым». Рандомизированы разложение LU $A$ $n$ $n$ $n^{3}/3$ может оказаться более быстрым алгоритмом, который стоит рассмотреть, если (1) вам действительно нужно вычислить большое количество матриц, (2) факторизация действительно является ограничивающим шагом в вашем приложении, и (3) любая ошибка, возникающая при использовании рандомизированного алгоритма, приемлемо. Ваши матрицы, вероятно, слишком малы, чтобы разреженные алгоритмы были полезны, поэтому единственные другие возможности для более быстрых алгоритмов потребовали бы дополнительной структуры матрицы (например, с полосами) или использования структуры проблемы (например, возможно, вы можете разумно реструктурировать свой алгоритм так, чтобы вы не больше нужно вычислять матрицу, обратную или ее определитель). Эффективные алгоритмы определителя - это примерно стоимость решения линейной системы с точностью до постоянного множителя, поэтому те же аргументы, что и для линейных систем, применимы и к вычислению определителей.

Джефф Оксберри
источник

Только краткое замечание: если , для вычисления одного элемента следует вычисляют только й столбец . Как только факторизация Холецкого вычислена, это делается путем прямой и обратной подстановки по отношению к вектору rhs всех нулей и только к одному в строке . Поскольку вычисление может быть прервано, как только будет вычислено , наилучший случай - для наихудший случай для когда нужно вычислить полный назад и прямые замены.

B = A^{- 1}

$B = A^{-1}$

b_{i j}

$b_{ij}$

j

$j$

B

$B$

j

$j$

b_{i j}

$b_{ij}$

b_{n n} = l_{n n}^{- 2}

$b_{nn} = l_{nn} ^{-2}$

b_{11}

$b_{11}$

Стефано М

@StefanoM Более того, вы можете переставить матрицу до начала вычислений, чтобы вы всегда были в лучшем случае.

Федерико Полони

Какой самый быстрый алгоритм для вычисления обратной матрицы и ее определителя для положительно определенных симметричных матриц?

Ответы: