Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > решение больших разреженых систем уравнений

Автор: maxchv 17.4.2006, 08:29

Какие более эффективные методы решения больших систем (например 10000x10000 и более) численные (Зейделя) или точные (Гаусса, Холецкого) с точки зрения времени счета, занимаемой машинной памяти и точности в конечном счете?

Автор: nostromo 17.4.2006, 14:34

Кажется, эти вопросы в свое время подробно обсуждались при разработке фортрановских библиотек (linpack).

Автор: maxim1000 17.4.2006, 15:53

про Холецкого ничего не скажу - не знаю но если смотреть Гаусса, то брать его не стоит - в процессе решения очень многие коэффициенты матрицы могут стать ненулевыми а вот какие-нибудь итеративные методы подойдут они даже не требуют знания коэффициентов матрицы - просто какую-нибудь функцию, которая действует на вектор...

Автор: esperant0 17.4.2006, 16:47

для разных видов разреженных систем есть разные способы решения

Автор: Cr@$h 19.4.2006, 15:52

Цитата(maxim1000 @  17.4.2006,  16:53 ) но если смотреть Гаусса, то брать его не стоит - в процессе решения очень многие коэффициенты матрицы могут стать ненулевыми Вырождение, в смысле, -- оно решается путем выбора ведущего элемента по строкам и по столбцам. Цитата(maxim1000 @  17.4.2006,  16:53 ) они даже не требуют знания коэффициентов матрицы - просто какую-нибудь функцию, которая действует на вектор...       Цитата(maxchv @  17.4.2006,  09:29 ) Какие более эффективные методы решения больших систем (например 10000x10000 и более) численные (Зейделя) или точные (Гаусса, Холецкого) с точки зрения времени счета, занимаемой машинной памяти и точности в конечном счете?    Немного прокоменчу. Все методы численные и все неточные на машине ввиду округлений. Здесь методы делят на прямые и итерационные. Прямые обычно больше учитывают структуру матрицы, но требуют обычно и больше памяти. Например, Гаусса потребует места для хранения всей матрицы. Итерационные более универсальные, но стрктуру матрицы учитывают в меньшей степени. Не портят разреженный вид матрицы, решение получается итерационным способом. Наконец, в "последнее" время все большую популярность получают неявные прямые методы, или "итерационно-прямые": действуют как итерационные, но на каждой итерации решается прямым методом какая-то более простая система. Если размер матрицы большой, например, для указанной матрицы потребуется 763 Мб, то следует использоватьь итерационные методы, которые потребую хранения только ненулевых элементов и не нарушат структуру матрицы. Все еще зависит от того, откуда произрастает матрица -- очень часто из уравнений мат физики, a la дифуры в частных производных. Для некоторых их видов, например, матрица будет иметь специальный вид и решаться эффективно одним из прямых методов, учитывающих эту структуру. Для симметричных систем советую использовать метод сопряженных градиентов или т.н. чебышевский, но последний нужно будет подкручивать. Для несимметричных такой вопрос еще не решен, но можно попробовать аналог МСГ -- биортогональный алгоритм. Правда он сходится довольно таки странно. Во всех итерационных случаях рекомендуется использовать предобуславливание. К сожалению, нормальных книг, где это было бы "популярно" расписано я не встречал.

Автор: maxim1000 19.4.2006, 17:01

Цитата(Cr@$h @  19.4.2006,  14:52 ) Вырождение, в смысле, -- оно решается путем выбора ведущего элемента по строкам и по столбцам нет, имелось в виду не это предположим, в матрице очень мало ненулевых элементов (неважно, где они находятся), так вот в процессе решения Гауссом количество ненулевых элементов может сильно увеличиться в конце-то оно будет небольшим - только на диагонали, а вот где-нибудь в середине может получиться матрица с кучей ненулевых элементов с точки зрения корректности никаких проблем - так и должно быть но если разреженность матрицы использовалась при выборе способа ее хранения (например, список ненулевых элементов), то использование памяти может сильно подскочить, что нежелательно, особенно для очень больших матриц... Цитата(Cr@$h @  19.4.2006,  14:52 ) они даже не требуют знания коэффициентов матрицы - просто какую-нибудь функцию, которая действует на вектор...  матрица - один из способов записи линейного отображения - когда f(x+y)=f(x)+f(y) и f(a*x)=a*f(x) для векторных пространств и если Гаусс манипулирует коэффициентами матрицы, то для некоторых других методов достаточно, чтоб им дали указатель на функцию, которая берет вектор x и возвращает Ax, а как она их вычисляет, для метода абсолютно все равно можно представить себе такую задачу: у нас есть матрица, которая при действии на вектор сдвигает все его компоненты на 1 вниз, а последний ставит наверх задача сформулирована для размерности, скажем, тысяча что нужно? решить Ax=b, как обычно для использования Гаусса нужно записать матрицу полностью, что потребует миллиона ячеек при том, любой программист напишет простенькую функцию, которая будет занимать сотню байт...

