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

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

Параллельное возведение в степень

Пусть $A$, $B$ — матрицы размеров $m\times n$ и $n\times p$ соответственно. Тогда для вычисления матрицы $C=AB$ достаточно параллельно вычислить ${\textstyle c_{ij}=\sum _{k=1}^{n}a_{ik}\cdot b_{kj}}$ для всех $1\leq i\leq m$, $1\leq j\leq p$.

Префиксные суммы в выражениях такого вида могут быть вычислены за время $O(\log n)$ с применением $O(n)$ параллельных процессоров. Таким образом, используя $O(mnp)$ процессоров, можно вычислить всю матрицу $AB$ за время $O(\log n)$.

Применяя схожую процедуру для вычисления ${\textstyle A^{n}=A\cdot A\cdot \ldots \cdot A}$, можно вычислить все степени матрицы, не превосходящие $n$, что потребует ${\textstyle O(\log n)\cdot M(n)=O(\log ^{2}n)}$ времени и ${\textstyle O(n^{4})}$ процессоров.

Здесь $M(n)$ — время, необходимое для умножения двух квадратных матриц размера $n\times n$.

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

Нижнетреугольную матрицу $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} ^{-1}={\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}$ размера ${\textstyle \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$. Её характеристический многочлен имеет вид

${\begin{aligned}\chi (\lambda )=\det(A-\lambda E)=(\lambda -\lambda _{1})\dots (\lambda -\lambda _{n})=\lambda ^{n}-s_{1}\lambda ^{n-1}+s_{2}\lambda ^{n-2}+...+(-1)^{n}s_{n}\end{aligned}}$,

где $s_{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}$, такую что

$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}$, можно выразить

${\begin{aligned}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}\end{aligned}}$

Используя данное соотношение, можно записать

${\begin{aligned}&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}\end{aligned}}$

Таким образом, для произвольного $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}&\dots &s_{n}\end{pmatrix}}^{T}$, остаётся лишь взять последний элемент $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
• Солтис М. Алгоритм Чанки // Введение в анализ алгоритмов / пер. с англ. А. В. Логунова. — М.: ДМК Пресс, 2019. — С. 145—146. — 278 с. — ISBN 978-5-97060-696-4.