Bagaimana cara membangun operator pemanjangan dan pembatasan untuk pemecah multigrid aljabar?

10

Saya mencoba memecahkan sistem linear persamaan yang jarang, tetapi tidak memiliki struktur pita apa pun. Saya telah mendengar bahwa ada cara untuk memperluas prinsip-prinsip pemecah multigrid untuk skema beda hingga implisit ke masalah linear umum (jika saya tidak salah, itu disebut pemecah multigrid aljabar). Setelah membaca beberapa literatur tentang itu, saya masih sangat bingung tentang bagaimana cara interpolasi (yaitu memperpanjang dan membatasi) antara grid kasar dan halus tanpa mengeksploitasi struktur bagus dari matriks-matriks yang diikat seperti yang dari skema beda hingga. Apakah ada heuristik untuk itu? Adakah yang bisa memberi contoh?

Paul
sumber

Jawaban:

13

Pertama, jika Anda memiliki kisi terstruktur, Anda mungkin ingin menggunakan geometri alih-alih aljabar multigrid karena beberapa keuntungan teoretis dan efisiensi (mis. Kemampuan untuk menata kembali alih-alih menggunakan operator jaringan kasar Galerkin). Metode multigrid aljabar umumnya terbagi dalam dua kategori.

Multigrid Aljabar Klasik

Metode ini diperkenalkan oleh Brandt, McCormick, dan Ruge pada tahun 1982 dan memiliki teori yang kuat untuk -matrices . Brandt (1986) memiliki teori konvergensi standar. Lihat BoomerAMG dari paket Hypre untuk implementasi paralel yang populer dan sangat skalabel. Varian yang lebih kuat dan umum disebut Bootstrap AMG, lihat tulisan terbaru dari Brandt, Brannick, Kahl, dan Livshits .M

Agregasi yang dihaluskan

Agregasi yang dihaluskan dari Vaněk, Mandel, dan Brezina (1996) adalah metode yang lebih baru yang telah terbukti bermanfaat untuk masalah vektor seperti elastisitas. Pendekatan umum adalah mulai dengan vektor yang mengkarakterisasi ruang mendekati nol dari operator (misalnya mode tubuh kaku dalam elastisitas), membangun agregat menggunakan konektivitas matriks (biasanya dengan menemukan set independen maksimal ), dan "halus "agregat (menggunakan operator) untuk membuat fungsi dasar kasar energi rendah. Implementasi paralel yang populer adalah ML dari Trilinos , Prometheus dari Mark Adams (hadiah Gordon Bell 2004), PCGAMG dalam PETScATA(juga dari Mark Adams, sebagian besar pengganti lengkap untuk Prometheus), dan komponen agregasi yang dihaluskan dari CUSP kode GPU berbasis CUDA .

Perhatikan bahwa semua perangkat lunak yang disebutkan di atas dapat diakses melalui antarmuka umum menggunakan PETSc .

Jed Brown
sumber
4

"Multigrid" oleh Trottenberg, dkk, adalah buku yang sangat bagus dan sepertinya sebagian besar tersedia di buku Google. Ini memiliki lampiran pada AMG dan Anda mungkin perlu mendapatkan latar belakang dalam MG dari sisa buku ini. "Tutorial Multigrid" juga merupakan buku yang bagus.

Adams
sumber
3

Saya akan menyarankan bab 8 dari "A Multigrid Tutorial" (2Ed) oleh WL Briggs, VE Henson dan SF McCormick. Ini memberikan ide umum pada beberapa konsep penting seperti kelancaran aljabar dan ketergantungan yang kuat. Ini juga menjelaskan cara mendefinisikan operator interpolasi (operator jaringan kasar juga) dan cara memilih grid kasar.

Bernardo MR
sumber
Bernardo, selamat datang scicomp! Paragraf kedua Anda lebih mirip pertanyaan daripada jawaban. Bisakah Anda memotongnya dari jawaban Anda dan menempelkannya ke pertanyaan yang terpisah? Pertanyaan yang Anda ajukan di paragraf kedua adalah contoh yang baik dari jenis pertanyaan yang ingin kita lihat scicomp.
Geoff Oxberry