Как изменить алгоритм Штрассена, чтобы он работал для матрицы любого размера (например, для п=5)?
алгоритм Штрассена для любого входа
comment
На вашем месте я бы добавил ссылку на алгоритм Штрассена, чтобы избавить нас от гугления :)
- person Armen Tsirunyan schedule 02.04.2011
comment
Единственное, что я мог придумать, это Boost (uBlas); Однако, согласно этот проект Штрассена все еще находится в списке TODO.
- person sehe schedule 02.04.2011
Ответы (1)
Все, что вам нужно сделать, это дополнить матрицы нулями в строках и столбцах, пока они не станут квадратными матрицами, размер которых равен степени двойки. Или, говоря иначе:
Поместите матрицы, которые нужно умножить, в левые верхние углы двух матриц 2 ^ n x 2 ^ n. Установите для всех неиспользуемых элементов значение 0. Затем просто запустите алгоритм, и нужный вам результат будет в верхнем левом углу матрицы результатов.
person
Null Set
schedule
01.04.2011
Получающийся алгоритм тогда медленнее, чем стандартный алгоритм умножения?
- person Antti Huima; 02.04.2011
Нет, это все равно будет быстрее для больших матриц. Скажем, N - размер - находится между 2 ^ (n-1) и 2 ^ n. Тогда в простой версии будет использоваться O(N^3) операций, что составляет не менее O(2^(3n - 3)). Штрассен составляет около O (N ^ 2,8), т.е. O (2 ^ (2,8n)). Обычно 2 ^ (3 n - 3) больше, чем 2 ^ (2,8 n) :)
- person Andrei; 02.04.2011
