Bagaimana menyusun ulang variabel untuk menghasilkan matriks berpita bandwidth minimum?

15

Saya mencoba menyelesaikan persamaan 2D Poisson dengan perbedaan hingga. Dalam prosesnya, saya mendapatkan matriks jarang dengan hanya variabel di setiap persamaan. Misalnya, jika variabelnya adalah , maka diskritisasi akan menghasilkan: $5$ $U$

U_{i - 1, j} + U_{i + 1, j} - 4 U_{i, j} + U_{i, j - 1} + U_{i, j + 1} = f_{i, j}

$U_{i-1,j} + U_{i+1,j} -4U_{i,j} + U_{i,j-1} + U_{i,j+1} = f_{i,j}$

Saya tahu bahwa saya dapat menyelesaikan sistem ini dengan metode berulang, tetapi saya berpikir bahwa jika saya memesan variabel dengan tepat, saya mungkin dapat memperoleh matriks berpita yang dapat diselesaikan dengan metode langsung (yaitu, eliminasi Gaussian. / o berputar). Apakah ini mungkin? Apakah ada strategi untuk melakukan ini untuk sistem lain yang mungkin kurang terstruktur?

linear-algebra pde finite-difference sparse-matrix banded-matrix Paul
sumber

2

Sesuatu seperti Cuthill-McKee, kalau begitu?

JM

Menarik ... saya belum pernah mendengar tentang algoritma Cuthill-McKee sebelumnya! :)

Paul

1

Ada juga Reverse Cuthill-McKee juga.

Geoff Oxberry

1

Saya harap ini jelas dari jawaban, tetapi Anda tidak ingin menggunakan solver berpita untuk masalah ini, juga tidak memilih pemesanan yang meminimalkan bandwidth. Mungkin pertanyaan atau jawaban yang dipilih dapat diedit untuk memperjelas ini, jika tidak saya khawatir mitos ini akan terus berlanjut. Saya memberikan perbandingan visual dan membandingkan isi di scicomp.stackexchange.com/a/880/119 .

Jed Brown

@JedBrown: Sebenarnya, saya tidak cukup bekerja dengan masalah poisson, per se ... Masalah saya memiliki struktur yang mirip dengan masalah poisson ... Indeks variabel (i dan j) persis sama, dan matriks dominan secara diagonal dengan entri off-diagonal (dalam baris yang sama) menambah persis jumlah entri diagonal.

Paul

13

Ini adalah masalah yang dipelajari dengan baik di bidang pemecah langsung-jarang. Saya sangat merekomendasikan membaca ikhtisar Joseph Liu tentang metode multifrontal untuk mendapatkan ide yang lebih baik tentang bagaimana pemesanan ulang dan supernode mempengaruhi waktu pengisian dan solusi.

Diseksi bersarang adalah cara yang sangat umum untuk menghasilkan pemesanan ulang, dan pada dasarnya terdiri dari partisi grafik rekursif. MeTiS adalah standar de facto untuk partisi grafik, dan Anda dapat membaca tentang beberapa ide di baliknya di sini . Paket lain yang umum digunakan adalah SCOTCH , dan Chaco juga penting, karena penulisnya memperkenalkan partisi grafik multi-level , yang juga merupakan ide mendasar di balik MeTiS .

George dan Liu menunjukkan dalam buku klasik mereka yang 2d solusi jarang-langsung hanya membutuhkan kerja dan memori, sedangkan 3d jarang-direct membutuhkan kerja dan memori. $O(n^{3/2})$ $O(n \log n)$ $O(n^2)$ $O(n^{4/3})$

Jack Poulson
sumber

Apakah Anda memiliki kutipan untuk referensi George dan Liu?

Paul

Ditambahkan; Saya akan keluar dari mobil ketika saya pertama kali menyerahkannya. Saya tahu bahwa ada versi gratis buku yang tersedia secara online di suatu tempat (Jed tahu di mana itu), tetapi saya tidak dapat menemukannya.

Jack Poulson

Saya memperbarui tautan untuk menunjuk ke PDF buku, bukan ulasan buku.

Jed Brown

@JedBrown Itu referensi yang bagus! Terima kasih banyak! :)

Paul

1

@Alexander Semua orang menghubungkan 3D ke George dan Liu, meskipun saya tidak tahu apakah mereka secara eksplisit menunjukkannya di buku. Namun jelas dari teori. Pemisah titik minimal untuk

grid

. Matriks padat terkait dengan supernode yang memiliki

entri dan membutuhkan

n = m \times m \times m

$n = m\times m\times m$

