Решая огромную плотную линейную систему?

11

Есть ли надежда на эффективное решение следующей линейной системы итерационным методом?

ARn×n,xRn,bRn, with n>106

Ax=b

с участием

A=(ΔK) , где - очень разреженная матрица с несколькими диагоналями, возникающая в результате дискретизации оператора Лапласа. На его главной диагонали и есть еще диагоналей с на нем.- 6 6 1Δ661

K является полной матрицей которая полностью состоит из единиц.Rn×n

Решение отлично работает с итерационными методами, такими как Gauss-Seidel, потому что это разреженная диагонально доминирующая матрица. Я подозреваю, что проблему практически невозможно эффективно решить для больших чисел , но есть ли способ ее решить, используя структуру ?A = ( Δ - K ) n KA=ΔA=(ΔK)nK

РЕДАКТИРОВАТЬ: будет делать что-то вроде

Δxk+1=b+Kxk // решить для с помощью Гаусса-Зайделяxk+1

дойти до правильного решения? Я читал, что такой метод расщепления сходится, если , где - спектральная норма. Я вручную вычислил собственные значения для некоторых разных небольших значений и все они равны нулю, кроме значения, которое имеет довольно высокое отрицательное значение. (около ~ 500 для ) Так что я думаю, это не сработает.ρ Δ - 1 K n n = 256ρ(Δ1K)<1ρΔ1Knn=256

РЕДАКТИРОВАТЬ: Больше информации оΔ :

ΔRn×n является симметричным, отрицательно определенным и диагонально доминирующим.

Это сделано следующим образом в Matlab

n=W*H*D;

e=ones(W*H*D,1);

d=[e,e,e,-6*e,e,e,e];

delta=spdiags(d, [-W*H, -W, -1, 0, 1, W, W*H], n, n);

вон там
источник
Можете ли вы предоставить больше информации о , пожалуйста? Симметричный? Определенный, полуопределенный, не определенный? Δ
Стефано М
симметрично и отрицательно определено. Δ
йон
Поможет ли вам идентификация матрицы Вудбери , так как K является младшим?
Арон Ахмадиа

Ответы:

14

Есть два варианта, которые, если вы используете разумные структуры данных, могут решить проблему с на ноутбуке и n 10 12 на суперкомпьютере. Обратите внимание, что для эффективности вы должны использовать multigrid для решения с Δ . Стоимость в любом случае будет небольшим фактором дороже, чем просто решение с Δ . Два подхода эквивалентны через аргумент дополнения Шура, но я опишу их отдельно, потому что реализация отличается.n>106n1012ΔΔ

  • Используйте граничную систему

M=(ΔeeT1)

где - вектор-столбец, состоящий из всех единиц и решающий системуe

M(xy)=(b0)

используя итеративный или прямой решатель.

  • Используйте метод Крылова и примените матрицу как Δ - e e T (т. Е. Разреженную матрицу плюс поправку на ранг-1. Используйте существующий предварительный кондиционер P - 1Δ - 1 или, особенно, если вы хотите использовать прямое решение с Δ обновите его формулой Шермана-Моррисона .AΔeeTP1Δ1Δ
Джед браун
источник
KAzh=Δzy=he(eTz)z
Вольфганг Бангерт