Градуированные вычисления и быстрое умножение матриц

При решении задач с большим параметром (размерности) $n$ используется два метода уменьшения сложности. В качестве основного метода используется метод рекурентного разделения задачи с параметром $n$ на несколько подзадач с меньшей размерностью $n/l$ и формирование общего решения основываясь на решении подзадач с уменьшенными размерностями. Автор называет этот метод методом фильтрации. В англоязычных источниках этот метод выделяют как принцип Разделяй и властвуй.
Сортировка. Продемонстрируем этот метод в задаче упорядочивания (сортировки) $n$ чисел. Если решили задачу для размерностей $n_1, n_2, \ n_1+n_2=n$, то остается только сливать два упорядоченных множества:
$$x[i[1]]<x[i[2]]<...<x[i[n_1]], \ \ \ x[j[1]]<x[j[2]]<...<x[j[n_2-1]].$$
Для этого достаточно установить два указателя для двух массивов $l_1=1, l_2=1, l=1$ и сдвигать указатели массива с меньшим знаменателем:
$$while(l<n)\{ if(x[i[l_1]]<x[j[l_2]])\{ii[l++]=i[l_1];if(l_1<n_1)l_1++;$$

$$else\{while(l_2<=n_2)ii[l++]=j[l_2++]\}\}else ...$$
В случае не выполнения сравнения передвижение по второму счетчику. Обозначая количество операций (в нашем случае сравнений) через $T(n)$ приходим к неравенству типа:
$$T(n)= Cn^\alpha+mT(\frac nl).$$
В нашем случае $l=m=2, \alpha=1, \ \frac{n-1}{2}\le Cn\le n-1.$ Решая рекурентное соотношение (для нашего случая) получаем $T(n)=O(n\log n)$. Отметим, что каждый член массива участвует в операции сравнения примерно $O(\log n)$ раз. Для отделения члена $x[i]$ с соседнем по порядку необходимо в среднем не меньше $n_i\ge \log n$ битовых сравнений. Следовательно, по каждому элементу в среднем на сравнение требуется не менее $\log^2 n /2$ битовых операций.
При использовании метода фильтрации промежуточные вычисления (сравнения в низших ветках) используются только выше в своей ветке. Поэтому этот метод менее эффективен по сравнению метода градуированного вычисления. В задаче сортировки градуировка по битам переменных отличает от всех элементов, которые относятся к другой градуировке. Таким образом, общее количество битовых операций равно $\sum_{i=1}^{n-1}n_i =O(n\log n)$. Это может быть меньше количества всех битов в записи чисел. За меньшее количество битовых сравнений нельзя упорядочить. Такие алгоритмы, не улучшаемые по эффективности, некоторые авторы называют алгоритмом от бога.
Умножение по методу фильтрации. Большие числа на компьютере представляются в M – ичной системе исчисления как значения многочлена:
$$X=x_0+x_1M+...+x_{k-1}M^{k-1}.$$
$M$ есть степень двойки, обычно $M=2^d, \ d=32$. Считаем, что $0\le x_i<M$. Соответственно $X<M^k=2^n, n=kd$
Допустим имеется еще другое большое число $Y=y_0+...+y_{l-1}M^{l-1}$ и требуется их умножить. Произведение не превышает $M^m, m=k+l$, и оно представляется в виде:
$$Z=XY=\sum_{i=0}^{m-1}z_iM^i, \ \ z_i=\sum_{j\le i}x_jy_{i-j}.$$
Правда, здесь после вычисления надо осуществить переносы, когда цифры становятся не меньше $M$. Для этого складываем перенос из нижнего уровня и делим на $M$, остаток от деления будет настоящей цифрой этого уровня, а целая часть от деления пойдет в следующий уровень как перенос. На переносы потребуется $O(n\log n)$ операций.
Более эффективный метод умножения больших чисел впервые использовал А.А. Карацуба в 1962 г. Он использовал метод фильтрации (разделяй и властвуй), разделяя умножаемые числа на композицию двух поменьше:
$$X=X_0+X_1*N, \ N=2^R, \ Y=Y_0+Y_1*N.$$
Здесь $X_0,Y_0$ числа, состоящие из младших разрядов, $X_1,Y_1$ из старших разрядов. Результат умножения представляется в виде:
$$XY=X_0Y_0+N(X_0Y_1+X_1Y_0)+X_1Y_1N^2.$$
Среднее число вычисляется одним дополнительным умножением, используя результаты умножений крайних:
$$X_0Y_1+X_1Y_0=(X_0+X_1)(Y_0+Y_1)-X_0Y_0-X_1Y_1.$$

Таким образом, принцип разделяй и властвуй для умножения двух $n$ битных чисел, требующих $T(n)$ операций приводит к рекурентному соотношению:
$$T(n)=3T(\frac n2)+Cn.$$
Решая эту рекурсию получаем:
\begin{equation}\label{Eq2.1} T(n)=C(2^k+3*2^{k-1}+...+3^k)=C(3^{k+1}-2^{k+1})=O(n^{\log 3}). \end{equation}

В соответствии с приведенной мастер теоремой принципа разделяй и властвуй, число операций при умножении методом Карацуба оценивается величиной $O(n^{\log 3})$. Мы условились, что логарифм без указания основания означает логарифм по основанию 2.
Впоследствии в 1969 г. Штрассеном найден аналог такого умножения и для матриц. Для этого разобьем матрицы $X,Y$ размером $n\times n$ на подматрицы половинной размерности:
$$X=\binom{A \ B}{C \ D}, \ Y=\binom{E \ F}{G \ H}, \ XY=\binom{AE+BG \ \ \ AF+BH}{CE+DG \ \ \ CF+DH}.$$
Вводя 7 произведений:
$$P_1=A(F-H), \ P_2=(A+B)H, \ P_3=(C+D)E,$$

$$P_4=D(G-E), \ P_5=(A+D)(E+H),$$

$$P_6=(B-D)(G+H), \ P_7=(A-C)(E+F),$$
произведение матриц можно представить в виде:
$$XY=\binom{P_5+P_4-P_2+P_6 \ \ \ \ \ \ \ P_1+P_2}{ \ \ \ \ \ \ \ \ \ \ \ \ P_3+P_4 \ \ \ \ \ \ \ \ \ P_1+P_5-P_3-P_7}.$$

Это приводит к рекурентному соотношению относительно необходимого количества операций для умножения матриц размера $n\times n$:
$$T(n)=7T(\frac n2)+\frac{9}{2}n^2.$$
Решая рекурентное соотношение получаем
$$T(n)=O(n^{\log 7}), \ \log 7\approx 2.81.$$
Точнее, без учета операций с адресами элементов при $n=2^k$: $T(2^k)=6(7^k-4^k)+7^k.$ Здесь $7^k$ - количество умножений в формате чисел, $6(7^k-4^k)$ количество сложений и вычитаний в формате чисел.
Через оценку ранга умножения матриц добились уменьшения показателя степени, называемого предельной экспонентой умножения, до величины $O(n^{\alpha}), \alpha \approx 2.3728639$
Умножение градуировкой В методе градуировки умножение переносится в умножение в градуированной алгебре. Например, для умножения двух многочленов от $k$ переменных
$$f(x)=f(x_1,x_2,...,x_k)=\sum_{0\le i_j<m_j}a[i_1,..,i_k]x_1^{i_1}...x_{k}^{i_k}, \phi(x)=\sum_i b[i_1,..,i_k]x_1^{i_1}...x_{k}^{i_k}$$
градуируем по степеням многочлена сопоставляя однородным элементам элементы группы $G=Z_{n_1}\bigoplus Z_{n_2}\bigoplus ...\bigoplus Z_{n_k}, n_i=2m_i-1.$ Здесь учитывается, что произведение двух многочленов, имеющих степень $m_i-1$, является многочленом степени $2m_i-2$ и следовательно имеет $2m_i-1$ коэффициентов для определения. Пусть $G'=\{\mu=\mu_1...\mu_k\}$ группа характеров. Каждый характер определяет значение многочлена - элемента групповой алгебры по схеме:
$$f=\sum_{g\in G}a(g)g \to \mu(f)=\sum_{g\in G}a(g)\mu(g).$$
В силу $\mu(g_1g_2)=\mu(g_1)\mu(g_2)$ каждое $\mu$ значение произведения равно произведению $\mu$ значений сомножителей. Набор $\mu$ значений достаточно для определения многочлена (его коэффициентов перед степенями). Действительно
$$\psi=\sum_{g_k} c(g_k)g_k=(\sum_{g_i}a(g_i)g_i )(\sum_{g_j} b(g_j)g_j ), \ c(g_k)=\sum_{g_ig_j=g_k} a(g_i)b(g_j),$$

$$nc_{g_k}=\sum_{\mu} \mu(g_k^{-1})\mu(\psi)=\sum_i \sum_{\mu}c(g_i)\mu(g_k^{-1}g_i)=\sum_i \delta_k^i c(g_i)n.$$
Ясно, что меньшим количеством умножений нельзя вычислить произведение. Поэтому и здесь метод градуировки можно назвать алгоритмом от бога. Вычисление произведения требует предварительного вычисления $n$ $\mu$ значений каждого сомножителя. На это уходит $O(n\log n)$ операций. Этот процесс называют преобразованием Фурье. После вычисления значений произведения требуется вычислить $n$ коэффициентов по значениям. Этот процесс называют обратным преобразованием Фурье. На его вычисление так же тратится $O(n\log n)$ операций.
Отметим, что в каждом произведении $\mu$ значений присутвует каждая пара произведений $a(g_i)b(g_j)$ с одинаковым коэффициентом $\mu(g_ig_j)$ для всех $g_ig_j=g_k$. Поэтому, этот метод соответствует принципу Объединяй и направляй. Гёте сказал: Разделяй и властвуй - мудрое правило, однако правило объединяй и направляй лучше. Первое соответствует методу фильтрации, второе методу градуировки.
В случае не коммутативного умножения возникают следующие трудности. Произведения $g_ig_j$ и $g_jg_i$ отличаются, характеров (одномерных представлений) меньше базисных элементов. Здесь групповая алгебра заменяется бигрупповой алгеброй $K(G',G)=\{\sum_{\mu,g}a(\mu,g)\mu g\}$, порожденной характерами и элементами группы с соотношениями перестановочности $\mu g=\mu(g) g\mu$. Это соотношение по сути является соотношением неопределенности Гейзенберга об одновременной не измеримости координат и импульса.
Удобнее работать с группой $G=(Z_2)^k, \ n=2^k$. Сопоставим элементу группы $g=(i_1,...,i_k)$ число $i=i_1+i_2*2+...+i_k*2^{k-1}$ с двоичными цифрами $(i_1,...,i_k)$ и матрицу $n\times n$ переставляющую строки правого множителя:
$$y^j=(y^j_{il}), \ y^j_{i,l}=\delta_{i}^{j\bigoplus l},(y^j)^2=1=E.$$
Здесь все операции сложения, умножения производятся покомпонентно (без переносов). В качестве характеров служат диагональные матрицы
$$x^i=(x^i_{lj}), x^i_{lj}=\delta_l^j(-1)^{(i,j)}, (i,j)=\sum_{m=1}^k i_m*j_m, (x^i)^2=1=E.$$
Легко проверяется, что $x^iy^j$ образуют базис в алгебре матриц $n\times n$ и соотношение коммутирования (неопределенности) $x^iy^j=(-1)^{(i,j)}y^jx^i$. Соответственно, задача умножения матриц сводится к умножению некоммутирующих многочленов от $x^i,y^j$. Каждому элементу $x^{t_1}y^{t_2}$ соответствует характер
$$\mu_{t_1,t_2}(x^iy^j)=x^{t_1}y^{t_2}x^iy^j(x^{t_1}y^{t_2})^{-1}(x^iy^j)^{-1}=(-1)^{(t_1,j)-(t_2,i)}.$$
Этих характеров достаточно для выделения нужных коэффициентов многочлена. Однако, для выделения коэффициентов с произведений $\mu$ значений
$$a(i_1,j_1)b(i_2,j_2)\mu(x^{i_1}y^{j_1}x^{i_2}y^{j_2})=a(i_1,j_1)b(i_2,j_2)(-1)^{(j_1,i_2)}\mu(x^{i_1+i_2}y^{j_1+j_2}$$
необходимо разделить члены с разными знаками $(-1)^{(j_1,i_2)}$. Для этого необходимо привлечь нечетные характеры:
$$\mu^*_{t_1,t_2}(x^iy^j)=(-1)^{(i,j)}\mu_{t_1,t_2}(x^iy^j).$$
Это соответствует значению транспонированной матрицы. У нечетных элементов значения характеров отличаются знаком. Этот набор характеров, совместно с предыдущим набором позволяет отличить порядок произведения в выражении $x^{i_1}y^{j_1}x^{i_2}y^{j_2}$. Произведения двух элементов $x^{i_1}y^{j_1},x^{i_2}y^{j_2}$ переставляются множителем $(-1)^{(i_1,j_2)-(j_1,i_2)}$. Он равен произведению нечетностей сомножителей и самого произведения:
$$(-1)^{(i_1,j_2)-(j_1,i_2)}=(-1)^{(i_1,j_1)+(i_2,j_2)+(i_1+i_2,j_1+j_2)}.$$
Это позволяет получить коэффициенты разложения произведения через произведения значений из $2n^2$ наборов. Учитывая наличие одной зависимости в наборе произведений, можно избежать использования одного произведения значений. Т.е. достаточно вычислить $2n^2-1$ произведений значений. Не сложно показать, что ранг умножения матриц не меньше $2n^2-1$ . В этом смысле, опять получаем алгоритм от бога. Предварительные вычисления $2n^2$ значений сомножителей и $n^2$ коэффициентов произведения из $2n^2-1$ произведений производится за $O(n^2\log n)$ операций.