RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления





Для просмотра файлов Вам могут потребоваться






Семинар «Актуальные проблемы дискретной математики»
29 марта 2016 г. 14:10, г. Москва, МИАН, ул. Губкина, д. 8
 


Синтез низкоресурсного линейного автомата с заданным характеристическим многочленом

В. О. Дрелихов
Материалы:
Adobe PDF 191.7 Kb

Количество просмотров:
Эта страница:85

В. О. Дрелихов
Фотогалерея

Аннотация: Формулировка задачи о выборе матрицы с заданным характеристическим многочленом, допускающей простую и быструю реализацию умножения вектора на неё для различных вычислительных платформ.
Задан характеристический многочлен $f(x)$, $\deg f=n$, «общего вида» над $GF(q)$, $q>2$. Требуется разработать алгоритм (работающий «быстро» при больших $n$) нахождения матрицы $A$ над полем $GF(q)$ размера $n\times n$, удовлетворяющей условиям:
  • $f(x)=\|xE_n-A\|$, где $E_n$ – единичная матрица размера $n\times n$;
  • в каждой строке и в каждом столбце должно быть не более трех ненулевых элементов поля $GF(q)$.

Случаи, представляющие особый практический интерес. Матрица трехдиагональная (линейный клеточный автомат), при этом: либо многочлен $f(x)$ неприводим, либо $f(x)=f_1(x)f_2(x)$, где многочлены $f_1(x)$, $f_2(x)$ неприводимы.
Для случая $q=2$ задача уже имеет решение (т.е. алгоритм построения трехдиагональной матрицы по заданному характеристическому многочлену).

Материалы: Дрелихов.pdf (191.7 Kb)

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017