Рекурсия в алгоритме Штрассена
Мне интересно, как вы будете делать рекурсивные вызовы в алгоритме Штрассена, и где именно они требуются.
Я понимаю, что 7 множителей более эффективны, чем 8, которые мы имели бы в противном случае, но я запутался в том, как эти множители вычисляются рекурсивно. В частности, если мы следуем парадигме "разделяй и властвуй", то какую именно часть матриц мы "делим" и как мы будем это делать, пока не доберемся до базового случая, в котором мы можем покорить рекурсивные части по отдельности?
Спасибо!
2 ответа
Мы делаем рекурсивные вызовы при расчете этих 7 множителей. Сначала мы увеличиваем размер матриц до степени 2, а затем на каждом шаге делим каждую матрицу на 4 части.
Мы делим A и B равномерно на четверти или шестнадцатые или шестьдесят четвертые и т. Д., Чтобы уменьшить их до матриц 2x2. Метод Штрассена может быть применен только к матрицам типа 2 ^ nx 2 ^ n.
Для матриц не типа 2 ^ nx 2 ^ n вы можете заполнять нулями до тех пор, пока не будет выполнено требование.