Минимальный заказ плитки
Предположим, у меня была следующая симметричная матрица 9x9, N ^ 2 взаимодействия между N частицами:
(1,2) (2,9) (4,5) (4,6) (5,8) (7,8),
Это симметричные взаимодействия, поэтому подразумевается, что они существуют:
(2,1) (9,2) (5,4) (6,4) (8,5) (8,7),
В моей задаче предположим, что они расположены в матричной форме, где показан только верхний треугольник:
t 0 1 2 (tiles)
# 1 2 3 4 5 6 7 8 9
1 [ 0 1 0 0 0 0 0 0 0 ]
0 2 [ x 0 0 0 0 0 0 0 1 ]
3 [ x x 0 0 0 0 0 0 0 ]
4 [ x x x 0 1 1 0 0 0 ]
1 5 [ x x x x 0 0 0 1 0 ]
6 [ x x x x x 0 0 0 0 ]
7 [ x x x x x x 0 1 0 ]
2 8 [ x x x x x x x 0 0 ]
9 [ x x x x x x x x 0 ] (x's denote symmetric pair)
У меня есть некоторая операция, которая вычисляется в ячейках 3х3, и любые 3х3, которые содержат хотя бы одну единицу, должны быть вычислены полностью. В приведенном выше примере требуется как минимум 5 плиток: (0,0), (0,2), (1,1), (1,2), (2,2)
Однако, если я поменяю местами 3-й и 9-й столбцы (и вместе со строками, так как это симметричная матрица), переставив входные данные:
t 0 1 2
# 1 2 9 4 5 6 7 8 3
1 [ 0 1 0 0 0 0 0 0 0 ]
0 2 [ x 0 1 0 0 0 0 0 0 ]
9 [ x x 0 0 0 0 0 0 0 ]
4 [ x x x 0 1 1 0 0 0 ]
1 5 [ x x x x 0 0 0 1 0 ]
6 [ x x x x x 0 0 0 0 ]
7 [ x x x x x x 0 1 0 ]
2 8 [ x x x x x x x 0 0 ]
3 [ x x x x x x x x 0 ] (x's denote symmetric pair)
Теперь мне нужно только вычислить 4 плитки: (0,0), (1,1), (1,2), (2,2).
Общая проблема:
Учитывая NxN разреженную матрицу, нахождение переупорядочения, чтобы минимизировать количество TxT-фрагментов, которые должны быть вычислены. Предположим, что N кратно T. Оптимальное, но неосуществимое решение можно найти, попробовав N! перестановки входного порядка.
Для эвристики я пробовал процедуры минимизации пропускной способности (такие как Reverse CutHill McKee), Tim Davis '. Подпрограммы AMD, пока безрезультатно. Я не думаю, что диагонализация - это правильный подход.
Вот пример начальной матрицы:
http://proteneer.com/misc/out2.dat
Кривая Гильберта:
RCM:
Кривая Мортона:
