• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

A Method for Computing the Characteristic Polynomial and Determining Semidefiniteness

Mika Hirvensalo, A Method for Computing the Characteristic Polynomial and Determining Semidefiniteness. TUCS Technical Reports 727, Turku Centre for Computer Science, 2005.

Abstract:

We point out that to determine whether a given self-adjoint
matrix <I>A</I> is positive semidefinite
is equivalent to determining whether the characteristic
polynomial of <I>A</I> is <I>alternating</I>,
and give a new algorithm for computing the characteristic
polynomial. The said algorithm uses O(<I>n</I>³ log <I>n</I>)
multiplications and additions, and one division when computing any coefficient
of the characteristic polynomial of an <I>n</I> &#215 <I>n</I> matrix.
The algorithm is essentially division-free,
and hence it can be also used to compute the determinant
for <I>n</I> &#215 <I>n</I> matrices over a great variety of commutative rings.
It takes
O(<I>n</I>³ log <I>n</I>) ring multiplications, additions, <B>Z</B>-module multiplications, and one <B>Z</B>-module
division to compute the determinant.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHirvensalo05a,
  title = {A Method for Computing the Characteristic Polynomial and Determining Semidefiniteness},
  author = {Hirvensalo, Mika},
  number = {727},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2005},
  keywords = {Determinant, Characteristic Polynomial, Positive Semidefinite, Polynomial Time},
  ISBN = {952-12-1649-2},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication