Алгоритм выделения блочно-древовидной структуры в разреженных задачах дискретной оптимизации

Журнал: 
Страница: 
44
УДК: 
519.658
В статье предложен алгоритм выделения блочно-древовидной структуры для разреженных матриц. Реализован в виде программы на C++ и протестирован алгоритм Финкельштейна для выделения квазиблочных структур в разрежённых матрицах. Произведен сравнительный эксперимент для модифицированной и исходной версий алгоритма, показавший существенное уменьшение количества построенных блоков и размеров сепараторов для модифицированного алгоритма Финкельштейна.
info_eng: 
Authors propose an algorithm of computing block-tree structure for sparse matrices. Finkelshtein's algorithm for constructing quasiblock structures is modified and implemented. Preliminary benchmarking with test problems was done. Quality of computed quasiblock structures is investigated.