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

Алгоритм Чанки — это алгоритм, позволяющий решать задачу вычисления определителя матрицы в классе 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\le i\le m$, $1\le j\le p$.

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

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

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

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

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

$𝐋=\left(\begin{array}{cc}{𝐋}_{1,1}& 0\\ {𝐋}_{2,1}& {𝐋}_{2,2}\end{array}\right)$,

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

${𝐋}^{-1}=\left(\begin{array}{cc}{𝐋}_{1,1}^{-1}& 0\\ {\mathbf{-}𝐋}_{2,2}^{-1}{𝐋}_{2,1}^{}{𝐋}_{1,1}^{-1}& {𝐋}_{2,2}^{-1}\end{array}\right)$.

Это означает, что задачу обращения матрицы $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)\le 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{array}{c}\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{array}$,

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

$s_1={\lambda }_1+{\lambda }_2+\dots +{\lambda }_n=\mathrm{t}\mathrm{r}A$ — след матрицы,

$s_n={\lambda }_1\cdot {\lambda }_2\cdot \dots \cdot {\lambda }_n=\det A$ — определитель матрицы.

Для удобства вводится $s_0=1$ и введём вспомогательную величину $f_k^m$, такую что

$f_k^m=\sum _{\genfrac{}{}{0ex}{}{1\le i_1<i_2<\dots <i_k\le n}{j\notin \{i_1,i_2,\dots ,i_k\}}}({\lambda }_{i_1}\cdot {\lambda }_{i_2}\cdot \dots \cdot {\lambda }_{i_k})\cdot {\lambda }_j^m$.

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

$\begin{array}{c}{s}_k\cdot \mathrm{t}\mathrm{r}{A}^m=(\sum _{1\le i_1<i_2<\dots <i_k\le n}{\lambda }_{i_1}\cdot {\lambda }_{i_2}\cdot \dots \cdot {\lambda }_{i_k})\cdot \left(\sum _{j=1}^n{\lambda }_j^m\right)=\sum _{\genfrac{}{}{0ex}{}{1\le i_1<i_2<\dots <i_k\le n}{1\le j\le n}}({\lambda }_{i_1}\cdot {\lambda }_{i_2}\cdot \dots \cdot {\lambda }_{i_k})\cdot {\lambda }_j^m=\\ =\sum _{\genfrac{}{}{0ex}{}{1\le i_1<i_2<\dots <i_k\le n}{j\notin \{i_1,i_2,\dots ,i_k\}}}({\lambda }_{i_1}\cdot {\lambda }_{i_2}\cdot \dots \cdot {\lambda }_{i_k})\cdot {\lambda }_j^m+\sum _{\genfrac{}{}{0ex}{}{1\le i_1<i_2<\dots <i_k\le n}{j\in \{i_1,i_2,\dots ,i_k\}}}({\lambda }_{i_1}\cdot {\lambda }_{i_2}\cdot \dots \cdot {\lambda }_{i_k})\cdot {\lambda }_j^m=f_k^m+f_{k-1}^{m+1}\end{array}$

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

$\begin{array}{cc}& s_k\cdot \mathrm{t}\mathrm{r}{A}^0-s_{k-1}\cdot \mathrm{t}\mathrm{r}{A}^1+s_{k-2}\cdot \mathrm{t}\mathrm{r}{A}^2+\dots +(-1{)}^{k-1}{s}_1\cdot \mathrm{t}\mathrm{r}{A}^{k-1}+(-1{)}^k\mathrm{t}\mathrm{r}{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)+\dots +(-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)+\dots +(-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{array}$

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

$k{s}_k-s_{k-1}\cdot \mathrm{t}\mathrm{r}{A}^1+s_{k-2}\cdot \mathrm{t}\mathrm{r}{A}^2+\dots +(-1{)}^{k-1}{s}_1\cdot \mathrm{t}\mathrm{r}{A}^{k-1}=(-1{)}^{k-1}\mathrm{t}\mathrm{r}{A}^k$

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

$\left(\begin{array}{cccccc}1& 0& 0& \dots & 0& 0\\ -\mathrm{t}\mathrm{r}A& 2& 0& \dots & 0& 0\\ \mathrm{t}\mathrm{r}{A}^2& -\mathrm{t}\mathrm{r}A& 3& \dots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ (-1{)}^{n-2}\mathrm{t}\mathrm{r}{A}^{n-2}& (-1{)}^{n-3}\mathrm{t}\mathrm{r}{A}^{n-3}& (-1{)}^{n-4}\mathrm{t}\mathrm{r}{A}^{n-4}& \dots & (n-1)& 0\\ (-1{)}^{n-1}\mathrm{t}\mathrm{r}{A}^{n-1}& (-1{)}^{n-2}\mathrm{t}\mathrm{r}{A}^{n-2}& (-1{)}^{n-3}\mathrm{t}\mathrm{r}{A}^{n-3}& \dots & -\mathrm{t}\mathrm{r}A& n\end{array}\right)\left(\begin{array}{c}{s}_1\\ s_2\\ s_3\\ ⋮\\ s_{n-1}\\ s_n\end{array}\right)=\left(\begin{array}{c}\mathrm{t}\mathrm{r}A\\ -\mathrm{t}\mathrm{r}{A}^2\\ \mathrm{t}\mathrm{r}{A}^3\\ ⋮\\ (-1{)}^{n-2}\mathrm{t}\mathrm{r}{A}^{n-1}\\ (-1{)}^{n-1}\mathrm{t}\mathrm{r}{A}^n\end{array}\right)$

Для решения этой системы нужно обратить нижнетреугольную матрицу в левой части и умножить её на столбец из правой — все эти операции вместе с одновременным вычислением значений вида $\mathrm{t}\mathrm{r}{A}^k$ для всех $k\in \{1,2,\dots ,n\}$ могут быть выполнены за время $O({\log }^{2}n)$ с использованием $O(n^4)$ процессоров. Получив решение $s={\left(\begin{array}{cccc}{s}_1& s_2& \dots & s_n\end{array}\right)}^T$, остаётся лишь взять последний элемент $s_n$, который равен искомому $\det A$.

Литература

• Шаблон:Citation
• Шаблон:Книга