New Deterministic Parallel Algorithms for the Characteristic Polynomial of a Matrix over Abstract Fields
Victor Pan
We study deterministic parallel computation of the characteristic polynomial of an $n \times n$ matrix $A$ over an arbitrary field $F$ of a positive characteristic $c \le 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 \ge c-1$ in the space of $ n\times n$ matrices. Our techniques of the algorithm design may be of independent interest.