Samuelson–Berkowitz algorithm

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.