Jump to content

Samuelson–Berkowitz algorithm

From Wikipedia, the free encyclopedia

In mathematics, the Samuelson–Berkowitz algorithm efficiently computes the characteristic polynomial of an 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

[edit]

The Samuelson–Berkowitz algorithm applied to a matrix produces a vector whose entries are the coefficient of the characteristic polynomial of . It computes this coefficients vector recursively as the product of a Toeplitz matrix and the coefficients vector an principal submatrix.

Let be an matrix partitioned so that

The first principal submatrix of is the matrix . Associate with the Toeplitz matrix defined by

if is ,

if is , and in general

That is, all super diagonals of consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of and the th subdiagonal consists of .

The algorithm is then applied recursively to , producing the Toeplitz matrix times the characteristic polynomial of , etc. Finally, the characteristic polynomial of the matrix is simply . The Samuelson–Berkowitz algorithm then states that the vector defined by

contains the coefficients of the characteristic polynomial of .

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

References

[edit]
  • Berkowitz, Stuart J. (30 March 1984). "On computing the determinant in small parallel time using a small number of processors". Information Processing Letters. 18 (3): 147–150. doi:10.1016/0020-0190(84)90018-8.
  • Soltys, Michael; Cook, Stephen (December 2004). "The Proof Complexity of Linear Algebra" (PDF). Annals of Pure and Applied Logic. 130 (1–3): 277–323. CiteSeerX 10.1.1.308.6521. doi:10.1016/j.apal.2003.10.018.
  • Kerber, Michael (May 2006). Division-Free computation of sub-resultants using Bezout matrices (PS) (Technical report). Saarbrucken: Max-Planck-Institut für Informatik. Tech. Report MPI-I-2006-1-006.