Automating the Design of Multigrid Methods with Evolutionary Program Synthesis

• URL: http://arxiv.org/abs/2312.14875v1
• Date: Fri, 22 Dec 2023 17:55:48 GMT
• Title: Automating the Design of Multigrid Methods with Evolutionary Program Synthesis
• Authors: Jonas Schmitt
• Abstract summary: 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 can discover multigrid methods of unprecedented structure. We present our implementation in the form of the Python framework EvoStencils, which is freely available as open-source software.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many of the most fundamental laws of nature can be formulated as partial differential equations (PDEs). Understanding these equations is, therefore, of exceptional importance for many branches of modern science and engineering. 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. To prove the feasibility of this approach, we present its implementation in the form of the Python framework EvoStencils, which is freely available as open-source software. This implementation comprises all steps from representing the algorithmic sequence of a multigrid method in the form of a directed acyclic graph of Python objects to its automatic generation and optimization using the capabilities of the code generation framework ExaStencils and the evolutionary computation library DEAP.

Related papers

• Bridging Visualization and Optimization: Multimodal Large Language Models on Graph-Structured Combinatorial Optimization [56.17811386955609]
  Graph-structured challenges are inherently difficult due to their nonlinear and intricate nature. In this study, we propose transforming graphs into images to preserve their higher-order structural features accurately. By combining the innovative paradigm powered by multimodal large language models with simple search techniques, we aim to develop a novel and effective framework.
  arXiv  Detail & Related papers  (2025-01-21T08:28:10Z)
• Towards Automated Algebraic Multigrid Preconditioner Design Using Genetic Programming for Large-Scale Laser Beam Welding Simulations [0.0]
  We employ evolutionary algorithms to construct efficient multigrid cycles from available individual components. This technology is applied to finite element simulations of the laser beam welding process.
  arXiv  Detail & Related papers  (2024-12-11T08:24:38Z)
• Evolving Algebraic Multigrid Methods Using Grammar-Guided Genetic Programming [0.0]
  We use grammar rules to generate arbitrary-shaped cycles, where smoothers and relaxation weights are chosen independently. These flexible cycles are used in Algebraic Multigrid (AMG) methods with the help of grammar rules and optimized using genetic programming. We observe that the optimized flexible cycles provide higher efficiency and better performance than the standard cycle types.
  arXiv  Detail & Related papers  (2024-12-08T08:21:35Z)
• A reinforcement learning strategy to automate and accelerate h/p-multigrid solvers [0.37109226820205005]
  Multigrid methods are very efficient but require fine-tuning of numerical parameters, such as the number of smoothing sweeps per level. This paper is to use a proximal policy optimization algorithm to automatically tune the multigrid parameters. Our findings reveal that the proposed reinforcement learning h/p-multigrid approach significantly accelerates and improves the robustness of steady-state simulations.
  arXiv  Detail & Related papers  (2024-07-18T21:26:28Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  We focus on optimisation programming (SP), Optimal Control (SOC) and Decision Processes (MDP) Recent progress in solving convex multistage Markov problems is based on cutting planes approximations of the cost-to-go functions of dynamic programming equations. Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables.
  arXiv  Detail & Related papers  (2023-03-28T01:30:40Z)
• Evolving Generalizable Multigrid-Based Helmholtz Preconditioners with Grammar-Guided Genetic Programming [0.0]
  We introduce a new approach for evolving efficient preconditioned iterative solvers for Helmholtz problems. Our approach is based on a novel context-free grammar, which enables the construction of multigrid preconditioners. We demonstrate our approach's effectiveness by evolving multigrid-based preconditioners for a two-dimensional indefinite Helmholtz problem.
  arXiv  Detail & Related papers  (2022-04-27T11:13:34Z)
• Learning optimal multigrid smoothers via neural networks [1.9336815376402723]
  We propose an efficient framework for learning optimized smoothers from operator stencils in the form of convolutional neural networks (CNNs) CNNs are trained on small-scale problems from a given type of PDEs based on a supervised loss function derived from multigrid convergence theories. Numerical results on anisotropic rotated Laplacian problems demonstrate improved convergence rates and solution time compared with classical hand-crafted relaxation methods.
  arXiv  Detail & Related papers  (2021-02-24T05:02:54Z)
• AdaLead: A simple and robust adaptive greedy search algorithm for sequence design [55.41644538483948]
  We develop an easy-to-directed, scalable, and robust evolutionary greedy algorithm (AdaLead) AdaLead is a remarkably strong benchmark that out-competes more complex state of the art approaches in a variety of biologically motivated sequence design challenges.
  arXiv  Detail & Related papers  (2020-10-05T16:40:38Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space. Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
  arXiv  Detail & Related papers  (2020-02-17T20:21:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.