Решение больших разреженных СЛАУ

[AndrSlav]

Здравствуйте, вопрос в следующем:
есть большая несимметричная разреженная матрица, состоящая из 7 диагоналей - главная, примыкающие к ней сверху и снизу и еще две пары диагоналей, расположенных симметрично относительно главной. Т.е. матрица не ленточная (не все диагонали примыкают друг к другу), была бы симметричной, если бы элементы в симметричных диагоналях совпадали.
Решаю СЛАУ методом простой итерации Гаусса-Зейделя- долго. Пишут, что проекционные методы (подпространства Крылова) быстрее, но, там все упирается в решение СЛАУ с Хессенберговой матрицей (методом Гаусса рекомендуется), а это не быстро
Как решать такие СЛАУ? Ведь в пакетах газодинамики они решаются мгновенно- что за методы?
--------------------------------------------------------------------------------------------------------
Пока склоняюсь к:
1. умножению матрицы на транспонированную для приведения к симметричному виду (но увеличивается кол-во диагоналей )
2. затем, если разберусь, предобуславливание Холецкого
3. и после- решение проекционным методом Крылова или др.

Можно ли как-то провести предобуславливание исходной несимметричной матрицы с сохранением разреженности и приведением ее к симметричному виду?

Вообще какие методы/алгоритм посоветуете? А то литературы и методов дикое кол-во, а знания поверхностные - потратил кучу времени, все время обнаруживается, что смотрю то, что не подходит.

[мат-ламер]

Попробуйте в MatLabe почитать help. Они приводят названия методов и есть кое-какие ссылки на литературу. И в этом разделе форума http://dxdy.ru/chislennye-i-vychislitelnye-metody-optimizatsiya-f71.html поищите.

[bin]

Классическая книга: С.Писсанецки, Технология разреженных матриц, М.:Мир, 1988. Из готового ПО в первую очередь стоит посмотреть LAPACK (в Википедии есть статья со ссылками), в частности, посмотреть Intel MKL.

[rtfai]

Если матрица "хорошо" положительно определенная, то решайте итерационными методами не преобразуя. Например,если она получена как дискретизация эллиптической краевой задачи с конвективными членами. Метод верхней релаксации.

[AndrSlav]

Методы с релаксацией медленно сходятся А еще обычные методы трудно параллелить. Предобуславливание бы помогло, наверно, но, не знаю как того же Холецкого распараллелить.
А задача действительно простая эллиптическая.

Может кому пригодится, интересная литература:
1. Методы решения СЛАУ большой размерности. М.Ю. Баландин, Э.П. Шурина
2. Вычислительная линейная алгебра с примерами на MATLAB. В.И. Горбаченко
3. Iterative methods for sparce linear systems. Yousef Saad - (очень хорошая подробная книга)

[Romkin]

Если расположение ненулевых элементов достаточно предсказуемо, то может стоит перейти к поблочным вычислениям? Разбить матрицу на блоки и перейти к матричной арифметике. Матрица станет трехдиагональной, и распараллелить можно операции над блоками.

[rtfai]

AndrSlav в сообщении #866661 писал(а):

Методы с релаксацией медленно сходятся А еще обычные методы трудно параллелить. Предобуславливание бы помогло, наверно, но, не знаю как того же Холецкого распараллелить.
А задача действительно простая эллиптическая.

Может кому пригодится, интересная литература:
1. Методы решения СЛАУ большой размерности. М.Ю. Баландин, Э.П. Шурина
2. Вычислительная линейная алгебра с примерами на MATLAB. В.И. Горбаченко
3. Iterative methods for sparce linear systems. Yousef Saad - (очень хорошая подробная книга)

Параллелить можно с помощью альтернирующего метода Шварца.
Начальное приближение можно выбрать с помощью решения задачи без конвективных членов.
Эллиптические задачи вообще трудно параллелятся.

[AndrSlav]

Пытаюсь осознать метод Шварца. Правильно ли я понимаю:

Без декомпозиции.
Пусть область одномерная, состоит из n ячеек. Для каждой ячейки можно записать центральноразностную схему, которая будет для i-ой ячейки иметь вид f(i+1)-2*f(i)+f(i-1)= H(i). Таким образом, имеем n-2 уравнения, первая и последняя ячейки -граничные условия, отсюда находим f в ячейках.

Теперь разбиваем на 2 области.
В каждой области n/2 ячеек. По идее, можно записать 2 отдельные СЛАУ, но что с ГУ в месте соприкосновения?
Например, 1ая СЛАУ- в 1ой ячейке значение известно (ГУ), а в последней?
Пусть в последней ячейке (№ n/2) 1ой СЛАУ записана конечно-разностная схема
f(n/2-1)-2*f(n/2)+f(n/2+1)= H(n/2).
Считать, что f(n/2+1) - задано (взять значение из смежной СЛАУ)? Но ведь на самом деле это значение не дано, а тоже вычисляется?

Как я понимаю, это снижает сходимость в граничных областях? И для ее улучшения используются области с перекрытием? Или я не правильно понимаю?