But to get the polynomial you need to take the determine of A -lambda I, which runs in n^3. Next question then why doesn’t this Berlelamp-Massey method then effectively give you determinants in n^2?

▲

shiandow 19 hours ago | parent [-]

I think it could generate the minimal polynomiale instead. Though it is curious that this would still make it faster for almost all matrices, just not guaranteed to be correct.

	▲	Chinjut 11 hours ago \| parent [-]
		Note that the article describes this Berlekamp-Massey approach as involving a step of complexity on the order of EV, which is V^3 in the worst-case. So this is only beneficial for sparse matrices. It does seem like Berlekamp-Massey is used to efficiently but non-guaranteedly compute determinants for sparse matrices, as described at https://en.wikipedia.org/wiki/Block_Wiedemann_algorithm