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

[Zealint]

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

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

Цитата:

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

Вы только сформулируйте это условие несколько иначе. А то получится, что если у меня, скажем, $x_1=1$, а у вас $x_1=1-10^{-13}=0.\underbrace{9999999999999}_{\text{сколько надо раз}}$. То цифры не совпадают, а точность выдерживается.

[Eugeen1948]

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

Цитата:

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

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

Спецификации видеокарт на сайтах производителей.
Вот удобный справочник http://www.overclockers.ua/video/gpu/compare/

-- Вс окт 02, 2011 22:34:58 --

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

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

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

Цитата:

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

Вы только сформулируйте это условие несколько иначе. А то получится, что если у меня, скажем, $x_1=1$, а у вас $x_1=1-10^{-13}=0.\underbrace{9999999999999}_{\text{сколько надо раз}}$. То цифры не совпадают, а точность выдерживается.

Прошу извинить. Я, по привычке (Default ), подразумевал что при печати результата в формате с 12-ю десятичными знаками результаты не будут отличаться, т.к. произойдет форматное округление.

[drozdov_mihail]

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

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 в сообщении #488857 писал(а):

Прошу извинить. Я, по привычке (Default ), подразумевал что при печати результата в формате с 12-ю десятичными знаками результаты не будут отличаться, т.к. произойдет форматное округление.

Я поэтому и не считаю ваше предложение концептуально ошибочным (с кем не бывает), а сказал, что вы должны просто уточнить, как округлять результат, чтобы цифры стали совпадать. А еще лучше не округлять, а просто сравнивать, чтобы $|x-y|<10^{-12}$, и пусть участники выводят столько цифр, столько хотят. В общем, во всех таких задачах с дробями вопрос точности нужно всегда описывать предельно понятно и аккуратно.

А еще вам нужно (сначала для себя) доказать, что ваше решение само укладывается в заданную точность. Так как после конкурса участники вас попросят это доказать, если заподозрят неладное.

[Pavia]

Цитата:

Спецификации видеокарт на сайтах производителей.
Вот удобный справочник http://www.overclockers.ua/video/gpu/compare/

Только там про CUDA и OpenCL ни слово, а в них свой способ счёта ядер. NVidea пишет что это сделано для оптимизации вычислений.

Цитата:

Прошу извинить. Я, по привычке (Default ), подразумевал что при печати результата в формате с 12-ю десятичными знаками результаты не будут отличаться, т.к. произойдет форматное округление.

Этого не будет. Так как перевод из 2 в 10 неточен, то результат может получить как 1.0000000000 так и 0.9999999999.
Вопрос точность вычислений при использование чисел с плавающей точкой в современной литературе довольно плохо освещён.
Во-многих книгах рекомендуется сравнения производить с допуском.
abs(a-b) <eps

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

Из-за того что числа в компьютере хранятся в конечном числе бит, то при операциях будет происходить округление.
То есть по любому ошибка в вычислениях будет накапливаться. Что в итоге если брать большую точность (маленький eps) может повлиять на устойчивость алгоритма.

[Eugeen1948]

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

Цитата:

Спецификации видеокарт на сайтах производителей.
Вот удобный справочник http://www.overclockers.ua/video/gpu/compare/

Только там про CUDA и OpenCL ни слово, а в них свой способ счёта ядер. NVidea пишет что это сделано для оптимизации вычислений.

Этого не будет. Так как перевод из 2 в 10 неточен, то результат может получить как 1.0000000000 так и 0.9999999999.
Вопрос точность вычислений при использование чисел с плавающей точкой в современной литературе довольно плохо освещён.
Во-многих книгах рекомендуется сравнения производить с допуском.
abs(a-b) <eps

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

Из-за того что числа в компьютере хранятся в конечном числе бит, то при операциях будет происходить округление.
То есть по любому ошибка в вычислениях будет накапливаться. Что в итоге если брать большую точность (маленький eps) может повлиять на устойчивость алгоритма.

Все вышесказанное не имеет значения для поставленной задачи.
Я сейчас посмотрел у себя два разных способа решения с одной и той же матрицей. Сопадают 13-14 цифр при форматном выводе 14 значащих цифр. Оба метода прямые. Не вижу, почему для итерационных методов нужно подходить иначе. Ведь решается одна конкретная система, а не какой-то абстактный набор.
Насчет GPU.
У Вас есть конкретная видеокарта, средства программирования дают возможность "запросить" доступные ресурсы по количеству разных типов памяти GPU и процессоров.

[Zealint]

Цитата:

Ведь решается одна конкретная система, а не какой-то абстактный набор.

Ещё раз хочу посоветовать тестировать решения участников на разных системах. Иначе, допустим, что кто-то применил итерационную схему, которая в общем случае сходится за 100500 шагов, а именно в вашем случае она сходится за 50250 шагов (сколько именно нужно шагов для решения вашей системы, можно легко определить бинарным поиском). Такой участник сразу получает выигрыш в два раза, несмотря на то, что почти во всех остальных случаях его метод будет работать неправильно. Таким образом, участник сделает заточку под одну систему и практического смысла в этом решение не будет никакого. Нужно чтобы участники не могли подгонять число итераций и не могли делать их меньше, чем необходимо для гарантированного получения нужной точности.

[Eugeen1948]

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

Цитата:

Ведь решается одна конкретная система, а не какой-то абстактный набор.

