Алгоритм Видемана для решения Ax = 0 за O(nk) (10 апреля 2014)

1. Ссылки
1. [Wiedemann, смотри в конце слайдов]
2. [Расширенный алгоритм Евклида для многочленов, смотри 17 главу]
3. [Что-то, что гуглится на тему Берликэмпа-Месси]
2. k − число ненулевых элементов в матрице A, пусть k ≥ n.
3. Теорема Гамильтона-Кэли: ^χ_A(A) = 0
4. Рассмотрим случайные вектора x, y. И последовательность z_k = xA^ky, k ≥ 0, первые ее m членов можно посчитать за O(mk)
5. ∀P : P(A) = 0 ⇒ xP(A)y = 0 ⇒ z_k линейно реккурентно порождена, длина рекуурентности не более n
6. Алгоритмом Берликэмпа-Месси за O(m²) найдем реккурентное соотношение. Алгоритм корректен, если m ≥ 2n.
7. w = Σq_kA^kz, w можно посчитать за O(mk), с большой вероятностью w ≠ 0
8. xAw = 0, x − случаен ⇒ с большой вероятностью Aw = 0, w − нетривиальное решение системы
9. Общее время работы: O(nk)