Вычислительная интенсивность транспонирования матрицы против вычисления обратного

Question

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

Меня особенно интересует разница в инструкциях процессора / графического процессора, участвующих в каждом процессе, или, если я ошибся, то самый низкий уровень в стеке, при котором возникает узкое место. Мне также было бы интересно узнать о любых ресурсах, книгах, веб-сайтах и ​​т. Д., Где я могу узнать больше об этих видах деятельности / узких местах.

Answer 1

Транспонирование матрицы nxn в худшем случае является операцией O (n ² ), в то время как вычисление обратной общей неособой матрицы nxn является операцией O (n ³ ) , Это просто стоимость выполнения этих вещей.

Кроме того, большинство приложений не вычисляют инверсии матриц, поскольку целью является решение линейной системы Ax = b, а не нахождение обратной. Это быстрее и точнее решить эту проблему, используя разложения и треугольные решения (см., Например, Разложение LU , для общих неособых матриц). Матричные инверсии могут быть вычислены с использованием исключения Гаусса-Джордана (а также других подходов).

Что касается доступных подпрограмм, вы можете найти реализации LAPACK, которые можно использовать для вычисления декомпозиции LU (и, вероятно, обратной матрицы).

Answer 2

Матрица transpose просто включает в себя обмен парами элементов в матрице - т.е. это просто перемещение данных и никаких вычислений.Матрица обратная OTOH требует значительных вычислений.