Алгоритм ЧанкиCsanky, L.: Almost parallel matrix inversion algorithms. SIAM 618–623 (1976) — это алгоритм, позволяющий решать задачу вычисления определителя матрицы в классе NC. Идея алгоритма состоит в том, чтобы свести исходную задачу к решению системы относительно вектора , где — нижнетреугольная матрица, которую можно обратить за время с использованием процессоров.
Параллельное возведение в степень Пусть , — матрицы размеров и соответственно. Тогда для вычисления матрицы достаточно параллельно вычислить для всех , .
Префиксные суммы в выражениях такого вида могут быть вычислены за время с применением параллельных процессоров. Таким образом, используя процессоров, можно вычислить всю матрицу за время .
Применяя схожую процедуру для вычисления , можно вычислить все степени матрицы, не превосходящие , что потребует времени и процессоров.
Здесь — время, необходимое для умножения двух квадратных матриц размера .
Обращение нижнетреугольной матрицы Нижнетреугольную матрицу размера можно разбить на равные по размеру блоки
,
тогда обратная к ней матрица примет вид
.
Это означает, что задачу обращения матрицы можно решить путём двух параллельно выполняемых обращений нижнетреугольных матриц и размера и двух последовательно выполняемых умножений.
Пусть — время, требуемое для обращения нижнетреугольной матрицы . Оно подчиняется рекуррентному соотношению
.
Выше показано, что , поэтому окончательная оценка, в силу основной теоремы о рекуррентных оценках, равна
.
Описание метода Пусть — квадратная матрица со стороной . Её характеристический многочлен имеет вид
,
где — элементарные симметрический многочлен степени , а — собственные значения матрицы . В частности,
— след матрицы, — определитель матрицы.
Для удобства вводится и введём вспомогательную величину , такую что
.
С учётом , можно выразить
Используя данное соотношение, можно записать
Таким образом, для произвольного справедливо
или в матричном виде
Для решения этой системы нужно обратить нижнетреугольную матрицу в левой части и умножить её на столбец из правой — все эти операции вместе с одновременным вычислением значений вида для всех могут быть выполнены за время с использованием процессоров. Получив решение , остаётся лишь взять последний элемент , который равен искомому .
Примечания
Литература
Категория:Параллельные алгоритмы