Эффективные алгоритмы вычисления матрицы, умноженной на ее транспонирование

Question

Для класса вопрос, который задал мой учитель, - это алгоритмическая стоимость умножения матрицы на ее транспонирование.При использовании стандартного алгоритма умножения матриц с 3 циклами эффективность равна O (N ^ 3), и мне интересно, был ли способ манипулировать или использовать преимущества транспонирования матрицы * матрицы для получения более быстрого алгоритма.Я понимаю, что когда вы умножаете матрицу на ее транспонирование, вы должны вычислять меньше матрицы, потому что она симметрична, но я не могу думать о том, как манипулировать алгоритмом, который может занять меньше O (n ^ 3).

Я знаю, что есть алгоритмы, такие как Коппенсмит и Страуссен, которые являются более быстрыми общими алгоритмами умножения матриц, но кто-нибудь может дать какие-либо советы или идеи о том, как в вычислительном отношении воспользоваться преимуществами транспонирования?

Спасибо

Answer 1

На данный момент нет никаких асимптотических разрушающих барьер свойств этого конкретного умножения.

Очевидная оптимизация заключается в использовании симметрии продукта. То есть [i][j] th запись равна [j][i] th записи.

Для оптимизаций, специфичных для реализации, вы можете выполнять значительный объем кэширования. Очень много времени при умножении больших матриц тратится на передачу данных в и из памяти и процессора. Поэтому разработчики ЦП внедрили интеллектуальную систему кеширования, благодаря которой недавно использованная память хранится в небольшом разделе памяти, называемом кеш. В дополнение к этому, они также сделали так, что рядом память также кэшируется. Это связано с тем, что большая часть ввода-вывода в памяти связана с чтением / записью из / в массивы, которые хранятся последовательно.

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