Альтернативы для гауссовского преобразования исключения и алгоритм победы

Question

Алгоритм исключения Гаусса в преобразовании и завоевании имеет сложность O (n ³ ). Есть ли методика, которая дает более эффективную сложность этого алгоритма?

Answer 1

Существуют алгоритмы обращения матриц с лучшей асимптотической сложностью, например, алгоритм Штрассена со сложностью O (n ^2.807 ) и алгоритм Копперсмита-Винограда со сложностью O (n ^2,376 ).

(Обратите внимание, что сложность умножения матриц и инверсии матриц одинакова )

Answer 2

Зависит от сложности, которую вы измеряете:

Количество умножений: нет, изменяя технику, вы можете только ухудшить сложность исключения Гаусса.

Количество временных шагов: Да, параллельная реализация операций со строками уменьшает сложность времени до O (n).