Ещё раз хочу посоветовать тестировать решения участников на разных системах. Иначе, допустим, что кто-то применил итерационную схему, которая в общем случае сходится за 100500 шагов, а именно в вашем случае она сходится за 50250 шагов (сколько именно нужно шагов для решения вашей системы, можно легко определить бинарным поиском). Такой участник сразу получает выигрыш в два раза, несмотря на то, что почти во всех остальных случаях его метод будет работать неправильно. Таким образом, участник сделает заточку под одну систему и практического смысла в этом решение не будет никакого. Нужно чтобы участники не могли подгонять число итераций и не могли делать их меньше, чем необходимо для гарантированного получения нужной точности.

Уважаемый Zealint !
Я был бы совсем неучем, без знаний и опыта решения подобных задач, если бы не знал заранее, что здесь все не так просто. Я уже говорил, что у меня есть тест на случай читерства.
Что касается итерационных схем, то я почти уверен что последние разработки прямых методов лучше. Эта уверенность основана на том факте, что спектр СЗ матрицы комплексный.
Я еще 25 лет назад анализировал эту проблему (как то я на форуме приводил ссылки на доклады), консультировался у В.И. Лебедева
( http://ru.wikipedia.org/wiki/%D0%9B%D0% ... 0%B8%D1%87 ),
известного спеца в этих проблемах. Правда Лебедев разрабатывал метод Чебышевских ускорений для матриц с комплексным спектром, но результата я не видел (поэтому я употребил "почти уверен").

[Zealint]

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

Уважаемый Zealint !
Я был бы совсем неучем, без знаний и опыта решения подобных задач, если бы не знал заранее, что здесь все не так просто. Я уже говорил, что у меня есть тест на случай читерства.
Что касается итерационных схем, то я почти уверен что последние разработки прямых методов лучше. Эта уверенность основана на том факте, что спектр СЗ матрицы комплексный.
Я еще 25 лет назад анализировал эту проблему (как то я на форуме приводил ссылки на доклады), консультировался у В.И. Лебедева
( http://ru.wikipedia.org/wiki/%D0%9B%D0% ... 0%B8%D1%87 ),
известного спеца в этих проблемах. Правда Лебедев разрабатывал метод Чебышевских ускорений для матриц с комплексным спектром, но результата я не видел (поэтому я употребил "почти уверен").

Хорошо, вопросов нет. В любом случае, нужна была уверенность, что вы делаете шаги против читерства. Такое объяснение вполне может заменить набор тестов одним, если вы точно нигде не ошиблись.

Хорошо бы ещё, чтобы ваши собственные алгоритмы (подразумевается, что они заведомо быстрее почти всех решений участников) на этом тесте работали не быстрее 10-20 секунд. Иначе тяжело замерять время, когда программы работают быстрее. Видел людей, который соревновались на миллисекунды (измеряли через профилировку), забывая о том, что в эти миллисекунды входили операции самих команд измерения времени и занимали почти всё это время.

Еще вам нужно определиться с форматом входных и выходных данных и назвать участникам ограничения по памяти. Такие большие матрицы абы как в память не полезут. И считывание их из файла может сожрать все попытки оптимизировать код решения системы.

[Pavia]

Цитата:

Хорошо бы ещё, чтобы ваши собственные алгоритмы (подразумевается, что они заведомо быстрее почти всех решений участников) на этом тесте работали не быстрее 10-20 секунд. Иначе тяжело замерять время, когда программы работают быстрее. Видел людей, который соревновались на миллисекунды (измеряли через профилировку), забывая о том, что в эти миллисекунды входили операции самих команд измерения времени и занимали почти всё это время.

При замере надо учитывать множество факторов. Из-за того что виндоус и линукс имеет вытесняющую многозадачность могут наблюдать погрешности в измерениях. При запуске программы ядро может вытеснить одну задачу другой. Виндосу делает это через определенный промежутки времени около 4-20 миллисекунд. Есть ещё у поминание что виндоус использует длинные и короткие кванты. Длинные порядка 4с.
Но в целом по моим наблюдениям если задача длится более 4 секунд(до 1 минуты) , то ошибка измерения будет менее 0.1 раза. Для ошибки 0.001 надо уже несколько минут тратить на измерение.
Если говорить про измерения миллисекунд, то ошибка будет большая и надо делать цикл чтобы перейти в окно с большим интервалом. От 0.016 до 4 секунд точность не возрастала.
Правда выше сказанные измерения проводились без учёта времени потраченного на основную задачу и на дополнительные. И тут точность можно поднять если сделать такой учёт.

Если задача выполняется менее 15 мс(менее кванта) то тут измерения достаточно точные.
Также мне было интересно измерить скорость работы одной инструкции с точностью до 0.001
Понятно что инструкцию надо гонять в цикле порядка 10000. Самое удивительное получил результат $0.330\pm 0.0005$ такта (В руководстве от интел написано 0.33)

Если не брать замеры на промежуточных участках, то профилировщик время не тратит. Он замеряет время только на старте(т.е до) и в конце программы(т.е сразу по её завершению). А если мерит на промежуточных, тогда появляются накладные расходы, но их можно вычислить и вычесть. А да зачастую они не превосходят наносекунд в самом плохом случае микросекунды. Так что миллисекунды измерять можно.

[Eugeen1948]

Никто не откликнулся в участники
Может приз маловат?

[Zealint]

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

Никто не откликнулся в участники
Может приз маловат?

Так вы же ещё конкурс не начали.
Чтобы начать конкурс, нужен пиар. По моему опыту конкурс получается нормальным, если оставить сообщение на 5-7 форумах. Но перед этим нужно где-нибудь внятно написать все правила и сообщить, где будут отображаться текущие результаты (если будут). Сейчас у меня в блоге больше 80 подписчиков, почти все читают только посты по конкурсам. Как сделаете свой - дам у себя объявление. Уверен, что народ будет, так как задача слишком популярная.

Ну если не будет, тоже опыт полезный.