Решение системы уравнений - призовой конкурс

[Eugeen1948]

Уважаемые программисты. Я наблюдал за конкурсом Zealint по матрицам и увидел много талантливых программистов.
Хочу предложить свой вариант конкурса.
1. Постановка задачи:
Есть система из 60000 линейных уравнений с разреженной матрицей.
2. Требование:
2.1. Сделать программу решения этой системы за минимальное время на одном ядре процессора Интел.
2.2. Сделать программу решения этой системы за минимальное время в принципе, с использованием одного ядра процессора Интел и одной видеоплаты с одним видеочипом.
Победителю по п. 2.1. - приз 1 000 р.
Абсолютному чемпиону (п. 2.2.) - приз 10 000 р.
Готов к обсуждению. Жду вопросов.

[drozdov_mihail]

Eugeen1948 в сообщении #488648 писал(а):

Есть система из ... линейных уравнений с разреженной матрицей.

Разреженные матрицы разные бывают: её структура напрямую связана со скоростью ее решения.

[Eugeen1948]

Не важно, какого цвета кошка, лишь бы мышей ловила (из цитатника Великого Кормчего).
Структура матрицы безобразная , никакой симметрии и антисимметрии.

[Pavia]

Eugeen1948
Только тут надо всё-таки подкорректировать условие задачи. Сколько уравнений это понятно. Но число коэффициентов вы не указали, что очень странно. Да и ограничения на коэффициенты вы не указали, толи хватит float хватит, толи double, толи длинные длинную арифметику. Тем более целые или дробные коэффициенты. Причем каково еще точность решения?

Видео карту вы не указали. А не все они в родном режиме поддерживают расчёт используя double числа.

Цитата:

одной видеоплаты с одним видеочипом

Что значит "один видеочип"?

[drozdov_mihail]

Eugeen1948 в сообщении #488662 писал(а):

Не важно, какого цвета кошка, лишь бы мышей ловила (из цитатника Великого Кормчего).
Структура матрицы безобразная , никакой симметрии и антисимметрии.

Безобразных структур не бывает: почему вы ее считаете разреженной?

[Eugeen1948]

Pavia в сообщении #488667 писал(а):

Eugeen1948
Только тут надо всё-таки подкорректировать условие задачи. Сколько уравнений это понятно. Но число коэффициентов вы не указали, что очень странно. Да и ограничения на коэффициенты вы не указали, толи хватит float хватит, толи double, толи длинные длинную арифметику. Тем более целые или дробные коэффициенты. Причем каково еще точность решения?

Видео карту вы не указали. А не все они в родном режиме поддерживают расчёт используя double числа.

Цитата:

одной видеоплаты с одним видеочипом

Что значит "один видеочип"?

Ничего страшного, сейчас уточним.

1. Все операции с двойной точностью (стандартно - 8 байт). Коэффициенты (на всякий случай уточняю -действительные, а не комплексные и не целые);
2. Степень разреженности матрицы коэф. порядка 35%;
3. Видеокарта у Вас, конечно же, должна поддерживать двойную точность. Но тип карты я специально не ограничиваю. Это может быть Nvidia или ATI. Проверить я могу на любом типе, т.к. у меня есть самые последние Nvidia GTX-580 и ATI Radeon 6970. Я понимаю, что при программировании на GPU сказываются ограничения по рангу видеочипа. По крайней мере в CUDA это явно указывается. Поэтому давайте свои предложения по процедуре сравнения. Частоты CPU и GPU условимся принимать без разгона и установим стандарт.
Про "видеочип". Есть модели карт с одним и с двумя видеочипами. Например Nvidia GTX-580 и ATI Radeon 6970 - карты с одним чипом, Nvidia GTX-590 и ATI Radeon 6990 - с двумя чипами.

-- Вс окт 02, 2011 19:38:35 --

drozdov_mihail в сообщении #488678 писал(а):

Eugeen1948 в сообщении #488662 писал(а):

Не важно, какого цвета кошка, лишь бы мышей ловила (из цитатника Великого Кормчего).
Структура матрицы безобразная , никакой симметрии и антисимметрии.