n^{2 / 3} = m \times m

$n^{2/3} = m\times m$

(n^{2 / 3})^{2} = n^{4 / 3}

$(n^{2/3})^2 = n^{4/3}$

(n^{2 / 3})^{3} = n^{2}

$(n^{2/3})^3 = n^2$ operasi menjadi faktor. Istilah logaritmik dalam kasus 2D lebih halus dan dibahas dalam Bab 8 tentang Diseksi Bersarang, yang mencapai batas bawah.

Jed Brown

5

Cuthill-McKee adalah standar de facto untuk apa yang ingin Anda lakukan. Jika Anda ingin bermain dengan metode ini, ada implementasi algoritma yang mudah digunakan (dan kebalikannya) di Boost Graph Library (BGL), dan dokumentasi berisi contoh cara menggunakannya.

Wolfgang Bangerth
sumber

sebenarnya membalikkan Cuhill-McKee; biasanya memberikan lebih sedikit isian. Tetapi pemesanan diseksi bersarang jauh lebih unggul daripada pemesanan bandwidth rendah.

Arnold Neumaier

4

Berbicara tentang metode multifrontal, Tim Davis , yang bekerja pada metode multifrontal untuk faktorisasi LU ( UMFPACK ) memiliki sejumlah rutin yang akan menyusun ulang matriks untuk meminimalkan pengisian. Anda dapat menemukannya di sini sebagai bagian dari SuiteSparse . SuiteSparse menggunakan MeTiS.

Satu hal lagi yang perlu diperhatikan: Dalam beberapa masalah, Anda bisa pandai tentang pemesanan variabel sehingga Anda mendapatkan banded, atau dekat dengan banded, pola, yang dapat menyelamatkan Anda dari masalah (dan waktu CPU) dalam memanggil algoritma ini. Namun, pengurutan ulang yang cerdik ini membutuhkan wawasan dari Anda dan sama sekali tidak umum seperti algoritma pengurutan ulang berbasis teori-grafik yang disebutkan orang dalam jawaban mereka di sini.

Geoff Oxberry
sumber

Sama-sama, Paul. Jika Anda suka, pilih itu.

Geoff Oxberry

3

Ada algoritma yang disebut ADI (Alternating Direction Implicit) dalam lingkaran matematika terapan dan operator perpecahan dalam lingkaran fisika yang pada dasarnya melakukan apa yang Anda gambarkan. Ini adalah metode berulang, dan mengikuti prosedur dasar ini:

Untuk setiap nilai , bersantai di arah- . Matriks ini harus tridiagonal, sehingga dapat diselesaikan secara langsung dalam waktu yang relatif sedikit. $y$ $x$
Untuk setiap nilai , bersantai di directional. Sekali lagi, ini seharusnya cukup cepat. $x$ $y$
Ulangi 1 dan 2 hingga kesalahannya sekecil yang Anda inginkan.

Saya tidak tahu kompleksitas formal dari algoritma ini, tetapi saya menemukan itu untuk menyatu dalam iterasi yang lebih sedikit daripada hal-hal seperti Jacobi dan Gauss-Seidel setiap kali saya menggunakannya.

Dan
sumber

2

Jika Anda memutuskan untuk pergi ke rute pemisahan operator, sesuatu yang Anda ingin berhati-hati adalah bahwa pemisahan operator diketahui menyebabkan kesalahan dalam solusi kondisi tunak dalam beberapa kasus. (Salah satu teman lab saya telah mengembangkan cara untuk mengatasi kesulitan ini, tapi saya tidak percaya dia menerbitkannya.) Juga, pemisahan operator diketahui menyebabkan kesalahan numerik. Ada beberapa cara yang mapan untuk memperkirakan kesalahan ini a posteriori ; Don Estep telah melakukan pekerjaan luar biasa di bidang itu.

Geoff Oxberry

@ GeoffOxberry Sepertinya Anda mengacu pada pemisahan yang berbeda. Anda dapat menggunakan ADI dalam skema sepenuhnya implisit yang tidak memiliki kesalahan pemisahan karena sebenarnya memecahkan sistem. Ada juga metode IMEX yang secara ketat mengontrol kesalahan pemisahan.

Jed Brown

x

$x$

y

$y$

Saya belum pernah mendengar tentang Godunov dan Strang yang membelah. Saya cenderung membagi operator saya dengan formula Baker-Campbell-Hausdorf. Apakah itu sama?

Dan

Bagaimana menyusun ulang variabel untuk menghasilkan matriks berpita bandwidth minimum?

Jawaban: