bin писал(а):
Про анализ ошибок с плавающей точкой применительно к решению СЛАУ лучше почитать не у Кулиша, у Кулиша пара прстеньких, но поучительных примеров, в которых мы получаем результаты, где нет ни одной верной цифры
Ну, это примерно тоже, что теорию суперструн на пальцах объяснять. Таких специалистов типа Гордона сейчас много развелось. Эти примеры неискушенных читателей вводят только в заблуждение.
bin писал(а):
Мне показалось интересным, что Intel MKL показывает не лучшее время как для больших, так и для малых матриц, т.е. она для "средних". Это, наверное, удел всех универсальных библиотек.
Это не соответствует действительности: большие объемы генерируемого кода при использовании Intel MKL (например, при перемножении матриц несколько мегабайт: из-за этого умножения код для решения СЛАУ получается таким раздутым) объясняется тем, что оптимизация проводится для целого семейства процессоров (не Celeron: эти дешевые поделки не включены в оптимизацию, а может я и ошибаюсь, но для них приличной скорости нельзя добиться по опредедению). Я на решении СЛАУ "собаку съел" и знаю, о чем говорю. Для матриц, начиная примерно с 1000*1000 код работает на пределе теоретических возможностей.
bin писал(а):
В статье в Известиях для 10 тыс. пар изоморфных случайных графов с числом вершин 40 потребовалось решать СЛАУ не более 6 раз для каждого графа.
Да, для больших графов от Вашего, наверное, теоретически полезного алгоритма, толку мало. А жаль.
bin писал(а):
Однако еще раз повторю: вопросы практики не соответствуют теоретической цели обсуждаемой здесь работы. Цель в том, чтобы доказать возможность тестирования графов на изоморфизм за полиномиальное время, и успеет ли наблюдатель состариться, тестируя какой-либо граф, теорию в данном случае не интересует. Даже для очень быстрых алгоритмов на графах всегда можно взять такое
, что реальное время работы будет заведомо превышать время жизни наблюдателя
Просто в данном разделе рассматриваются задачи, лежащие в основном в практической плоскости. Поэтому меня и интересовала возможность практического применения данного алгоритма.
Думаю, что ключевое отличие от моего подхода в словах "вероятностная интерпретация". Нарисовать граф в 10000 тысяч вершин вручную трудно. Наверное, их генерировали, и тут многое зависит от принципа генерации. Если генератор строил графы случайным образом, можно ждать очень долго, пока он построит что-то нетривиальное. Если графы определенного класса (например, регулярные), то, может, контр примеры лежат в другом классе и т.д. Лучше искать трудности в графах меньшего размера. А для столь больших графов будет трудно понять причину ошибки: то ли недостаток алгоритма, то ли баг в программе. Тем более трудно найти пару "неизоморфных графов, которые бы программа не распознала". Например, в химии очень популярен так назывемый индекс Хосои (полное число всех реберных паросочетаний плюс единица). Было предложено использовать его для распознавания на изоморфизм. Позже нашли три графа (у каждого 5 вершин), которые имеют один и тот же индекс Хосои. Поиск велся полным перебором химически осмысленных графов... Поэтому считаю, что в общем случае для любого алгоритма он должен не просто отвечать на вопрос "графы изоморфны?" (как делалось с индексом Хосои), а находить одно из возможных изоморфных отображений. По определению изоморфизма графов, такое отображение должно сохранять связность графа, что можно проверить очень легко (у меня это делает функция Verify). При таком подходе нужно убедиться только в том, что программа правильно распознает изоморфизм для любой пары изоморфных графов.
. Я понял, что Вы имели ввиду плохую обусловленность, что бывает при больших элементах и т.д. Думаю, что свойства, отмеченные в статье, исключают такую возможность. Если считаете, что я не прав, поясните, пожалуйста, подробнее (общая теория мне известна, но, может, я что-то не учел применительно к системе данного типа?) В предыдущем ответе я хотел сказать, что только обычных ошибок округления может оказаться достаточно. Забавные примеры на эту тему приведены в книге 