Вопрос по permutation, sparse-matrix, algorithm, combinatorics – Минимальный заказ плитки

4
Minimizing Tile Re-ordering Problem:

Предположим, у меня была следующая симметричная матрица 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

Кривая Гильберта: Hilbert Curve

RCM: RCM

Кривая Мортона: Morton Curve

@BobBryan Лучший способ проиллюстрировать вышесказанное - рассмотреть список соседних кортежей: (1,2) (2,9) (4,5) (4,6) (5,8) (7,8), эти симметричны, поэтому подразумевается, что существует (2,1) (9,2) (5,4) и т. д. Обе матрицы представляют этот список соседей. proteneer
@proteneer: Можете ли вы быть более конкретным, когда говорите кривую Мортона? Это кривая z-порядка или только 4 копии кривой Гильберта, соединяющиеся вместе с именем кривой-демона в честь американского mathemacien? Bytemain
В общем, очень сложно (и почти невозможно) для одного свопа столбца / строки улучшить счет, где счет - это число TxT-фрагментов, которые нужно вычислить. В реальных ситуациях большинство плиток уже имеют по меньшей мере две единицы. Один своп, вероятно, никогда не сможет удалить плитку. Лучшая функция подсчета очков, безусловно, поможет. proteneer
Просто первая мысль (у меня еще не было моего первого кофе, так что не ожидайте многого) - если алгоритм жадного переупорядочения не является оптимальным, моделируемый отжиг часто дает хорошие результаты. То есть для каждого возможного «перемещения» (из столбца / строки), сколько улучшений вы получаете? Rafe
Когда вы говорите «Впрочем, если я поменяю местами 3-й и 9-й столбцы (и вместе со строками, так как это симметричная матрица), переставив мои входные данные». Вы имеете в виду, что любой заданный ряд можно поменять местами с другим? Имеет ли значение, если столбец в каждой строке, подлежащей обмену, уже был заменен? Кроме того, в вашем примере, когда столбец 3 поменялся местами со столбцом 9 - значения x, по-видимому, не были поменяны местами, а затем были указаны нули для значений x, которые были в столбце 3 и теперь находятся в столбце 9. Итак, если столбец 8 должны были поменяться местами с колонкой 1, это будет разрешено? Bob Bryan

Ваш Ответ

2   ответа
0

такую как kd-tree, R-tree, quadtree или кривую заполнения пространства. Особенно полезна кривая заполнения пространства, потому что она уменьшает размер, а также переупорядочивает плитки и, таким образом, может добавлять некоторую новую информацию в сетку. С сеткой 9x9, вероятно, хорошо смотреть на кривые Пеано. Кривая демонов z порядка лучше для мощности 2 сеток.

3

которые вы можете попробовать (некоторые из них у вас есть, но все же):

(Reverse) Cuthill-McKee reduced the matrix bandwidth, keeping the entries close to the diagonal. Approximage Minimum Degree - a light-weight fill-reducing reordering. fill-reducing reordering for sparse LU/LL' decomposition (METIS, SCOTCH) - quite computationally heavy. space filling curve reordering (something in these lines) quad-trees for 2D or oct-trees for 3D problems - you assign the particles to quads/octants and later number them according to the quad/octant id, similar to space filling curves in a sense. Self Avoiding Walk is used on structured grids to traverse the grid points in such order that all points are only visited once a lot of research in blocking of the sparse matrix entries has been done in the context of Sparse Matrix-Vector multiplication. Many of the researchers have tried to find good reordering for that purpose (I do not have the perfect overview on that subject, but have a look at e.g. this paper)

Все они имеют тенденцию находить структуру в вашей матрице и в некотором смысле группировать ненулевые записи. Поскольку вы говорите, что имеете дело с частицами, это означает, что ваш граф связности в некотором смысле «локальный». из-за пространственной локальности взаимодействия частиц. В этом случае эти методы должны быть полезны.

Конечно, они не дают точного решения проблемы :) Но они обычно используются именно в таких случаях, потому что они дают очень хорошие изменения порядка на практике. Интересно, что вы имеете в виду, говоря, что методы, которые вы попробовали, потерпели неудачу? Ожидаете ли вы найти оптимальное решение? Конечно, они улучшают ситуацию по сравнению со случайным упорядочением матриц.

Edit Позвольте мне кратко просмотреть несколько фотографий. Я создал трехмерную структурированную декартову сетку, состоящую из кирпичных элементов с 20 узлами. Я подобрал размер меша так, чтобы он был похож на ваш (~ 1000 узлов). Кроме того, число ненулевых записей в строке не слишком далеко (51-81 в моем случае, 59-81 в вашем случае, однако оба имеютvery различные распределения) На рисунках ниже показаны переупорядочения RCM и METIS для непериодической сетки (слева) и для сетки с полной периодичностью x-y-z (справа):RCM reordering

На следующем рисунке показана та же матрица, переупорядоченная с использованием METIS и переупорядочения с уменьшением заполнения

metis reordering

Разница поразительна - плохое влияние периодичности очевидно. Теперь ваша матрица переупорядочена с помощью RCM и METIS

enter image description here

ВОТ ЭТО ДА. У вас есть проблема :) Во-первых, я думаю, что с вашим rcm что-то не так, потому что мой выглядит иначе;) Кроме того, я уверен, что вы не можете сделать ничего общего и значимого в отношении любого переупорядочения на основе этой конкретной матрицы. Это потому, что размер вашей системыvery маленький (менее примерно 10x10x10 точек), и вы, кажется, имеете относительно дальние взаимодействия между вашими частицами. Следовательно, введение периодичности в такую маленькую систему оказывает гораздо более сильное негативное влияние на переупорядочение, чем в моем структурированном случае.

Я бы начал поиск хорошего переупорядочения, отключив периодичность. Как только у вас есть порядок, который вас устраивает, вводите периодические взаимодействия. В показанной вами системе практически ничего нетbut периодичность: потому что она очень мала и потому, что ваши взаимодействия довольно большие, по крайней мере, по сравнению с моей сеткой. В гораздо больших системах периодичность будет оказывать меньшее влияние на центр модели.

Меньше, но все же отрицательно. Может быть, вы могли бы изменить свой подход к периодичности? Вместо явного включения периодических связей в матрицу, построить и переупорядочить матрицу без таковых и ввести явные уравнения, связывающие периодические частицы вместе, например:

V_particle1 = V_particle100

или другими словами

V_particle1 - V_particle100 = 0

и добавьте эти уравнения в конце вашей матрицы. Этот метод называется множителями Лагранжа. Вот как это выглядит для моей системы

enter image description here

Вы сохраняете переупорядочение непериодической системы, и периодические соединения локализуются в блоке в конце матрицы. Конечно, вы можете использовать его для любых других заказов.

Следующая идея заключается в том, что вы начинаете с переупорядоченной непериодической системы и явно удаляете строки матрицы для периодических узлов, добавляя их в строки, на которые они отображаются. Вы должны, конечно, также устранить столбцы.

Можете ли вы использовать их, зависит от того, что вы делаете со своей матрицей. Например, множитель Лагранжа вводит 0 по диагонали - не все решатели, как это ..

Во всяком случае, это очень интересное исследование. Я думаю, что из-за специфики вашей проблемы (насколько я понимаю - нерегулярно размещенные частицы в 3D, с довольно дальними взаимодействиями) очень сложно сгруппировать элементы матрицы. Но мне очень любопытно, что вы в итоге делаете. Пожалуйста, дайте мне знать!

феноменальный ответ. Да, приведенный пример - немного глупый пример. Фактически это симуляция, выполненная с ~ 900 атомами в периодической рамке из 3 ангстрем с радиусом обрезания 0,8. Если я понимаю метод множителя Лагранжа, он, по-видимому, в основном делает явные копии всех атомов, периодическая копия которых взаимодействует с каким-то конкретным атомом, и развязывает его (и, кроме того, вводит новые индексы для этих замещающих копий). Теперь существуют технические ограничения для увеличения размера матрицы. Кроме того, мне любопытно увидеть количество плиток. proteneer
хм, я не слишком знаком с тем, как работают множители Лагранжа. Я должен прочитать об этом. Последний вариант кажется немного сложным, когда вы говорите «нумеру остальное», что именно остальные? Вы рассматриваете все 26 периодических изображений центрального? proteneer
Позже вечером я также опробую METIS, чтобы увидеть, как он работает в гораздо более реалистичной системе (24 тыс. Атомов, 6,223 ангстрем, 0,8 ангстрем). Я могу выслать вам дополнительную информацию (которая не имеет непосредственного отношения к этой теме), если вы отправите мне электронное письмо: proteneer на gmail dot com proteneer
Первоначально я намеревался сделать это как можно более «черным ящиком» без введения системы координат. Основная причина состоит в том, что пространство, с которым мы имеем дело, может быть периодическим (трехмерные плоские торы, топологически говоря). Это AFAIK, неизвестно, существует ли кривая заполнения пространства, которая может сохранять локальность в периодических пространствах. Кривая Гильберта (просто предполагая, что пространство непериодическое) - это то, что мы используем в настоящее время, но мы сталкиваемся с граничными проблемами. CHMK, AMD, SAW, Morton, все работают значительно хуже, чем кривая Гильберта. proteneer
@proteneer Теперь я вижу, что мой комментарий относительно нумерации сбивает с толку - я удалил его. Вчера вечером была поздняя пятница;) Я постараюсь написать что-нибудь позже сегодня вечером. Общий смысл заключается в том, что переупорядочение матрицы, которая явно включает в себя соединения между периодическими узлами, приводит к гораздо худшим переупорядочениям, чем для той же системы, только не периодическим. Следовательно, для вас может быть полезно ввести периодичность другим способом (например, множителями Лагранжа или манипулированием столбцами строк на уже переупорядоченной матрице). Но это также зависит от того, что вы позже сделаете с матрицей ...

Похожие вопросы