Ага, всё понятно. Если сделаешь подобную оптимизацию для алгоритма Штрассена - выложи, мне очень интересен результат. Там явно надо грамотно обращаться с памятью :)
И если интересно будет, попробуй ещё поработать с алгоритмом Винограда (именно Винограда, а не Копперсмита—Винограда), там совсем ничего сложного нет, но мне кажется подобная оптимизация заставит его работать лучше, чем просто блочное перемножение. У меня на тех же матрицах он дал результат в 50% от времени перебора в лоб.
Хорошо, я сейчас обьясню в чём у меня была проблема.
Дело в том, что алгоритм Штрассена (в котором мы разбиваем матрицу на 4 подматрицы а затем обходимся перемножением 7 матриц размером n/2) действует рекурсивно. В результате чего мой код на си под юникс для матрицы 2000x2000 дал результат по времени в 75% процентов по сравнению с подсчётом в лоб. Теоретически же он должен был дать 23%. Но я не оптимизировал его иначе как алгоритмически. Потери времени у меня как раз были на этапе выделения памяти. Так вот вы использовали этот алгоритм, я правильно понял?
"И будем перемножать матрицу из подматриц по обычному правилу. Не сложно математически доказать, что ответ получится такой же как и при обычном перемножении"
И если интересно будет, попробуй ещё поработать с алгоритмом Винограда (именно Винограда, а не Копперсмита—Винограда), там совсем ничего сложного нет, но мне кажется подобная оптимизация заставит его работать лучше, чем просто блочное перемножение. У меня на тех же матрицах он дал результат в 50% от времени перебора в лоб.
Дело в том, что алгоритм Штрассена (в котором мы разбиваем матрицу на 4 подматрицы а затем обходимся перемножением 7 матриц размером n/2) действует рекурсивно. В результате чего мой код на си под юникс для матрицы 2000x2000 дал результат по времени в 75% процентов по сравнению с подсчётом в лоб. Теоретически же он должен был дать 23%. Но я не оптимизировал его иначе как алгоритмически. Потери времени у меня как раз были на этапе выделения памяти. Так вот вы использовали этот алгоритм, я правильно понял?
Раскажи-ка тут поподробнее.