Безобразных структур не бывает: почему вы ее считаете разреженной?

В ней не более 65% ненулевых элементов.

[Zealint]

Eugeen1948,
Видите ли, в чём дело...
На вашем месте я бы максимально уточнил все условия конкурса и схему проведения. Кто и где будет тестировать? Что считать правильным ответом? Как придти к общему мнению о качествах той или иной программы, если вы не уточнили этих моментов? Куда посылать решения? Каковы вообще сроки конкурса? Каков Time Limit? Сколько памяти? Какова разрядность системы (сколько памяти можно под swap пустить)?
Короче, берите пример с моих конкурсов, по ним вопросы обычно задают только те, кто не осилил много букв. Либо вопросы носят философский характер, не относящийся к деталям проведения.

Кроме того, задача у вас слишком популярная, даже популярней перемножения матриц. Существует "дофига + 100500" методов её решения, зависящих от желаемой точности и специфики задачи, народ просто запутается, какой выбирать, а ради 10000 р. проводить полноценное научное исследование в этой области мало кто возьмется. Поэтому победителем может оказаться более удачливый. Может сузить задачу? Или, чтобы веселей было, предложить хотя бы миллион уравнений?

Если запустите конкурс, дайте знать, я у себя объявление повешу...

[Eugeen1948]

Zealint в сообщении #488737 писал(а):

Eugeen1948,
Видите ли, в чём дело...
На вашем месте я бы максимально уточнил все условия конкурса и схему проведения. Кто и где будет тестировать? Что считать правильным ответом? Как придти к общему мнению о качествах той или иной программы, если вы не уточнили этих моментов? Куда посылать решения? Каковы вообще сроки конкурса? Каков Time Limit? Сколько памяти? Какова разрядность системы (сколько памяти можно под swap пустить)?
Короче, берите пример с моих конкурсов, по ним вопросы обычно задают только те, кто не осилил много букв. Либо вопросы носят философский характер, не относящийся к деталям проведения.

Кроме того, задача у вас слишком популярная, даже популярней перемножения матриц. Существует "дофига + 100500" методов её решения, зависящих от желаемой точности и специфики задачи, народ просто запутается, какой выбирать, а ради 10000 р. проводить полноценное научное исследование в этой области мало кто возьмется. Поэтому победителем может оказаться более удачливый. Может сузить задачу? Или, чтобы веселей было, предложить хотя бы миллион уравнений?

Если запустите конкурс, дайте знать, я у себя объявление повешу...

Сейчас и идет уточнение условий конкурса. Пока не внесем полную ясность, не начнем.
Правильное решение будет представлено. Есть и проверочный тест, т.е. вторая, неизвестная участникам конкурса матрица.
Для меня важно убрать максимально какие либо ограничения, кроме тех, без которых решить задачу нельзя. Согласен, что есть много способов решения, но 90% из этих способов сразу покажут свою несостоятельность, так что здесь не всё так примитивно.
Насчет денежного приза.
Это только отборочные соревнования, если можно так сказать. Предквалификация. Следующий конкурс будет на порядок сложнее, но и приз на порядок больше!

[Zealint]

Eugeen1948 в сообщении #488766 писал(а):

Сейчас и идет уточнение условий конкурса. Пока не внесем полную ясность, не начнем.
Правильное решение будет представлено. Есть и проверочный тест, т.е. вторая, неизвестная участникам конкурса матрица.
Для меня важно убрать максимально какие либо ограничения, кроме тех, без которых решить задачу нельзя. Согласен, что есть много способов решения, но 90% из этих способов сразу покажут свою несостоятельность, так что здесь не всё так примитивно.
Насчет денежного приза.
Это только отборочные соревнования, если можно так сказать. Предквалификация. Следующий конкурс будет на порядок сложнее, но и приз на порядок больше!

Хорошо, но я вам сказал, над какими вопросами лучше подумать, чтобы не получилась нелепость.
Теперь добавлю, что тест лучше сделать не один, а хотя бы 10. На всякий случай. Мало ли, алгоритм какого-го участника вот так взял, и случайно лучше сработал именно на вашем тесте.

