2014 dxdy logo

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

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




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


22/09/09

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


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

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


Полный абсурд! Я этого не говорил!
Ну, где я говорил о размерах кода MKL? Я так и не понял, что в моих словах не соответствовало действительности? Факт в том, что несколько лет назад, еще до появления многоядерных процессоров, я попробовал решать очень много небольших СЛУ (например, 8 уравнений с 8 неизвестными) в MKL. И производительность оказалась ниже, чем у написанной мной процедуры. По этому вопросу я обратился в Intel support, они не смогли мне помочь и связали с разработчиками. Я некоторое время переписывался с ними, выслал исходной код своей процедуры. Разработчики проанализировали и признали, что я сделал корректное сравнение и что для данного случая моя процедура действительно быстрее. С тех пор у меня не возникало задач, для которых могла понадобиться MKL. И что тут не соответствует действительности? И наверняка, я завел эту тему не для того, чтобы обсуждать достоинства/недостатки MKL! Что же получается: не сумели сказать что-то по существу моей статьи, зато сказали: «а он про MKL не соответствующее действительности написал». Очень мило! Больше здесь обсуждать MKL давайте не будем. Хотите, открывайте новую тему, можете и мои слова туда перенести. Но участвовать я в такой теме не смогу, потому что больше про MKL добавить мне нечего.

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


18/09/10

183
bin,

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

Я про это и говорил: я же не знал, что Вы бабушкиными алгоритмами пользовались и не следите за последними релизами.

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


22/09/09

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

Да! И не только "бабушкиными", но и алгоритмами Евклида, Эратосфена (а они мне даже в пра-пра-дедушки не годятся - слишком я для этого молод :D Впрочем, и Кнут этими алгоритмами пользуется. Что касается "последних релизов" - это недостижимая мечта индустриальных лидеров об идеальном потребителе, который каждый день с утра до полудня только и делает, что ставит очередные обновления. Наверное, Вы стремитесь к такому недостижимому идеалу, с которым и связываете оценку "собаку съел" ;-) А я-то всегда считал, что если специалист съел собаку в СЛАУ, то он может и на теоретическом уровне что-то содержательное сказать, а не только на уровне пресс-релизов. Жаль.

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


18/09/10

183
bin
Я смотрю, Вы совершенно не в теме. Пакет Intel MKL, в частности, обновляется из-за появления новых процессоров (а я ведь писал про это: для каждого нового семейства процессоров код в Intel MKL для этого самого семейства добавляется - у меня, например, сейчас процессор i7 930) и, в частности, из-за того, что обновляется и исправляется пакет LAPACK, и ... Продолжать? А Вы пробабушкины сказки рассказываете о том, что было несколько лет назад: несколько лет для компьютерной индустрии - это целая вечность. А что касается моего, как Вы выразились, "теоретического уровня", то попробуйте ответить на мой вопрос:
topic36662.html - буду Вам очень признателен.

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


22/09/09

1907
Повторяю:
Цитата:
Больше здесь обсуждать MKL давайте не будем. Хотите, открывайте новую тему

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


18/09/10

183
bin в сообщении #356054 писал(а):
Повторяю:
Цитата:
Больше здесь обсуждать MKL давайте не будем. Хотите, открывайте новую тему

Я Вас за язык не тянул: Вы сами привели свои мифические сравнения, да и по поводу "теории" мне не ответили.

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


22/09/09

1907
Здесь обсуждение: "Полиномиальный алгоритм изоморфизма графов". Не на тему здесь не отвечаю.

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


18/09/10

183
bin в сообщении #356057 писал(а):
Здесь обсуждение: "Полиномиальный алгоритм изоморфизма графов". Не на тему здесь не отвечаю.

Я не возражаю, ответьте тогда здесь: topic36662.html . Ведь Вы сами подняли вопрос про "теоретическую подкованность".

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


18/09/10

183
bin

Нашел я программу, о которой говорил (не там ранее искал: это далекий 2004 год). Я ошибался: там 1000 с небольшим узлов. На моем проце i7 930 расчет занял 0.43 с. Будет время, распараллелю.

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


22/09/09

1907
Цитата:
Нашел я программу, о которой говорил (не там ранее искал: это далекий 2004 год). Я ошибался: там 1000 с небольшим узлов. На моем проце i7 930 расчет занял 0.43 с. Будет время, распараллелю.

