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

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

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

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

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

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

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

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

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

${\displaystyle \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}}}$.

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

Пусть ${\displaystyle T(n)}$ — время, требуемое для обращения нижнетреугольной матрицы ${\displaystyle n\times n}$. Оно подчиняется рекуррентному соотношению

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

Выше показано, что ${\displaystyle M(n)=O(\log n)}$, поэтому окончательная оценка, в силу основной теоремы о рекуррентных оценках, равна

${\displaystyle T(n)=O(\log ^{2}n)}$.

Пусть ${\displaystyle A}$ — квадратная матрица со стороной ${\displaystyle n}$. Её характеристический многочлен имеет вид

${\displaystyle {\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}}}$,

где ${\displaystyle s_{k}}$ — элементарные симметрический многочлен степени ${\displaystyle k}$, а ${\displaystyle \lambda _{i}}$ — собственные значения матрицы ${\displaystyle A}$. В частности,

${\displaystyle s_{1}=\lambda _{1}+\lambda _{2}+\ldots +\lambda _{n}=\mathrm {tr} A}$ — след матрицы,

${\displaystyle s_{n}=\lambda _{1}\cdot \lambda _{2}\cdot \ldots \cdot \lambda _{n}=\det A}$ — определитель матрицы.

Для удобства вводится ${\displaystyle s_{0}=1}$ и введём вспомогательную величину ${\displaystyle f_{k}^{m}}$, такую что

${\displaystyle 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}}$.

С учётом ${\displaystyle \mathrm {tr} A^{m}=\sum _{j=1}^{n}\lambda _{j}^{m}}$, можно выразить

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

${\displaystyle 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}}$

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

${\displaystyle {\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}}}$

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