А по поводу правильного ответа, я имел в виду, в какую точность нужно уложиться? Если $10^{-4}, то одно число итераций, а если $10^{-8}, то другое. То есть я и спросил: что считать правильным ответом? Если разница между вашим и моим ответами такая-то? Или норма этой разницы такая-то? Или вообще числа в формате IEEE-754 должны совпадать побитово?

[Pavia]

Цитата:

Проверить я могу на любом типе, т.к. у меня есть самые последние Nvidia GTX-580 и ATI Radeon 6970. Я понимаю, что при программировании на GPU сказываются ограничения по рангу видеочипа. По крайней мере в CUDA это явно указывается. Поэтому давайте свои предложения по процедуре сравнения. Частоты CPU и GPU условимся принимать без разгона и установим стандарт.
Про "видеочип". Есть модели карт с одним и с двумя видеочипами. Например Nvidia GTX-580 и ATI Radeon 6970 - карты с одним чипом, Nvidia GTX-590 и ATI Radeon 6990 - с двумя чипами.

Тогда смысла писать про один чип нету. У вас по любому карты с одним чипом. А с точки зрения программных интерфейсов, видео карты(с 1 и 2 чипами) могут делиться на какое угодно число процессоров/ядер. Так что предлагаю оставить 1 видео карту. У вас надеюсь по одной видео карте в компьютере?
Либо второй вариант ограничить программный интерфейс Brook+ Тогда почти вся оптимизация будет алгоритмической.

[Eugeen1948]

Zealint уже поставил первое ограничение - точность. Это важный параметр, особенно при итерационной процедуре решения системы ур-ний.
Давайте примем точность как сопадение 12 десятичных цифр в каждом решении (из, практически, 16-ти). Такой подход позволит легко проверять результат.

[Pavia]

Eugeen1948 в сообщении #488819 писал(а):

Zealint уже поставил первое ограничение - точность. Это важный параметр, особенно при итерационной процедуре решения системы ур-ний.
Давайте примем точность как сопадение 12 десятичных цифр в каждом решении (из, практически, 16-ти). Такой подход позволит легко проверять результат.

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

[Eugeen1948]

Pavia в сообщении #488802 писал(а):

Цитата:

Тогда смысла писать про один чип нету. У вас по любому карты с одним чипом. А с точки зрения программных интерфейсов, видео карты(с 1 и 2 чипами) могут делиться на какое угодно число процессоров/ядер. Так что предлагаю оставить 1 видео карту. У вас надеюсь по одной видео карте в компьютере?
Либо второй вариант ограничить программный интерфейс Brook+ Тогда почти вся оптимизация будет алгоритмической.

У меня 3 карты в компьютере. В идеале можно поставить 7 с водой.
Насчет "....видео карты(с 1 и 2 чипами) могут делиться на какое угодно число процессоров/ядер. " не понял о каком конкретно программном интерфейсе идет речь? Это ведь только теоретически так. На сегодня, к сожалению, программирование для GPU должно учитывать тип видеочипа и объем памяти, доступный для использования.
Насчет Brook+, я не считаю необходимым ограничивать потенциальных участников выбором вспомогательных средств. CUDA, ATI Stream, OPEN CL, CUDA FORTRAN PGI, Brook+ , ets. - на Ваш выбор. Иначе получится непонятное ограничение, исключающее потенциального участника.
Подчеркиваю, надо прибежать первым. Если Вам удобно бежать в мешке - пожалуйста, босиком - ради бога

[Pavia]

Цитата:

не понял о каком конкретно программном интерфейсе идет речь?

Драйвер NVidea для OpenCL и Cuda выдаёт некоторое виртуальное число ядер обычно меньшее чем число реальных ядер(по классификации NVidia). При двух чиповой карте я к примеру не знаю какое число ядер будет.

[Eugeen1948]

Pavia
Насчет точности по совпадению результатов решения. Обоснуйте оба Ваши утверждение, пожалуйста.