РЕШЕНИЕ БОЛЬШИНСТВА ЛИНЕЙНЫХ ЛОГИЧЕСКИХ УРАВНЕНИЙ НЕСОВМЕСТНОЙ СИСТЕМЫ НА СУПЕРКОМПЬЮТЕРЕ
Abstract
Рассматриваются переопределенные системы линейных логических уравнений, число уравнений в которых превышает число неизвестных. Такие системы, как правило, не имеют корней и называются поэтому несовместными. Однако и они могут быть разрешимы в определенном смысле. Например, для криптографии представляет интерес задача поиска корней, удовлетворяющих максимальному числу уравнений, или, в случае искажения правых частей уравнений, задача восстановления системы. Предлагается параллельная реализация рандомизированного алгоритма решения несовместных систем на суперкомпьютере семейства СКИФ. Приводятся результаты экспериментальных испытаний алгоритма, показывающие эффективность параллельных вычислений при решении больших систем линейных логических уравнений.
About the Authors
А. Закревский
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
Н. Торопов
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
References
1. Закревский А.Д. Комбинаторные методы оптимизации решений систем линейных логических уравнений // Вестник ТГУ. Приложение. № 6. – Сентябрь 2003. – С. 4–8.
2. Gauss C. F. Beitrage zur Theorie der algebraischen Gleichungen. – Germany, 1849.
3. Закревский А.Д., Торопов Н.Р. Полиномиальная реализация частичных булевых функций и систем. – М.: УРСС, 2003.
4. Zakrevskij A. Solution of a system of logical equations with distorted right members – when it could be found. – New Information Technologies // Proc. of the Fifth International Conference NITe’2002. – Minsk: BSEU, 2002. – Vol. 1. – Р. 54–58.
5. Закревский А.Д., Торопов Н.Р. Поиск кратчайшего решения системы линейных логических уравнений // Тр. Второй Междунар. конф. CAD DD’1997. T. 2. – Мн.: Ин-т техн. кибернетики НАН Беларуси, 1997. – С. 16–23.
6. Закревский А.Д. Эффективные методы нахождения кратчайших решений систем линейных логических уравнений // Проблемы управления. – 2003. – № 4. – С.16 – 22.
7. Zakrevskij A.D. Randomization of a parallel algorithm for solving undefined systems of linear logical equations // Proc. of the International Workshop on Discrete-Event System Design – DESDes’04. – University of Zielona Gora Press, Poland, 2004. – P. 97–102.
8. Принципы построения суперкомпьютеров семейства «СКИФ» и их реализация / С.М. Абрамов, Н.Н. Парамонов, В.В. Анищенко, С.В. Абламейко // Информатика. – 2004. – № 1. – С. 89–106.
9. Торопов Н.Р. Параллельные логико-комбинаторные вычисления в среде MPI // Информатика. – 2005. – № 3. – С. 82–90.
10. Gropp W. , Lusk E. , Skjellum A. Using MPI: Portable Parallel Programming with the Message Passing Interface. – MIT Press, 1995.
11. Шпаковский Г.И., Серикова Н.В. Программирование для многопроцессорных систем в стандарте MPI. – Мн.: БГУ, 2002. – 323 с.
Review
For citations:
, . Informatics. 2006;(1(9)):68-77. (In Russ.)
Views: 488
Email this article 