NEW DETERMINISTIC PARALLEL ALGORITHMS FOR THE

CHARACTERISTIC POLYNOMIAL OF A MATRIX OVER ABSTRACT FIELDS

VICTOR PAN

Abstract. We study deterministic parallel computation of the characteristic polynomial of an n × n matrix A over an arbitrary field F of a positive characteristic c ≤ n. Our new NC algorithms run in polylogarithmic time and simultaneously enable us to decrease the known upper bounds on processor complexity by order of magnitude except for matrices A forming an algebraic variety of codimension d ≥ c − 1 in the space of n × n matrices. Our techniques of the algorithm design may be of independent interest.