Talk:Faddeev–LeVerrier algorithm

Efficiency

The claim about efficiency of this method is highly misleading. As presented there is reccurence which requires N steps, so on machine with infintely many processors it still need linear (in dimension N) time. NC class requires polylogaritmic time on such machine, so it is clearly not in NC. Determinant of a matrix is obtaned from constant term of characteristic polynomial, so clearly any method of computing characteristic polynomial has at least as big complexity as best method for computing determinats. Naive computation of characteristic polynomial via determiant is problematic because of need for symbolic comptation.

On the other hand, characteristic polynomial can be computed by N determiant calculations of matrices I\lambda_j - A using different \lambda_j from the same set as coefficients of A (if A has coefficients ins small finite field to get N distinct values we may be forced to slightly enlarge the field, this may cause logartimic in N increase in work, but does not change essence of following argument). The N determiant calculations can go in parallel. Next interpolation can reconstruct characteristic polynomial. Interpolation in NC so given NC algortithm for determiants one can easily create NC algorithm for characteristic polynomial.

I do not add this to main body because it may violate "no original work" clause: it contains simple reasoning for which I have no reference (and whoever wrote this article apparently missed it). If deemed trivial enough I can add it to the article. Alternatively I would propose delete misleading statements.

Extra: There is simple method of computing characteristic polynomial of numeric matrices with cost essentialy of the same order as computing single determinant and compared to that Faddeev–LeVerrier method has much higher cost on sequential machine. The efficient sequential method is old Ralston numeric analysis book. 156.17.86.7 11:07, 26 January 2021‎