2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Решить систему алгебраических линейных неоднородных уравнени
Сообщение22.07.2011, 15:01 
У меня есть система линейных уравнений. В ней 4000 уравнений.
Киньте плиз код для её решения. Желательно, чтобы он был максимально быстрым.
В последствии придется решать системы, состоящие из 100 000 уравнений. Так что хочется, чтобы алгоритм был без рекурсии.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение02.08.2011, 17:10 
Аватара пользователя
Если Вам надо будет решать систему из 100000 уравнений, то тот код, который я (или кто иной, не знающий Вашей специфики очень глубоко) Вам предложит, Вам заведомо не пригодится.
Методы "общего вида" кубичны по числу операций, и, значит, время решения будет запредельно велико.
Задачи такого размера решаются с учётом специфики матрицы. Возможно, она разрежена, возможно, ленточна, возможно, произведение матриц меньшей размерности. Но это известно Вам, а не нам.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение02.08.2011, 17:13 

(Оффтоп)

ТС, похоже, ответов не читает.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение08.08.2011, 15:02 
Иногда слышу о таких требованиях то тут то там.
Типа 100к Х 100к матрицы, желательно быстрый алгоритм...

А где такое применяется? Что-то я ни разу не встречал реального применения таким постановкам задачи.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение08.08.2011, 15:28 
Аватара пользователя
В Методе Конечных Элементов, например...

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение08.08.2011, 20:54 
Евгений Машеров в сообщении #472873 писал(а):
Если Вам надо будет решать систему из 100000 уравнений, то тот код, который я (или кто иной, не знающий Вашей специфики очень глубоко) Вам предложит, Вам заведомо не пригодится.
Методы "общего вида" кубичны по числу операций, и, значит, время решения будет запредельно велико.

Недалеко то время, когда на 1-ом компе можно будет использовать 80 гигов памяти и тогда систему из 100000 уравнений можно будет решить за разумное время без всяких излишних ограничений на свойства матрицы.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение10.08.2011, 16:31 
Аватара пользователя
Э-мнэээ...
Влезть-то оно влезет... А что Вы будете делать с числом операций порядка $10^16$?
Цитата:
пиковая производительность компьютера на базе четырехъядерного процессора AMD Phenom 9500 sAM2+ с тактовой частотой 2,2 ГГц равна:
2200 МГц × 4 ядра × 4×10−6 = 35.2 млрд операций в секунду = 0,0352 терафлопс.


То есть считаться задача у Вас будет 79 часов (если очень повезёт в распараллеливании, реальная средняя производительность в лучшем случае 60%-80% от пиковой...)

Впрочем, главная проблема будет у Вас не во времени, а в численной устойчивости решения.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение10.08.2011, 17:33 
Евгений Машеров,

в значительные разы ошиблись: у меня четырехядерный процессор 3400 Mhz и памяти - 16 гигов. При этом комп. перемножает две вещественные квадратные матрицы 20000 * 20000 примерно за 5 минут. Привожу этот пример для того, чтобы Вы поняли, какая ошибка Вами допущена. Кстати, именно перемножение матриц "съедает" львиную долю времени при решении системы.
Ну, а когда будет доступно 80 гигов памяти, то частота процессоров приблизится к 5000 Mhz, а число ядер не менее 8 станет обыденным: при этом система, рассмотренная выше, будет решаться за считанные часы.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение10.08.2011, 18:20 
drozdov_mihail в сообщении #474690 писал(а):
Евгений Машеров,

в значительные разы ошиблись: у меня четырехядерный процессор 3400 Mhz и памяти - 16 гигов. При этом комп. перемножает две вещественные квадратные матрицы 20000 * 20000 примерно за 5 минут. Привожу этот пример для того, чтобы Вы поняли, какая ошибка Вами допущена. Кстати, именно перемножение матриц "съедает" львиную долю времени при решении системы.


Это либо какие-то матрицы специального вида, либо какой-то очень хитрый алгоритм. Наивный алгоритм требует N^3 умножений, так что даже при умножении за такт (а на деле - медленнее), за пять минут перемножить не получится (даже если поделить время на 4, рассмотрев идеальные ядра в вакууме). Не говоря уже про сложения, чтение-запись и прочие накладные расходы.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение10.08.2011, 18:28 
alex1910,

N^3 умножений и N^3 сложений: никаких хитростей.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение10.08.2011, 18:55 
drozdov_mihail в сообщении #474703 писал(а):
alex1910,

N^3 умножений и N^3 сложений: никаких хитростей.


Без хитростей не получится, N^3 = 8*10^12 ~ 10^13 умножений.
В секунду 3,5*10^9 тактов, пусть, даже, 14*10^9 тактов в секунду.
5 минут = 300 секунд --> полтакта на умножение.

А так не бывает, умножение - операция на несколько тактов.

Сгенерите свои матрицы, чтобы элементы были равномерно распределены на отрезке, отделенном от нуля и перемножьте еще раз - посмотрите на время счета.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение10.08.2011, 18:59 
Аватара пользователя
Скажите, а зачем Вы перемножаете матрицы при решении систем уравнений? Там, извините, либо LU-разложение, либо обычный Гаусс, и ничего перемножать не надо...

-- Ср авг 10, 2011 20:05:21 --

И теперь по Вашему примеру. У Вас матрица в 5 раз меньше, следовательно, в 125 раз меньше операций. То есть примерно за 11 часов Вы бы, при должной памяти, перемножили бы матрицы 100000х100000. Однако решение системы уравнений требует в несколько раз бОльшей затраты времени, чем простое усножение. Так что, положим, 40-50 часов. Что согласуется с тем, что моя прикидка для 2.2 ГГц, а у Вас 3.4 ГГц.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение10.08.2011, 19:16 
alex1910 в сообщении #474711 писал(а):
А так не бывает

Бывает.
Евгений Машеров в сообщении #474713 писал(а):
ничего перемножать не надо...

Надо (на это и уходит основное время счета): поэтому Ваши предположения о многократном увеличении времени счета сильно преувеличены.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение10.08.2011, 19:51 
alex1910 в сообщении #474711 писал(а):
Без хитростей не получится, N^3 = 8*10^12 ~ 10^13 умножений.
В секунду 3,5*10^9 тактов, пусть, даже, 14*10^9 тактов в секунду.
5 минут = 300 секунд --> полтакта на умножение.

А так не бывает, умножение - операция на несколько тактов.
Во-первых, бывает.
Во-вторых, операций в методе Гаусса меньше, чем $N^3$.

 
 
 
 Re: Решить систему алгебраических линейных неоднородных уравнени
Сообщение12.08.2011, 10:26 
drozdov_mihail в сообщении #474690 писал(а):
у меня четырехядерный процессор 3400 Mhz и памяти - 16 гигов. При этом комп. перемножает две вещественные квадратные матрицы 20000 * 20000 примерно за 5 минут.

Пока руки "не доходят" до AVX инструкций: тогда вместо 5-ти минут должен получить менее 3-х минут.

 
 
 [ Сообщений: 21 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group