Мне удалось реализовать решение на месте с помощью манипуляций с индексами для наивного алгоритма Divide & Conquer для умножения матриц, который требует 8 рекурсивных вызовов в каждом повторении. Однако при попытке реализовать алгоритм Штрассена я не смог найти способ сделать это на месте. Вместо этого я должен выделить 19 подматриц для 7 рекурсивных вызовов при использовании C для программирования.
Как реализовать алгоритм Штрассена на месте? Или это возможно?
Допустим, вы перемножаете две матрицы размера nxn. Вам понадобится место для 4n ^ 2 целых чисел: 2n ^ 2 для умножаемых матриц, n ^ 2 для результата и окончательное n ^ 2 для работы с нуля. Вы используете рекурсивную рабочую матрицу. То есть вы используете 1/4 его для каждой из двух подматриц, которые вы создаете, добавляя к Штрассену, 1/4 для результата умножения и последнюю 1/4 для первоначальной работы этого умножения. И т.д. ... насколько вы хотите рекурсивно.
