Алгоритм Чанки

Алгоритм Чанского — это алгоритм, позволяющий решать задачу вычисления определителя матрицы в классе $NC$. Идея алгоритма состоит в том, чтобы свести исходную задачу к решению системы $Ls=t$ относительно вектора $s$, где $L$ - нижнетреугольная матрица, которую можно обратить за время $T(n)=O(\log ^{2}n)$ с использованием $O(n^{4})$ процессоров.

Умножение матриц и их возведение в степень

Пусть $A$, $B$ - матрицы размеров $m\times n$ и $n\times p$ соответственно. Тогда для вычисления матрицы $C=AB$ достаточно параллельно вычислить $c_{ij}=\sum _{k=1}^{n}a_{ik}\cdot b_{kj}$ для всех $1\leq i\leq m$, $1\leq j\leq p$. Каждую из сумм при помощи $O(n)$ процессоров и процедуры параллельного префикса можно вычислить за время $O(\log n)$. Таким образом, используя $O(mnp)$ процессоров, можно вычислить всю матрицу $AB$ за время $O(\log n)$. В частности, если $A$ и $B$ - квадратные, понадобится $O(n^{3})$ процессоров и время $M(n)=O(\log n)$.

Используя процедуру параллельного префикса для цепочки $\underbrace {A\cdot A\cdot \ldots \cdot A} _{n}$ можно одновременно вычислить все степени матрицы, не превосходящие её размера $n$. В таком случае потребуется время $O(\log n)\cdot M(n)=O(\log ^{2}n)$ и $O(n^{4})$ процессоров.

Обращение нижнетреугольной матрицы

Нижнетреугольную матрицу $L$ размера $n\times n$ можно разбить на равные по размеру блоки

$\mathbf {L} ={\begin{pmatrix}\mathbf {L} _{1,1}&0\\\mathbf {L} _{2,1}&\mathbf {L} _{2,2}\end{pmatrix}}$

и тогда обратная к ней матрица $L^{-1}$ примет вид

$\mathbf {L} ={\begin{pmatrix}\mathbf {L} _{1,1}^{-1}&0\\\mathbf {-L} _{2,2}^{-1}\mathbf {L} _{2,1}^{}\mathbf {L} _{1,1}^{-1}&\mathbf {L} _{2,2}^{-1}\end{pmatrix}}$

Это означает, что задачу обращения матрицы $L$ можно решить путём двух параллельно выполняемых обращений нижнетреугольных матриц $L_{1,1}$, $L_{2,2}$ размеров $\left[{\frac {n}{2}}\right]\times \left[{\frac {n}{2}}\right]$ и двух последовательно выполняемых умножений. Обозначив через $T(n)$ время, требуемое для обращения матрицы $n\times n$, получим рекурренту

$T(n)\leq T\left({\frac {n}{2}}\right)+2M\left({\frac {n}{2}}\right)$

Так как $M(n)=O(\log n)$, $T(n)=O(\log ^{2}n)$

Описание метода

Пусть $A$ - квадратная матрица со стороной $n$. Её характеристический многочлен $\chi (\lambda )=\det(A-\lambda E)=\prod _{i=1}^{n}(\lambda -\lambda _{i})=\lambda ^{n}-s_{1}\lambda ^{n-1}+s_{2}\lambda ^{n-2}+...+(-1)^{n}s_{n}$,

где $s_{k}=\sum _{1\leq i_{1}<i_{2}<\ldots <i_{k}\leq n}\lambda _{i_{1}}\cdot \lambda _{i_{2}}\cdot \ldots \cdot \lambda _{i_{k}}$ - элементарный симметрический многочлен степени $k$, а $\lambda _{i}$ - собственные значения матрицы $A$. Заметим, что

$s_{1}=\lambda _{1}+\lambda _{2}+\ldots +\lambda _{n}=\mathrm {tr} A$, $s_{n}=\lambda _{1}\cdot \lambda _{2}\cdot \ldots \cdot \lambda _{n}=\det A$. Определим $s_{0}=1$.

Введём вспомогательную величину $f_{k}^{m}=\sum _{1\leq i_{1}<i_{2}<\ldots <i_{k}\leq n \atop j\notin \{i_{1},i_{2},\ldots ,i_{k}\}}(\lambda _{i_{1}}\cdot \lambda _{i_{2}}\cdot \ldots \cdot \lambda _{i_{k}})\cdot \lambda _{j}^{m}$. Учитывая $\mathrm {tr} A^{m}=\sum _{j=1}^{n}\lambda _{j}^{m}$, имеем

