4 ms·
Odd to use Berlelamp-Massey to recover a linear recurrence, when Cayley-Hamilton already directly gives you a linear recurrence whose characteristic polynomial
by Chinjut 1y ago
Odd to use Berlelamp-Massey to recover a linear recurrence, when Cayley-Hamilton already directly gives you a linear recurrence whose characteristic polynomial is that of the matrix.
- efavdb 1y agoBut 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 1y agoI 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 1y agoNote 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 https://en.wikipedia.org/wiki/Block_Wiedemann_algorithm
- Labo333 1y agoCH gives you recurrence on the matrix. You want recurrence on an individual element (indexed by [start][end]).
- Chinjut 1y agoAny recurrence that holds on the matrix also holds on each individual element (and vice versa, in that a recurrence holds on the matrix just in case it holds on every individual element).