Очень хорошо. Однако давайте будем обсуждать здесь мой алгоритм, а не другие программы.

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


18/09/10

183
bin

Вы правы: алгоритм O(n^3) не вписывается в парадигму полиномиального алгоритма.

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


22/09/09

1907
Я понимаю, что есть привычка неторопливо формулировать свои мысли, более того есть привычка очень неторопливо формулировать свои мысли, и более того есть привычка очень-очень неторопливо формулировать свои мысли, но нельзя ли все-таки покороче? Если Вы наконец нашли понравившийся Вам алгоритм, то можно сразу дать ссылку на сокровищницу инета, где он хранится? Из того, что Вы написали ранее, я понял, что это вероятностный приближенный алгоритм. А может, он и эвристический? Но даже если он был строго доказан, почему его до сих пор не признали? С 2004 г. прошло достаточно времени? Как бы то ни было, эта тема не для того, чтобы раскапывать и обсуждать все когда-либо предложенные решения этой задачи. Эта тема значительно более узкая - обсуждение моего предложения. Большое множество других алгоритмов, а я знаю, их было предложено очень много, можете обсудить в другой теме, если есть такая охота.

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


18/09/10

183
bin

Не знаю, где он хранится. Он мне дан (исходники) на условиях нераспространения за то, что я написал для него графический интерфейс в стиле ChemDraw. Вот мне и интересно, туфта это или нет.

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


22/09/09

1907
Прошел месяц с момента, как я обновил статью “Polynomial Time Algorithm for Graph Isomorphism Testing” http://arxiv.org/abs/1004.1808. В отличие от первой версии, я до сих пор не получил сообщений о замеченных ошибках в доказательстве. Если посмотреть по этому обсуждению, для первой версии такие сообщения пришли довольно быстро. В то же время я вижу по счетчикам посещаемости как этого обсуждения, так и на других форумах и блогах (не только в зоне .ru, но и международных) - эти счетчики каждый день растут. Более того, я часто просматриваю результаты поиска по свежим публикациям на тему "Graph Isomorphism". По таким публикациям удается выяснить email авторов, и им я тоже посылал эту ссылку. Иногда ответа нет, но чаще я получаю в ответ: "Спасибо за ссылку. Это представляется потрясным результатом. Обязательно прочитаю." (Вольность в переводе слова "потрясный" :) Я, естественно, пишу "Dear Prof ... Looking forward to hear from you again!" А дальше тишина... До того, как 11 апреля я выложил первую статью на arxiv.org, я, в частности, спросил редактора одного известного международного журнала, не хочет ли он рассмотреть вопрос о публикации такой статьи, и он тогда (в числе прочих) предложил мне выложить статью на arxiv.org, "а там посмотрим на отклики". Недавно я ему написал, что по второй версии не получил никаких возражений, он тут же ответил: "When you have some well-known researchers agreeing that your proof is now correct let me know." И как тут быть? Похоже, никто из well-known researchers не хочет брать на себя ответственности в поддержке статьи на столь одиозную тему. В то же время не случайно некоторые well-known researchers попали в список благодарностей: никто из них не сказал "брось это - твой подход ошибочен в принципе" (хотя по переписке от не совсем well-known я и такие комментарии получаю, равно как и несколько преждевременные поздравления с "великой победой"). Я рад любым ВНЯТНЫМ комментариям и пишу все это с просьбой совета, как быть дальше и робкой надеждой, что, может, кто-нибудь вникнет в мои доказательства и либо не побоится признать их публично, либо укажет мне на существенные ошибки. Однако заявлениями типа: "Мне кажется, что какая-нибудь пара строгорегулярных графов окажется контр-примером" - просьба не беспокоить, такое я уже неоднократно слышал, и не только по поводу этой статьи, но и в отношении статей других авторов - это универсальное средство рецензентов-халтурщиков: как увидел слова "Graph Isomorphism", дальше можно не читать :(

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение24.10.2010, 22:37 
Модератор
Аватара пользователя


11/01/06
5660
bin
Пошлите статью в профильный реферируемый журнал. Тогда рецензенты досконально проанализируют вашу статью и либо примут к публикации, либо откажут, указав на ошибки.

-- Sun Oct 24, 2010 15:06:09 --

Например, в один из этих:
Journal of Graph Algorithms and Applications
Journal of Graph Theory
Journal of the ACM

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

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



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

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


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

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