$s_{k}\cdot \mathrm {tr} A^{m}=\left(\sum _{1\leq i_{1}<i_{2}<\ldots <i_{k}\leq n}\lambda _{i_{1}}\cdot \lambda _{i_{2}}\cdot \ldots \cdot \lambda _{i_{k}}\right)\cdot \left(\sum _{j=1}^{n}\lambda _{j}^{m}\right)=\sum _{1\leq i_{1}<i_{2}<\ldots <i_{k}\leq n \atop 1\leq j\leq n}(\lambda _{i_{1}}\cdot \lambda _{i_{2}}\cdot \ldots \cdot \lambda _{i_{k}})\cdot \lambda _{j}^{m}=\sum _{1\leq i_{1}<i_{2}<\ldots <i_{k}\leq n \atop j\notin \{i_{1},i_{2},\ldots ,i_{k}\}}(\lambda _{i_{1}}\cdot \lambda _{i_{2}}\cdot \ldots \cdot \lambda _{i_{k}})\cdot \lambda _{j}^{m}+\sum _{1\leq i_{1}<i_{2}<\ldots <i_{k}\leq n \atop j\in \{i_{1},i_{2},\ldots ,i_{k}\}}(\lambda _{i_{1}}\cdot \lambda _{i_{2}}\cdot \ldots \cdot \lambda _{i_{k}})\cdot \lambda _{j}^{m}=f_{k}^{m}+f_{k-1}^{m+1}$

Используя соотношение $s_{k}\cdot \mathrm {tr} A^{m}=f_{k}^{m}+f_{k-1}^{m+1}$, получим тождество

$s_{k}\cdot \mathrm {tr} A^{0}-s_{k-1}\cdot \mathrm {tr} A^{1}+s_{k-2}\cdot \mathrm {tr} A^{2}+\ldots +(-1)^{k-1}s_{1}\cdot \mathrm {tr} A^{k-1}+(-1)^{k}\mathrm {tr} A^{k}=(f_{k}^{0}+f_{k-1}^{1})-(f_{k-1}^{1}+f_{k-2}^{2})+(f_{k-2}^{2}+f_{k-3}^{3})+\ldots +(-1)^{k-1}(f_{1}^{k-1}+f_{0}^{k})+(-1)^{k}f_{0}^{k}=$

$=f_{k}^{0}+(f_{k-1}^{1}-f_{k-1}^{1})-(f_{k-2}^{2}-f_{k-2}^{2})+\ldots +(-1)^{k-2}(f_{1}^{k-1}-f_{1}^{k-1})+(-1)^{k-1}(f_{0}^{k}-f_{0}^{k})=f_{k}^{0}=(n-k)s_{k}$

Таким образом, для произвольного $k$ справедливо

$ks_{k}-s_{k-1}\cdot \mathrm {tr} A^{1}+s_{k-2}\cdot \mathrm {tr} A^{2}+\ldots +(-1)^{k-1}s_{1}\cdot \mathrm {tr} A^{k-1}=(-1)^{k-1}\mathrm {tr} A^{k}$

или в матричном виде

${\begin{pmatrix}1&0&0&\ldots &0&0\\-\mathrm {tr} A&2&0&\ldots &0&0\\\mathrm {tr} A^{2}&-\mathrm {tr} A&3&\ldots &0&0\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\(-1)^{n-2}\mathrm {tr} A^{n-2}&(-1)^{n-3}\mathrm {tr} A^{n-3}&(-1)^{n-4}\mathrm {tr} A^{n-4}&\ldots &(n-1)&0\\(-1)^{n-1}\mathrm {tr} A^{n-1}&(-1)^{n-2}\mathrm {tr} A^{n-2}&(-1)^{n-3}\mathrm {tr} A^{n-3}&\ldots &-\mathrm {tr} A&n\end{pmatrix}}{\begin{pmatrix}s_{1}\\s_{2}\\s_{3}\\\vdots \\s_{n-1}\\s_{n}\end{pmatrix}}={\begin{pmatrix}\mathrm {tr} A\\-\mathrm {tr} A^{2}\\\mathrm {tr} A^{3}\\\vdots \\(-1)^{n-2}\mathrm {tr} A^{n-1}\\(-1)^{n-1}\mathrm {tr} A^{n}\end{pmatrix}}$

Для решения этой системы нам нужно обратить нижнетреугольную матрицу в левой части и умножить её на столбец из правой - все эти операции вместе с одновременным вычислением значений вида $\mathrm {tr} A^{k}$ для всех $k\in \{1,2,\ldots ,n\}$ мы можем выполнить за время $O(\log ^{2}n)$ с использованием $O(n^{4})$ процессоров. Получив решение $s={\begin{pmatrix}s_{1}\\s_{2}\\s_{3}\\\vdots \\s_{n-1}\\s_{n}\end{pmatrix}}$, остаётся лишь взять последний элемент $s_{n}$, который равен искомому $\det A$.

Литература

• Kozen, Dexter (1991), The Design and Analysis of Algorithms, New York: Springer-Verlag, pp. 166–170, ISBN 0-387-97687-6