Nhiều định luật cơ bản nhất của tự nhiên có thể được biểu diễn dưới dạng phương trình vi phân riêng phần (PDE). Tuy nhiên, vì nghiệm tổng quát của nhiều PDE chưa được biết đến, nên việc tìm ra nghiệm xấp xỉ hiệu quả cho các phương trình này là một trong những thách thức lớn nhất của nhân loại. Mặc dù phương pháp đa lưới (multigrid) là một trong những phương pháp hiệu quả nhất để giải PDE bằng số, nhưng trong nhiều trường hợp, việc thiết kế một bộ giải đa lưới hiệu quả hoặc ít nhất là hoạt động được vẫn là một vấn đề mở. Luận văn này chứng minh rằng lập trình di truyền hướng dẫn bằng ngữ pháp, một kỹ thuật tổng hợp chương trình tiến hóa, có thể khám phá ra các phương pháp đa lưới với cấu trúc chưa từng có, đạt được hiệu quả và khả năng khái quát hóa cao. Để phục vụ mục đích này, chúng tôi phát triển một ngữ pháp phi ngữ cảnh mới cho phép tự động tạo ra các phương pháp đa lưới trong một ngôn ngữ hình thức có thể thao tác ký hiệu, dựa trên đó chúng ta có thể áp dụng cùng một bộ giải dựa trên đa lưới cho các bài toán có kích thước khác nhau mà không cần phải điều chỉnh cấu trúc bên trong của nó. Việc coi thiết kế tự động một phương pháp đa lưới hiệu quả như một nhiệm vụ tổng hợp chương trình cho phép chúng ta tìm ra các chuỗi hoạt động đa lưới mới, bao gồm sự kết hợp của các bước làm mịn và hiệu chỉnh lưới thô khác nhau ở mỗi cấp độ của hệ thống phân cấp rời rác hóa.

Abstract:

Many of the most fundamental laws of nature can be formulated as partial differential equations (PDEs). However, since the general solution of many PDEs is unknown, the efficient approximate solution of these equations is one of humanity's greatest challenges. While multigrid represents one of the most effective methods for solving PDEs numerically, in many cases, the design of an efficient or at least working multigrid solver is an open problem. This thesis demonstrates that grammar-guided genetic programming, an evolutionary program synthesis technique, can discover multigrid methods of unprecedented structure that achieve a high degree of efficiency and generalization. For this purpose, we develop a novel context-free grammar that enables the automated generation of multigrid methods in a symbolically-manipulable formal language, based on which we can apply the same multigrid-based solver to problems of different sizes without having to adapt its internal structure. Treating the automated design of an efficient multigrid method as a program synthesis task allows us to find novel sequences of multigrid operations, including the combination of different smoothing and coarse-grid correction steps on each level of the discretization hierarchy.

Ngôn ngữ:	eng
Tác giả:	Schmitt, Jonas
Thông tin nhan đề:	Automating the Design of Multigrid Methods with Evolutionary Program Synthesis
Nhà xuất bản:	FAU University Press
Loại hình:	Tài nguyên giáo dục mở / Bộ sưu tập: Công nghệ thông tin
Bản quyền:	https://creativecommons.org/licenses/by/4.0/
Nguồn gốc:	https://directory.doabooks.org/handle/20.500.12854/170180
Mô tả vật lý:	222tr.
Năm xuất bản:	2024