Accurate eigenvalues and exact zero Jordan blocks of totally nonnegative matrices

摘要

We present a new algorithm which, given a bidiagonal decomposition of a totally nonnegative matrix, computes all its eigenvalues to high relative accuracy in floating point arithmetic in O(n3) time. It also computes exactly the Jordan blocks corresponding to zero eigenvalues in up to O(n4) time.