Samuelson–Berkowitz algorithm

{{Short description|Method for matrix characteristic polynomials}}

{{Expand German|Algorithmus von Samuelson-Berkowitz|date=July 2020}}

In mathematics, the Samuelson–Berkowitz algorithm efficiently computes the characteristic polynomial of an $n\times n$ matrix whose entries may be elements of any unital commutative ring. Unlike the Faddeev–LeVerrier algorithm, it performs no divisions, so may be applied to a wider range of algebraic structures.

Description of the algorithm

The Samuelson–Berkowitz algorithm applied to a matrix $A$ produces a vector whose entries are the coefficient of the characteristic polynomial of $A$ . It computes this coefficients vector recursively as the product of a Toeplitz matrix and the coefficients vector an $(n-1)\times(n-1)$ principal submatrix.

Let $A_0$ be an $n\times n$ matrix partitioned so that

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

The first principal submatrix of $A_0$ is the $(n-1)\times(n-1)$ matrix $A_1$ . Associate with $A_0$ the $(n+1)\times n$ Toeplitz matrix $T_0$

defined by

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

if $A_0$ is $1\times 1$ ,

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

if $A_0$ is $2\times 2$ ,

and in general

: $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_1C & -RC & -a_{1,1} & 1 & \cdots\\
-RA_1^2C & -RA_1C & -RC & -a_{1,1} & \cdots\\
\vdots & \vdots & \vdots & \vdots & \ddots
\end{array} \right]$

That is, all super diagonals of $T_0$ consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of $-a_{1,1}$ and the $k$ th subdiagonal

consists of $-RA_1^{k-2}C$ .

The algorithm is then applied recursively to $A_1$ , producing the Toeplitz matrix $T_1$ times the characteristic polynomial of $A_2$ , etc. Finally, the characteristic polynomial of the $1\times 1$ matrix $A_{n-1}$ is simply $T_{n-1}$ . The Samuelson–Berkowitz algorithm then states that the vector $v$ defined by

: $v=T_0 T_1 T_2\cdots T_{n-1}$

contains the coefficients of the characteristic polynomial of $A_0$ .

Because each of the $T_i$ may be computed independently, the algorithm is highly parallelizable.

References

{{cite journal |first=Stuart J. |last=Berkowitz |title=On computing the determinant in small parallel time using a small number of processors |journal=Information Processing Letters |volume=18 |issue=3 |date=30 March 1984 |pages=147–150 |doi=10.1016/0020-0190(84)90018-8}}
{{cite journal |last2=Cook |first2=Stephen |last1=Soltys |first1=Michael |title=The Proof Complexity of Linear Algebra |journal=Annals of Pure and Applied Logic |volume=130 |issue=1–3 |date=December 2004 |pages=277–323 |doi=10.1016/j.apal.2003.10.018 |citeseerx=10.1.1.308.6521 |url=http://prof.msoltys.com/wp-content/uploads/2015/04/soltys-cook-apal.pdf}}
{{cite tech report |first=Michael |last=Kerber |title=Division-Free computation of sub-resultants using Bezout matrices |id=Tech. Report MPI-I-2006-1-006 |publisher=Max-Planck-Institut für Informatik |location=Saarbrucken |date=May 2006 |url=https://pure.mpg.de/pubman/faces/ViewItemOverviewPage.jsp?itemId=item_1819171 |format=PS}}

Category:Linear algebra

Category:Polynomials

Category:Numerical linear algebra