Решить систему алгебраических линейных неоднородных уравнени

[hello19]

У меня есть система линейных уравнений. В ней 4000 уравнений.
Киньте плиз код для её решения. Желательно, чтобы он был максимально быстрым.
В последствии придется решать системы, состоящие из 100 000 уравнений. Так что хочется, чтобы алгоритм был без рекурсии.

[Евгений Машеров]

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

[venco]

(Оффтоп)

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

[logout2d]

Иногда слышу о таких требованиях то тут то там.
Типа 100к Х 100к матрицы, желательно быстрый алгоритм...

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

[Евгений Машеров]

В Методе Конечных Элементов, например...

[drozdov_mihail]

Евгений Машеров в сообщении #472873 писал(а):

Если Вам надо будет решать систему из 100000 уравнений, то тот код, который я (или кто иной, не знающий Вашей специфики очень глубоко) Вам предложит, Вам заведомо не пригодится.
Методы "общего вида" кубичны по числу операций, и, значит, время решения будет запредельно велико.

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

[Евгений Машеров]

Э-мнэээ...
Влезть-то оно влезет... А что Вы будете делать с числом операций порядка $10^16$?

Цитата:

пиковая производительность компьютера на базе четырехъядерного процессора AMD Phenom 9500 sAM2+ с тактовой частотой 2,2 ГГц равна:
2200 МГц × 4 ядра × 4×10−6 = 35.2 млрд операций в секунду = 0,0352 терафлопс.

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

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

[drozdov_mihail]

Евгений Машеров,

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

[alex1910]

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

Евгений Машеров,

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

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

[drozdov_mihail]

alex1910,

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

[alex1910]

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

alex1910,

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

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

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

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

[Евгений Машеров]

Скажите, а зачем Вы перемножаете матрицы при решении систем уравнений? Там, извините, либо LU-разложение, либо обычный Гаусс, и ничего перемножать не надо...

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

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

[drozdov_mihail]

alex1910 в сообщении #474711 писал(а):

А так не бывает

Бывает.

Евгений Машеров в сообщении #474713 писал(а):

ничего перемножать не надо...

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

[venco]

alex1910 в сообщении #474711 писал(а):

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

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

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

[drozdov_mihail]

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

у меня четырехядерный процессор 3400 Mhz и памяти - 16 гигов. При этом комп. перемножает две вещественные квадратные матрицы 20000 * 20000 примерно за 5 минут.

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