Алгоритм Самуэльсона – Берковица

В математике алгоритм Самуэльсона – Берковица эффективно вычисляет характеристический многочлен $n\times n$ матрица, элементы которой могут быть элементами любого коммутативного кольца с единицей . В отличие от алгоритма Фаддеева – Леверье , он не выполняет деления, поэтому может применяться к более широкому кругу алгебраических структур.

Описание алгоритма

Алгоритм Самуэльсона – Берковица, примененный к матрице $A$ создает вектор, элементы которого являются коэффициентом характеристического полинома $A$. Он вычисляет этот вектор коэффициентов рекурсивно как произведение матрицы Теплица и вектора коэффициентов an. $(n-1)\times (n-1)$ главная подматрица .

Позволять $A_{0}$ быть $n\times n$ матрица разбита так, что

$A_{0}=\left[{\begin{array}{c|c}a_{1,1}&R\\\hline C&A_{1}\end{array}}\right]$

Первая главная подматрица $A_{0}$ это $(n-1)\times (n-1)$ матрица $A_{1}$. Связаться с $A_{0}$ тот $(n+1)\times n$ Матрица Теплица $T_{0}$ определяется

$T_{0}=\left[{\begin{array}{c}1\\-a_{1,1}\end{array}}\right]$

если $A_{0}$ является $1\times 1$,

$T_{0}=\left[{\begin{array}{c c}1&0\\-a_{1,1}&1\\-RC&-a_{1,1}\end{array}}\right]$

если $A_{0}$ является $2\times 2$, и вообще

$T_{0}=\left[{\begin{array}{c c c c c}1&0&0&0&\cdots \\-a_{1,1}&1&0&0&\cdots \\-RC&-a_{1,1}&1&0&\cdots \\-RA_{1}C&-RC&-a_{1,1}&1&\cdots \\-RA_{1}^{2}C&-RA_{1}C&-RC&-a_{1,1}&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{array}}\right]$

То есть все супердиагонали $T_{0}$ состоят из нулей, главная диагональ состоит из единиц, первая поддиагональ состоит из $-a_{1,1}$ и $k$субдиагональ состоит из $-RA_{1}^{k-2}C$.

Затем алгоритм рекурсивно применяется к $A_{1}$, создавая матрицу Теплица $T_{1}$ раз характеристический полином $A_{2}$и т. д. Наконец, характеристический полином $1\times 1$ матрица $A_{n-1}$ это просто $T_{n-1}$. Затем алгоритм Самуэльсона – Берковица утверждает, что вектор $v$ определяется

$v=T_{0}T_{1}T_{2}\cdots T_{n-1}$

содержит коэффициенты характеристического многочлена $A_{0}$.

Потому что каждый из $T_{i}$ могут быть вычислены независимо, алгоритм легко распараллеливается .

Ссылки

• Берковиц, Стюарт Дж. (30 марта 1984 г.). «О вычислении определителя за малое параллельное время с использованием небольшого количества процессоров». Письма об обработке информации . 18 (3): 147–150. дои : 10.1016/0020-0190(84)90018-8 .
• Солтыс, Майкл; Кук, Стивен (декабрь 2004 г.). «Сложность доказательства линейной алгебры» (PDF) . Анналы чистой и прикладной логики . 130 (1–3): 277–323. CiteSeerX   10.1.1.308.6521 . дои : 10.1016/j.apal.2003.10.018 .
• Кербер, Майкл (май 2006 г.). Вычисление промежуточных результатов без деления с использованием матриц Безу (PS) (Технический отчет). Саарбрюкен: Институт Макса Планка по информатике. Тех. Отчет MPI-I-2006-1-006.