Berlekamp–Massey Algorithm
The Berlekamp–Massey algorithm finds the shortest linear recurrence of a sequence. Given a sequence of length \(n\) whose shortest linear recurrence has order \(m\), it finds the shortest linear recurrence of every prefix of the sequence in \(O(nm)\) time. In the worst case \(m = O(n)\), so the worst-case complexity of the algorithm is \(O(n^2)\).
Definition
A recurrence for a sequence \(\{a_0 \dots a_{n - 1} \}\) is a sequence \(\{r_0\dots r_m\}\) that satisfies
\(\sum_{j = 0} ^ m r_j a_{i - j} = 0, \forall i \ge m\)
where \(r_0 = 1\). The number \(m\) is called the order of the recurrence.
The shortest linear recurrence of the sequence \(\{a_i\}\) is the recurrence of smallest order.
Algorithm
Departing slightly from the definition above, we define new recurrence coefficients \(\{f_0 \dots f_{m - 1}\}\) that satisfy:
\(a_i = \sum_{j = 0} ^ {m - 1} f_j a_{i - j - 1}, \forall i \ge m\)
Clearly \(f_i = -r_{i + 1}\), and the order \(m\) is the same as in the earlier definition.
We can find the recurrence incrementally: consider the terms of \(\{a_i\}\) one by one, in order, and adjust the recurrence coefficients \(\{f_i\}\) whenever the recurrence gives a wrong value. For convenience, write \(F_i = \{f_{i, j}\}\) for the shortest linear recurrence of the first \(i\) terms.
Initially \(F_0 = \{\}\). Suppose the recurrence coefficients \(F_{i - 1}\) hold for the first \(i - 1\) terms of the sequence \(\{a_i\}\). There are two cases for the \(i\)-th term:
- The recurrence coefficients hold for \(a_i\) as well. Nothing needs adjusting: set \(F_i = F_{i - 1}\).
- The recurrence coefficients fail for \(a_i\). Then \(F_{i - 1}\) must be adjusted to obtain a new \(F_i\).
Let \(\Delta_i = a_i - \sum_{j = 0} ^ m f_{i - 1, j} a_{i - j - 1}\), the difference between \(a_i\) and the value that \(F_{i - 1}\) predicts.
If this is the first update of the recurrence coefficients, then \(a_i\) is the first nonzero term of the sequence. In that case simply let \(F_i\) consist of \(i\) copies of \(0\); this is clearly a valid shortest linear recurrence.
Otherwise, let \(k\) be the number of terms of \(\{a_i\}\) that had been considered at the last update of the recurrence coefficients. Suppose there is a sequence \(G = \{g_0 \dots g_{m' - 1}\}\) that satisfies:
\(\sum_{j = 0} ^ {m' - 1} g_j a_{i' - j - 1} = 0, \forall i' \in [m', i)\)
and also \(\sum_{j = 0} ^ {m' - 1} g_j a_{i - j - 1} = \Delta_i\). Then adding \(F_k\) and \(G\) term by term gives valid recurrence coefficients \(F_i\).
How do we construct \(G\)? One construction that works is
\(G = \{0, 0, \dots, 0, \frac{\Delta_i}{\Delta_k}, -\frac{\Delta_i}{\Delta_k}F_{k-1}\}\)
Here \(i - k - 1\) copies of \(0\) come first, and the final \(-\frac{\Delta_i}{\Delta_k} F_{k-1}\) stands for the terms of \(F_{k-1}\), each multiplied by \(-\frac{\Delta_i}{\Delta_k}\), appended to the sequence.
A direct check gives \(\sum_{j = 0} ^ {m' - 1} g_j a_{i - j - 1} = \Delta_k \frac{\Delta_i}{\Delta_k} = \Delta_i\), so this \(G\) is valid. Set \(F_i\) to the term-by-term sum of \(F_k\) and \(G\).
If you want the recurrence \(\{r_i\}\) of the original definition, negate all of \(\{f_j\}\) and insert \(r_0 = 1\) at the front.
The procedure above shows that if the shortest linear recurrence of the sequence has order \(m\), the algorithm runs in \(O(nm)\). In the worst case \(m = O(n)\), so the worst-case complexity of the algorithm is \(O(n^2)\).
In an implementation, each adjustment of the recurrence coefficients needs only the coefficients \(F_k\) from the previous adjustment. So if only the shortest linear recurrence of the whole sequence is wanted, store just the current coefficients and those from the previous adjustment; the space complexity is then \(O(n)\).
Reference implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | |
The naive Berlekamp–Massey algorithm finds the shortest linear recurrence of a finite sequence. If the sequence is infinite but an upper bound on the order of its shortest linear recurrence is known, the first \(2m\) terms are enough to find the shortest linear recurrence of the whole sequence. (Proof omitted.)
Applications
The Berlekamp–Massey algorithm has rather poor numerical stability, so it is rarely used for problems over the real numbers. To keep the exposition simple, we assume from here on that all arithmetic is done in the residue system modulo some prime \(p\).
Shortest linear recurrence of a sequence of vectors or matrices
To find the shortest linear recurrence of a sequence of vectors \(\boldsymbol{v}_i\) of dimension \(n\), pick a random \(n\)-dimensional row vector \(\mathbf u^T\) and compute the shortest linear recurrence of the scalar sequence \(\{\boldsymbol{u}^T\boldsymbol{v}_i\}\). By the Schwartz–Zippel lemma, the two shortest linear recurrences are the same with probability at least \(1 - \frac n p\).
A sequence of matrices \(\{A_i\}\) is handled in the same way. If the matrices are \(n \times m\), pick a random \(1 \times n\) row vector \(\mathbf u^T\) and a random \(m \times 1\) column vector \(\boldsymbol{v}\), and compute the shortest linear recurrence of the scalar sequence \(\{\boldsymbol{u}^T A_i \boldsymbol{v}\}\). The Schwartz–Zippel lemma shows similarly that the two are the same with probability at least \(1 - \frac{n + m} p\).
Optimizing matrix exponentiation
Let the \(\boldsymbol{f}_i\) be \(n\)-dimensional column vectors with the transition \(\boldsymbol{f}_i = A \boldsymbol{f}_{i - 1}\). Then \(\{\boldsymbol{f}_i\}\) is a linearly recurrent sequence of vectors of order at most \(n\). (Proof omitted.)
Compute \(\boldsymbol{f}_0 \dots \boldsymbol{f}_{2n - 1}\) by brute force, find the shortest linear recurrence of \(\{\boldsymbol{f}_i\}\) by the method above, and then apply the algorithm for linear homogeneous recurrences with constant coefficients.
If the vector we want is \(\boldsymbol{f}_m\), the algorithm runs in \(O(n^3 + n\log n \log m)\). If \(A\) is a sparse matrix with only \(k\) nonzero entries, this drops to \(O(nk + n\log n \log m)\). But the algorithm needs at least \(O(nk)\) time for preprocessing anyway, so when the limits are not tight you can also use the \(O(n^2 \log m)\) linear recurrence algorithm, which is fast enough as well.
Minimal polynomial of a matrix
The minimal polynomial of a square matrix \(A\) is the polynomial \(f\) of least degree that satisfies \(f(A) = 0\).
The minimal polynomial is in fact the shortest recurrence of \(\{A^i\}\), so we can call the Berlekamp–Massey algorithm directly. If \(A\) is a square matrix of order \(n\), the degree of its minimal polynomial is clearly at most \(n\).
The bottleneck is computing \(A^i\): multiplying matrices at every step would bring the complexity to \(O(n^4)\). But finding the shortest linear recurrence of a sequence of matrices really means finding that of \(\{\boldsymbol{u}^T A^i \boldsymbol{v}\}\), so we only need to compute \(A^i \boldsymbol{v}\).
If \(A\) has \(k\) nonzero entries, the complexity is \(O(kn + n^2)\).
Determinant of a sparse matrix
If we can find the characteristic polynomial of a square matrix \(A\), its constant term times \((-1)^n\) is the determinant. But the minimal polynomial is not necessarily the characteristic polynomial.
However, if we multiply \(A\) by a random diagonal matrix \(B\), the minimal polynomial of \(AB\) is the characteristic polynomial with probability at least \(1 - \frac {2n^2 - n} p\). Finally, divide by \(\text{det}\;B\).
If \(A\) is a square matrix of order \(n\) with \(k\) nonzero entries, the complexity is \(O(kn + n ^ 2)\).
Rank of a sparse matrix
Let \(A\) be an \(n\times m\) matrix. Pick a random \(n\times n\) diagonal matrix \(P\) and a random \(m\times m\) diagonal matrix \(Q\), then compute the minimal polynomial of \(P A Q A^T P\).
There is no need to multiply the matrices together: finding the minimal polynomial only requires multiplying \(P A Q A^T P\) by a vector, so we apply these matrices to the vector one after another. The answer is the degree that remains after every factor \(x\) is divided out of the minimal polynomial.
If \(A\) has \(k\) nonzero entries and \(n \le m\), the complexity is \(O(kn + n ^ 2)\).
Solving a sparse system of equations
Problem: Consider \(A \mathbf x = \mathbf b\), where \(A\) is an \(n \times n\) sparse matrix of full rank, and \(\mathbf b\) and \(\mathbf x\) are \(n\times 1\) column vectors. Given \(A, \mathbf b\), solve for \(x\) with complexity below \(n^\omega\).
Solution: Clearly \(\mathbf x = A^{-1} \mathbf b\). If we can find the shortest recurrence \(\{r_0 \dots r_{m - 1}\}\) (\(m \le n\)) of \(\{A^i \mathbf b\}\) (\(i \ge 0\)), then we have
\(A^{-1} \mathbf b = -\frac 1 {r_{m - 1}} \sum_{i = 0} ^ {m - 2} A^i \mathbf b r_{m - 2 - i}\)
(Proof omitted.)
Since \(A\) is sparse, compute \(\mathbf b \dots A^{2n - 1} \mathbf b\) one after another, straight from the definition.
Likewise, if \(A\) has \(k\) nonzero entries, the complexity is \(O(kn + n^2)\).
Reference implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | |
Example problems
- LibreOJ #163. Gaussian Elimination 2
- ICPC2021 Taipei Gym103443E. Composition with Large Red Plane, Yellow, Black, Gray, and Blue
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: AntiLeaf, 24OI-bot, Enter-tainer, Tiphereth-A, ZnPdCo, Plastic-time (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.