53079

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Задачи большой размерности с квазиблочными матрицами

ISBN/ISSN: 

0002-3388

Наименование источника: 

  • ИЗВЕСТИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ

Обозначение и номер тома: 

Т.6

Город: 

  • Москва

Издательство: 

  • Российская Академия наук

Год издания: 

2019

Страницы: 

74-82
Аннотация
Рассматриваются разреженные матрицы большой размерности с блочно-лестничной и с блочно-древовидной структурами. Они называются квазиблочными и состоят из независимых блоков, которые связаны попарно друг с другом или еще в более общем виде. Устанавливается зависимость параметров таких матриц, а именно количество ненулевых элементов, число блоков, размерность самих матриц. Также описываются задачи целочисленного программирования с большими матрицами квазиблочной структуры. Используется локальный элиминационный алгоритм для их эффективного решения. Метод представляет собой итеративный процесс, где на каждом шаге исключаются переменные. Изучаются вопросы оптимального порядка исключения. Эта проблема оказывается экспо- ненциально сложной, что устанавливается с помощью графовой интерпретации понятия блочно-древовидной и блочно-лестничной структур. Рассматриваются вопросы сложности локального элиминационного алгоритма. Это важно, когда возникает вопрос, что лучше, использовать этот метод или применять другие подходы. Представлены результаты численных тестирований, в частности эффективные процедуры оптимальных порядков элиминации. Особое место занимает распараллеливание на компьютерной GRID-системе конкретных квазиблочных задач булевого программирования, которые ввиду больших размерностей не могут быть решены на одном процессоре.

Библиографическая ссылка: 

Лемтюжникова Д.В., Леонов В.Ю. Задачи большой размерности с квазиблочными матрицами // ИЗВЕСТИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ. 2019. Т.6. С. 74-82.