53077

Автор(ы): 

Автор(ов): 

2

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

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

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

Название: 

Large-Scale Problems with Quasi-Block Matrices

ISBN/ISSN: 

1064-2307

DOI: 

10.1134/S1064230719040099

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

  • Journal of Computer and Systems Sciences International

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

Volume 58, Issue 4

Город: 

  • Moscow

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

  • PLEIADES PUBLISHING Ltd.

Год издания: 

2019

Страницы: 

571–578
Аннотация
Sparse large matrices with a block-staircase and block-treelike structure are studied. They are called quasi-block matrices and consist of independent blocks that are connected to each other pairwise or in a more general fashion. The interdependence of parameters of such matrices, such as the number of nonzero elements, the number of blocks, and the matrix size, is determined. Integer programming problems with large quasi-block matrices are described. For the efficient solution of these problems, a local elimination algorithm is used. This is an iterative algorithm in which certain variables are eliminated at each step. The issues concerning the optimal elimination order are studied. This problem turns out to be exponentially complex, which is proved using a graph interpretation of the concepts of block-treelike and block-staircase structures. The complexity of the local elimination algorithm is considered. This is important for deciding which methods are better in different situations. The numerical results are presented; in particular, efficient procedures for determining the optimal elimination order are described. Special attention is given to the parallelization of particular quasi-block Boolean programming problems on a computer GRID if these problems cannot be solved on a single processor due to their large size.

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

Лемтюжникова Д.В., Леонов В.Ю. Large-Scale Problems with Quasi-Block Matrices / Journal of Computer and Systems Sciences International. Moscow: PLEIADES PUBLISHING Ltd., 2019. Volume 58, Issue 4. С. 571–578.

Публикация имеет версию на другом языке: 

Да

Связь с публикацией: