2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6 ... 26  След.
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение22.09.2010, 12:40 
Аватара пользователя


22/09/09

1907
y_nikolaenko в сообщении #353658 писал(а):
bin в сообщении #310516 писал(а):
Приглашаю обсудить мою статью: http://arxiv.org/abs/1004.1808v1

Несколько лет назад натолкнулся на быстрый алгоритм изоморфизма графов, который использовал вероятностную интерпретацию (помнится, порядка 10000 тысяч узлов (а может и 100000 тысяч: точно не помню) он на P4 перебирал за секунды 3: там был выложен тест). Там ни автор, ни его оппонеты так и не смогли найти пример неизоморфных графов, которые бы программа не распознала.

И Вам спасибо за интерес. Не знаю, о какой работе речь - похожих на Ваше описание довольно много. Что тут еще сказать? :-) Думаю, что ключевое отличие от моего подхода в словах "вероятностная интерпретация". Нарисовать граф в 10000 тысяч вершин вручную трудно. Наверное, их генерировали, и тут многое зависит от принципа генерации. Если генератор строил графы случайным образом, можно ждать очень долго, пока он построит что-то нетривиальное. Если графы определенного класса (например, регулярные), то, может, контр примеры лежат в другом классе и т.д. Лучше искать трудности в графах меньшего размера. А для столь больших графов будет трудно понять причину ошибки: то ли недостаток алгоритма, то ли баг в программе. Тем более трудно найти пару "неизоморфных графов, которые бы программа не распознала". Например, в химии очень популярен так назывемый индекс Хосои (полное число всех реберных паросочетаний плюс единица). Было предложено использовать его для распознавания на изоморфизм. Позже нашли три графа (у каждого 5 вершин), которые имеют один и тот же индекс Хосои. Поиск велся полным перебором химически осмысленных графов... Поэтому считаю, что в общем случае для любого алгоритма он должен не просто отвечать на вопрос "графы изоморфны?" (как делалось с индексом Хосои), а находить одно из возможных изоморфных отображений. По определению изоморфизма графов, такое отображение должно сохранять связность графа, что можно проверить очень легко (у меня это делает функция Verify). При таком подходе нужно убедиться только в том, что программа правильно распознает изоморфизм для любой пары изоморфных графов.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение23.09.2010, 07:49 
Заблокирован


18/09/10

183
bin писал(а):
...нужно убедиться только в том, что программа правильно распознает изоморфизм для любой пары изоморфных графов.

Да, они, помнится, от этой печки и плясали: сначала брали 2 одинаковых графа и у одного из них перенумеровывали узлы (там у них вроде каждый узел и ребро задавлись в виде структур: там тоже была задача, связанная с химическими формулами). В этом случае время счета у них и было максимальным. А у Вас сколько времени занимает такого типа расчет?

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение23.09.2010, 11:42 
Аватара пользователя


22/09/09

1907
y_nikolaenko в сообщении #355341 писал(а):
А у Вас сколько времени занимает такого типа расчет?

Зависит от числа вершин. Последняя на данный момент версия программы ограничена 60 вершинами. По времени это занимает от секунды до нескольких минут на Pentium-4, 3 ГГц, в режиме расчета с арифметикой многократной точности в рациональных числах. Режим расчета с плавающей точкой занимает секунду или меньше, но для некоторых графов стандартная точность extended (10 байт) оказывается недостаточной. Я намеренно не оптимизировал программу: ее основная цель - снять возможные неоднозначности и недопонимания в описании алгоритма исходным кодом. Поэтому код я пытался сделать проще и читабельнее. Цель статьи теоретическая. Для практических целей, например, для физ.-хим. СУБД высокую эффективность показывает исходный рекурсивный алгоритм, описанный в Известиях РАН (точная ссылка в Abstract статьи). Формально это алгоритм с возвратом, однако он очень шустро обрубает тупиковые ветви дерева решений, процесс измельчения разбиений носит лавинообразный характер. В статье в Известиях приводится таблица с реальным временем на решение заданий. Так, например, 84 миллиона неповторяющихся молекулярных графов были сгенерированы с применением этого алгоритма за 14 часов 42 мин. на Pentium-4, 3.2 ГГц.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение23.09.2010, 12:34 
Заблокирован


18/09/10

183
bin писал(а):
... extended (10 байт) оказывается недостаточной... Так, например, 84 миллиона неповторяющихся молекулярных графов были сгенерированы с применением этого алгоритма за 14 часов 42 мин. на Pentium-4, 3.2 ГГц.

На интеловском фортране можно и 16 байт использовать (хотя extended тоже жрет 16 байт из-за выравнивания, т.е. 6 байт вхолостую используются). А можно конкретней, сколько примерно времени оптимизированная программа будет сравнивать изоморфные связные графы с 10000 узлами, если от каждого узла отходят от 1 до 4 дуг (типа реальной химической системы со структурами узла и дуг)? И распараллеливается этот оптимизированный алгоритм или нет?

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение23.09.2010, 13:30 
Аватара пользователя


22/09/09

1907
y_nikolaenko в сообщении #355404 писал(а):
На интеловском фортране можно и 16 байт использовать (хотя extended тоже жрет 16 байт из-за выравнивания, т.е. 6 байт вхолостую используются). А можно конкретней, сколько примерно времени оптимизированная программа будет сравнивать изоморфные связные графы с 10000 узлами, если от каждого узла отходят от 1 до 4 дуг (типа реальной химической системы со структурами узла и дуг)? И распараллеливается этот оптимизированный алгоритм или нет?

Прежде всего: классическая органическая химия не имеет дела с молекулами в 10000 атомов. Если речь идет о биологических объектах или о полимерах, то это уже биохимия, молекулярная биология и химия высокомолекулярных соединений. А там применяются другие методы кодирования структуры. Специфические нотации для цепочек нуклеиновых кислот, например. Поэтому и задачу изоморфизма каких-нибудь белков (если такая задача возникает) там надо решать иными алгоритмами. Что касается полимеров, то в реальном куске искусственного полимера может и не быть двух в точности одинаковых молекул. Есть разброс молекулярной массы, на концах цепочек могут сидеть атомы разных элементов и т.д. Для таких объектов задача изоморфизма графов, наверное, неактуальна. Трудно сказать, сколько может считаться такая молекула, но уверен, что если потратить достаточно усилий на оптимизацию - очень быстро. Алгоритм хорошо распараллеливается: основные затраты времени в нем - решение систем линейных уравнений с одними и теми же коэффициентами при неизвестных, т.е. матричное умножение - классическая задача на распараллеливание. Несколько лет назад просил через Институт орг. химии Н.Д.Зелинского (РАН) у РФФИ грант на разработку параллельного алгоритма для вычислительного кластера, но не дали без объяснения причин :-(

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение23.09.2010, 13:47 
Заблокирован


18/09/10

183
Я и не имел в виду химическое соединение, а только граф, имеющий подобную структуру. И сколько примерно систем линейных уравнений и какого порядка для сравнения таких графов необходимо? И эти СЛУ всегда численно устойчивы, а то Вы про точность что-то писали?

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение23.09.2010, 14:49 
Аватара пользователя


22/09/09

1907
y_nikolaenko в сообщении #355425 писал(а):
Я и не имел в виду химическое соединение, а только граф, имеющий подобную структуру. И сколько примерно систем линейных уравнений и какого порядка для сравнения таких графов необходимо? И эти СЛУ всегда численно устойчивы, а то Вы про точность что-то писали?


С устойчивостью нормально (см.статью). Уравнений столько же, сколько у графа вершин: i-ое уравнение определяет вес i-ой вершины как среднее арифметическое начального веса этой вершины (св.член - натуральное число, изменяемое в ходе работы алгоритма) и весов соседних вершин. Если Вы возьмете такую систему и перенумеруете (переназовете) в ней неизвестные, то сранивая решения (до перенумерации и после), увидите, что погрешности округления накапливаются по-разному. Например, при решении методом Гаусса зависит, с какого неизвестного начали исключение. После публикации первой версии препринта мне прислали несколько "контр-примеров" графов ок. 50 вершин и более 500 ребер, где неподобные вершины были слишком похожи и их веса различались слишком мало для достижимой в реальности точности. Может быть, для плавающей точки поможет интервальная арифметика. Однако более привлекательным для поставленных теоретических целей мне представляется реализованные сейчас вычисления в рациональных числах. Для версии, опубликованной в Известиях, проблем с присланными графами не наблюдалось: не все вершины в них слишком похожи, и алгоритм делал лишний возврат.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение23.09.2010, 15:57 
Заблокирован


18/09/10

183
bin писал(а):
С устойчивостью нормально. Уравнений столько же, сколько у графа вершин...После публикации первой версии препринта мне прислали несколько "контр-примеров" графов ок. 50 вершин и более 500 ребер, где неподобные вершины были слишком похожи и их веса различались слишком мало для достижимой в реальности точности.

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

P.S.
Я не сомневаюсь, что Ваша статья заслуживает прочтенья. Но это не моя ипостась (просто проявляю природное любопытство): поэтому, пользуясь случаем, хочу получить ответ из первых рук.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение23.09.2010, 17:25 
Заблокирован


18/09/10

183
Да, почему я обратил внимание на решение СЛАУ: эта тема мне близка. У меня довольно плохо обусловленные задачи и я сначала пользовался сингулярным анализом, потом перешел на 4-ю точность, благо интеловский фортран это позволяет, но скорость решения катастрофически падает. И помучавшись, написал собственную программу 4-ой точности, которая соотносится со скоростью решения СЛАУ 2-ой точности как 2.5:1 (сравнение со скоростной блочной программой из Intel MKL). И даже реализовал 4-ою точность для long double, но там соотношение как 4:1: иногда и к ней приходится прибегать.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение23.09.2010, 17:54 
Аватара пользователя


22/09/09

1907
y_nikolaenko в сообщении #355467 писал(а):
Я спрашивал про число систем уравнений, а не число уравнений. И когда я писал про устойчивость, то имел в виду степень линейной зависимости строк или столбцов. И судя по всему, исходя из Вашего замечания, она может проявляться. И если я не порю чушь, то насколько.

P.S.
Я не сомневаюсь, что Ваша статья заслуживает прочтенья. Но это не моя ипостась (просто проявляю природное любопытство): поэтому, пользуясь случаем, хочу получить ответ из первых рук.


Никакой чуши нет, все вполне почтительно и вопросы совершенно закономерны :-) А Ваш вопрос я не так понял, извините. Верхняя оценка возможного числа систем $n^2+n$. Я понял, что Вы имели ввиду плохую обусловленность, что бывает при больших элементах и т.д. Думаю, что свойства, отмеченные в статье, исключают такую возможность. Если считаете, что я не прав, поясните, пожалуйста, подробнее (общая теория мне известна, но, может, я что-то не учел применительно к системе данного типа?) В предыдущем ответе я хотел сказать, что только обычных ошибок округления может оказаться достаточно. Забавные примеры на эту тему приведены в книге У.Кулиш, Д.Роц и др., Достоверные вычисления, базовые методы, М.-Ижевск: РХД, 2005, с. 37. И еще раз спасибо за вопросы - они помогут найти недоработки статьи. Про MKL: я тоже столкнулся, что моя процедура для небольших СЛАУ быстрее их. Переписывался с разработчиками, они согласились :D

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение23.09.2010, 19:20 
Заблокирован


18/09/10

183
Про анализ ошибок с плавающей точкой применительно к решению СЛАУ лучше почитать у Уилкинсона (Алгебраическая проблема собственных значений) на 200 странице, а не у Кулиша. А что касается Intel MKL, то Вы меня неправильно поняли: я говорил о больших матрицах, когда скорость процедур из этого пакета приближается к теоретически возможной.
Вы дали оценку числа СЛАУ сверху: для графа с 10000 узлами это будет многовато: пока ждешь решение, можно и состариться. Т.е. в среднем сколько надо СЛАУ решить? Я почему про эти 10000 тысяч долдоню: у меня в памяти 3 секунды отложились.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение24.09.2010, 11:48 
Аватара пользователя


22/09/09

1907
y_nikolaenko в сообщении #355553 писал(а):
Про анализ ошибок с плавающей точкой применительно к решению СЛАУ лучше почитать у Уилкинсона (Алгебраическая проблема собственных значений) на 200 странице, а не у Кулиша. А что касается Intel MKL, то Вы меня неправильно поняли: я говорил о больших матрицах, когда скорость процедур из этого пакета приближается к теоретически возможной.
Вы дали оценку числа СЛАУ сверху: для графа с 10000 узлами это будет многовато: пока ждешь решение, можно и состариться. Т.е. в среднем сколько надо СЛАУ решить? Я почему про эти 10000 тысяч долдоню: у меня в памяти 3 секунды отложились.


Про анализ ошибок с плавающей точкой применительно к решению СЛАУ лучше почитать не у Кулиша, у Кулиша пара прстеньких, но поучительных примеров, в которых мы получаем результаты, где нет ни одной верной цифры :D Мне показалось интересным, что Intel MKL показывает не лучшее время как для больших, так и для малых матриц, т.е. она для "средних". Это, наверное, удел всех универсальных библиотек. В статье в Известиях для 10 тыс. пар изоморфных случайных графов с числом вершин 40 потребовалось решать СЛАУ не более 6 раз для каждого графа. Это доли секунды. Всего же было испытано 95 млн. молекул с числом атомов углерода до 60. Ни в одном испытании не было зафиксировано достижения оценки $n^2+n$, т.о. она маловероятна. Однако еще раз повторю: вопросы практики не соответствуют теоретической цели обсуждаемой здесь работы. Цель в том, чтобы доказать возможность тестирования графов на изоморфизм за полиномиальное время, и успеет ли наблюдатель состариться, тестируя какой-либо граф, теорию в данном случае не интересует. Даже для очень быстрых алгоритмов на графах всегда можно взять такое $n$, что реальное время работы будет заведомо превышать время жизни наблюдателя ;-)

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение24.09.2010, 13:10 
Заблокирован


18/09/10

183
bin писал(а):
Про анализ ошибок с плавающей точкой применительно к решению СЛАУ лучше почитать не у Кулиша, у Кулиша пара прстеньких, но поучительных примеров, в которых мы получаем результаты, где нет ни одной верной цифры

Ну, это примерно тоже, что теорию суперструн на пальцах объяснять. Таких специалистов типа Гордона сейчас много развелось. Эти примеры неискушенных читателей вводят только в заблуждение.

bin писал(а):
Мне показалось интересным, что Intel MKL показывает не лучшее время как для больших, так и для малых матриц, т.е. она для "средних". Это, наверное, удел всех универсальных библиотек.

Это не соответствует действительности: большие объемы генерируемого кода при использовании Intel MKL (например, при перемножении матриц несколько мегабайт: из-за этого умножения код для решения СЛАУ получается таким раздутым) объясняется тем, что оптимизация проводится для целого семейства процессоров (не Celeron: эти дешевые поделки не включены в оптимизацию, а может я и ошибаюсь, но для них приличной скорости нельзя добиться по опредедению). Я на решении СЛАУ "собаку съел" и знаю, о чем говорю. Для матриц, начиная примерно с 1000*1000 код работает на пределе теоретических возможностей.

bin писал(а):
В статье в Известиях для 10 тыс. пар изоморфных случайных графов с числом вершин 40 потребовалось решать СЛАУ не более 6 раз для каждого графа.;-)

Да, для больших графов от Вашего, наверное, теоретически полезного алгоритма, толку мало. А жаль.

bin писал(а):
Однако еще раз повторю: вопросы практики не соответствуют теоретической цели обсуждаемой здесь работы. Цель в том, чтобы доказать возможность тестирования графов на изоморфизм за полиномиальное время, и успеет ли наблюдатель состариться, тестируя какой-либо граф, теорию в данном случае не интересует. Даже для очень быстрых алгоритмов на графах всегда можно взять такое $n$, что реальное время работы будет заведомо превышать время жизни наблюдателя

Просто в данном разделе рассматриваются задачи, лежащие в основном в практической плоскости. Поэтому меня и интересовала возможность практического применения данного алгоритма.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение24.09.2010, 14:38 
Аватара пользователя


22/09/09

1907
Цитата:
Да, для больших графов от Вашего, наверное, теоретически полезного алгоритма, толку мало. А жаль.


Это заявление явно преждевременно. Просто пока задача практического применения данного алгоритма к большим графам не ставилась. Если проделать соответствующую работу, может получится и очень хороший результат. Кроме того, с чем сравнивать? С неким известным по Вашим неточным воспоминаниям вероятностным (т.е. приближенным?) алгоритмом? А вот потянут ли такой граф хорошо известные и зарекомендовавшие себя алгоритмы типа Nauty и за какое время?

Цитата:
Просто в данном разделе рассматриваются задачи, лежащие в основном в практической плоскости.


Если не ошибаюсь, раздел называется Computer Science, так ведь Computer Science не только практическая, но и теоретическая. И сколько я мог видеть, в этом разделе обсуждают не только практические темы. Да и данное обсуждение начиналось на теоретическом уровне - посмотрите первые страницы.

Цитата:
Я на решении СЛАУ "собаку съел" и знаю, о чем говорю.


Ну а раз так, то просмотрите, пожалуйста, мою статью и скажите, в чем по-Вашему я допустил неточности, ошибки на уровне доказательств свойств СЛАУ этого типа. А может, Вам удастся предложить лучшее доказательство?

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение24.09.2010, 16:01 
Заблокирован


18/09/10

183
bin в сообщении #355782 писал(а):
Цитата:
Я на решении СЛАУ "собаку съел" и знаю, о чем говорю.


Ну а раз так, то просмотрите, пожалуйста, мою статью и скажите, в чем по-Вашему я допустил неточности, ошибки на уровне доказательств свойств СЛАУ этого типа. А может, Вам удастся предложить лучшее доказательство?

Я отметил Ваши существенные неточности в отношении пакета Intel MKL и не более того.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 380 ]  На страницу Пред.  1, 2, 3, 4, 5, 6 ... 26  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group