Memecahkan sistem linear padat besar?

11

Adakah harapan dalam menyelesaikan sistem linear berikut secara efisien dengan metode berulang?

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

Ax=b

dengan

A=(ΔK) , di manaΔ adalah matriks yang sangat jarang dengan beberapa diagonal, yang timbul dari diskritisasi Operator Laplace. Di diagonal utamanya ada6 dan ada6 diagonal lainnya dengan diagonal1.

K adalahmatriksRn×n yang sepenuhnya terdiri dari satu.

Memecahkan A=Δ bekerja dengan baik dengan metode berulang seperti Gauss-Seidel, karena itu adalah matriks dominan diagonal yang jarang. Saya menduga bahwa masalah A=(ΔK) sangat tidak mungkin untuk diselesaikan secara efisien untuk sejumlah besar n , tetapi apakah ada trik untuk menyelesaikannya, dengan mengeksploitasi struktur K ?

EDIT: Akan melakukan sesuatu seperti

Δxk+1=b+Kxk // memecahkan untukxk+1 dengan Gauss-Seidel

ρ(Δ1K)<1ρΔ1Knn=256

Δ

ΔRn×n

Ini dibuat dengan cara berikut di 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);

kamu
sumber
Δ
Δ
Apakah Woodbury Matrix Identity membantu Anda karena K adalah peringkat rendah?
Aron Ahmadia

Jawaban:

14

n>106n1012ΔΔ

  • Gunakan sistem berbatasan

M=(ΔeeT1)

di mana adalah vektor kolom yang terdiri dari semua yang ada dan menyelesaikan sisteme

M(xy)=(b0)

menggunakan soler iteratif atau langsung.

  • Gunakan metode Krylov dan terapkan matriks sebagai (yaitu matriks jarang plus koreksi peringkat-1. Gunakan prekondisier , atau , terutama jika Anda ingin menggunakan penyelesaian langsung dengan , perbarui dengan rumus Sherman-Morrison .AΔeeTP1Δ1Δ
Jed Brown
sumber
Saya cenderung berpikir bahwa Anda jauh lebih baik dengan pendekatan kedua. Intinya adalah bahwa Anda tidak boleh mencoba untuk menyimpan matriks dalam memori atau mencoba melakukan produk vektor matriks dengannya. Sebaliknya, setiap kali Anda harus mengalikan dengan dengan vektor dalam skema berulang Anda, Anda mengalikan dan kemudian menghitung . Istilah dalam tanda kurung hanya jumlah dari entri dan Anda menghitung hanya sekali. Jed sudah menjelaskan ini dengan baik, tetapi saya ingin menekankan urutan operasi. KAzh=Δzy=he(eTz)z
Wolfgang Bangerth