Автор: Cr@$h 23.4.2006, 13:30

Цитата(maxim1000 @  19.4.2006,  18:01 ) предположим, в матрице очень мало ненулевых элементов (неважно, где они находятся), так вот в процессе решения Гауссом количество ненулевых элементов может сильно увеличиться в конце-то оно будет небольшим - только на диагонали, а вот где-нибудь в середине может получиться матрица с кучей ненулевых элементов с точки зрения корректности никаких проблем  Это все понятно. Только "в конце-то оно будет небольшим" -- на самом деле такой халявы не будет. Решая разреженную систему методом Гаусса, мы нарушим ее разреженный вид раз и навсегда и в конце получим примерно полностью заполненную треугольную матрицу. Собственно, поэтому и нерекомендуется (если вообще возможно) применять для больших разреженных систем прямые методы. Цитата(maxim1000 @  19.4.2006,  18:01 ) для некоторых других методов достаточно, чтоб им дали указатель на функцию, которая берет вектор x и возвращает Ax, а как она их вычисляет, для метода абсолютно все равно Для любого метода -- "все равно", он просто содержит это действие внутри себя да и не имеет право заставлять делать это как-то по-особенному. Итерационные методы используют практически только операции с векторами и умножение матрицы на вектор, а не, например, умножение матриц, которое увеличит число ненулевых элементов в результате такого умножения. А как это уже реализовывать -- дело техники: через функции, подпрограммы, операции и прочее.

Автор: maxim1000 24.4.2006, 03:26

Цитата(Cr@$h @  23.4.2006,  12:30 ) Это все понятно. Только "в конце-то оно будет небольшим" -- на самом деле такой халявы не будет. Решая разреженную систему методом Гаусса, мы нарушим ее разреженный вид раз и навсегда и в конце получим примерно полностью заполненную треугольную матрицу ну есть же обратный ход (а иногда это делают и сразу) - когда обнуляется вторая треугольная часть и остаются только диагональные элементы, так что матрица получится, возможно, даже более разреженной, чем в начале, но никак не менее... Цитата(Cr@$h @  23.4.2006,  12:30 ) Для любого метода -- "все равно", он просто содержит это действие внутри себя да и не имеет право заставлять делать это как-то по-особенному. В принципе, конечно, можно, имея функцию f(x)=Ax получить все ее коэффициенты, но Гаусс использует кучу таких коэффициентов, которые надо хранить в памяти, а итерационные методы - вычисляют иногда всего один раз, и памяти для хранения этого результата (вектора) надо порядка N, а не N^2, как в Гауссе...

Автор: Cr@$h 24.4.2006, 13:06

Цитата(maxim1000 @  24.4.2006,  04:26 ) ну есть же обратный ход (а иногда это делают и сразу) - когда обнуляется вторая треугольная часть и остаются только диагональные элементы, так что матрица получится, возможно, даже более разреженной, чем в начале, но никак не менее... Так всести ее можно к чему угодно, главное -- сколько всего ненулевых элементов придется хранить, для Гаусса -- всю треугольную часть матрицы, поэтому разреженность только уменьшиться. А потом можно ее сразу решать, либо приводить к диагональной (не знаю зачем, правда). Факт в том, что прямые методы могут только увеличить число ненулевых элементов для ленточных матриц. А треугольную конечно можно превратить в диагональную, только мы с ней и не работаем. Цитата(maxim1000 @  24.4.2006,  04:26 ) можно, имея функцию f(x)=Ax получить все ее коэффициенты, но Гаусс использует кучу таких коэффициентов, которые надо хранить в памяти, а итерационные методы - вычисляют иногда всего один раз Часто по многу, но зато не заполняют нулевые элементы, в этом их основное преимущество для разряженных систем.

Автор: Vitaly333 23.1.2008, 02:30

Цитата Собственно, поэтому и нерекомендуется (если вообще возможно) применять для больших разреженных систем прямые методы. Ещё как возможно .... просто нужно перед тем как делать треуголное численное разложение нужно найти хорошую перестановку P. Для этого существует специальный класс алгоритмов которые ищат приемлемые по качеству перестановки исходя из графа матрицы или из самой матрицы. После того ка перестановка найдена .. делаеться след. замена: C = P*A*PT и   вектор D = b*P А потом уже решаеться система: C*X = D  Таким образом уменьшаеться заполнение в матрице которое происходит в результате численного этапа разложения и большая разреженная система решаеться очень быстро. Что касаеться итерационных алгоритмов то одни из самых быстрых - это итерационные алгоритмы крыловского подпространства! Но у них есть один большой минус - плохая сходимость на больших и плохообусловленных  задачах! Для улучшения сходимости также существует  специальный класс алгоритмов -  называемых предобуславливателями. В качестве предобуславливателя часто берут Неподные факторизации Холецкого (для симметричных) и LU (не симметричных) систем. Поэтому как кто -то выше и писал они и получаються итерационно - прямыми.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)