Быстрая и обратная-стабильная (слева) матрица обратная

Мне нужно вычислить много матрицы (для итерационного полярного разложения Ньютона) с очень небольшим числом вырожденных случаев ( ).$3\times3$$<0.1\%$

Кажется, что работает явное обратное (через младшие матрицы, разделенные по определителю), и составляет ~ 32 ~ 40 слитых флопов (в зависимости от того, как я вычисляю обратную величину по определителю). Не учитывая масштабный коэффициент det, это всего 18 плавких флопов (каждый из 9 элементов имеет форму ab-cd, 2 плавких флопа).

Вопрос:

• Есть ли способ вычислить обратное значение используя менее 18 (с произвольным масштабом) или 32 (с правильным масштабом, учитывая обратный 1 оп) слитые флопы?$3\times 3$
• Существует ли экономичный способ (использование ~ 50 флопс) для вычисления обратно-стабильной левой обратной матрицы ?$3\times 3$

Я использую поплавки одинарной точности (игра для iOS). Обратная стабильность - интересная новая концепция для меня, и я хочу экспериментировать. Вот статья, которая спровоцировала мысль.

Я постараюсь высказать свое мнение по первому вопросу относительно быстрого$3\times 3$обратное . Рассматривать

$$A=\left[ \begin{array}{ccc} a & d & g\\ b & e & h\\ c & f & i \end{array}\right]$$

Поскольку матрицы являются небольшими и очень общими (не имеют никакой известной структуры, нулей, относительных масштабов элементов), я думаю, что было бы невозможно дать алгоритм для произвольного масштаба (без $1/\det(A)$) обратный, который быстрее, чем 18 плавких флопов, поскольку для каждого из 9 элементов требуется 2 плавких флопа, а все продукты уникальны, при условии отсутствия предварительной информации о $A$записи $a,\ldots,i$,

$$A^{-1}\det(A)=\text{adj}(A)= \left[\begin{array}{ccc} ei-fh & di-fg & ge-dh\\ bi-ch & ai-cg & ah-bg\\ ce-bf & af-cd & ae-bd \end{array}\right]$$ Вот, $\text{adj}(A)$ обозначает адъюгат (транспонирование кофакторов), который по существу является обратным с «произвольным масштабом» (при условии, что обратное существует).

Тем не менее, некоторые расчеты могут быть повторно использованы для расчета $\det(A)$, Если я расширю его до первого столбца (есть еще 5 вариантов):

$$\begin{aligned} \det(A)&=a(ei-fh)+b(fg-di)+c(dh-ge)\\ &=a\underbrace{(ei-fh)}_*-b\underbrace{(di-fg)}_*-c\underbrace{(ge-dh)}_* \end{aligned}$$ Обратите внимание, что (*) уже был вычислен во время оценки $\text{adj}(A)$, Таким образом, обратная величина детерминанта может быть вычислена в 4 дополнительных плавких флопах (если$1/\det(A)$ взаимный считается 1 флоп).

Теперь каждый из 9 элементов $\text{adj}(A)$ следует масштабировать по уже полученной обратной величине определителя, добавив еще 9 слитых флопов.

Так,

1. Рассчитать $\text{adj}(A)$ в 18 слитых флопах
2. Рассчитать $\det(A)$ в 3 слитых флопах с использованием записей уже вычисленных $\text{adj}(A)$
3. найти $\frac{1}{\det(A)}$ (при условии 1 флопа).
4. Масштаб каждого элемента уже вычислен $\text{adj}(A)$ по $\frac{1}{\det(A)}$ в еще 9 слитых флопах.

В результате 18 + 3 + 1 + 9 = 31 слитых флопов . Вы не описали свой способ вычисления определителя, но я думаю, 1 дополнительный флоп может быть сохранен. Или это может быть использовано для проверки$|\det(A)|>\epsilon$ на шаге 3, где $\epsilon$- допуск для вырожденного (не обратимого) случая, в результате которого получается 32 плавныхif флопа (при условии, что 1 флоп).

Я не думаю, что есть более быстрый способ вычисления обратного $3\times 3$Общая матрица, так как все остальные расчеты являются уникальными. Использование Cayley-Hamilton не должно помочь с точки зрения скорости, так как в общем случае это потребует расчета$A^2$ для $3\times 3$ матрица помимо некоторых других операций.

NB:

• этот ответ не имеет дело с численной стабильностью
• Возможный потенциал векторизации и оптимизации структуры доступа к памяти также не обсуждается.