На месте реализации алгоритма Штрассена?

Question

Мне удалось реализовать решение на месте, хотя манипуляции с индексами для наивного Divide & Conquer алгоритм для матричного умножения, который требует 8 рекурсивных вызовов в каждом повторении. Однако при попытке реализовать алгоритм Штрассена я не смог найти способ сделать это на месте. Вместо этого я должен malloc 19 подматриц для 7 рекурсивных вызовов при использовании C для программирования.

Как реализовать алгоритм Strassen на месте? Или это возможно?

Answer 1

Скажем, вы умножаете две матрицы nxn. Вам понадобится место для 4n^2 целых чисел: 2n^2 для умножения матриц, n^2 для результата и окончательного n^2 для работы с нуля. Рекурсивно используется матрица работы с нуля. То есть вы используете 1/4 его для каждой из двух подматриц, которые вы создаете, добавляя в Strassen's 1/4 результат результата умножения и конечный 1/4 для работы с царапинами этого умножения. И т.д. ... насколько вы хотите рекурсивно.