GL-Coarsener: A Graph representation learning framework to construct coarse grid hierarchy for AMG solvers

• URL: http://arxiv.org/abs/2011.09994v1
• Date: Thu, 19 Nov 2020 17:49:09 GMT
• Title: GL-Coarsener: A Graph representation learning framework to construct coarse grid hierarchy for AMG solvers
• Authors: Reza Namazi, Arsham Zolanvari, Mahdi Sani, Seyed Amir Ali Ghafourian Ghahramani
• Abstract summary: Algebraic multi-grid (AMG) methods are numerical methods used to solve large linear systems of equations efficiently. Here we propose an aggregation-based coarsening framework leveraging graph representation learning and clustering algorithms. Our method introduces the power of machine learning into the AMG research field and opens a new perspective for future researches.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In many numerical schemes, the computational complexity scales non-linearly with the problem size. Solving a linear system of equations using direct methods or most iterative methods is a typical example. Algebraic multi-grid (AMG) methods are numerical methods used to solve large linear systems of equations efficiently. One of the main differences between AMG methods is how the coarser grid is constructed from a given fine grid. There are two main classes of AMG methods; graph and aggregation based coarsening methods. Here we propose an aggregation-based coarsening framework leveraging graph representation learning and clustering algorithms. Our method introduces the power of machine learning into the AMG research field and opens a new perspective for future researches. The proposed method uses graph representation learning techniques to learn latent features of the graph obtained from the underlying matrix of coefficients. Using these extracted features, we generated a coarser grid from the fine grid. The proposed method is highly capable of parallel computations. Our experiments show that the proposed method's efficiency in solving large systems is closely comparable with other aggregation-based methods, demonstrating the high capability of graph representation learning in designing multi-grid solvers.

Related papers

• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• From Cluster Assumption to Graph Convolution: Graph-based Semi-Supervised Learning Revisited [51.24526202984846]
  Graph-based semi-supervised learning (GSSL) has long been a hot research topic. graph convolutional networks (GCNs) have become the predominant techniques for their promising performance.
  arXiv  Detail & Related papers  (2023-09-24T10:10:21Z)
• A Deep Learning algorithm to accelerate Algebraic Multigrid methods in Finite Element solvers of 3D elliptic PDEs [0.0]
  We introduce a novel Deep Learning algorithm that minimizes the computational cost of the Algebraic multigrid method when used as a finite element solver. We experimentally prove that the pooling successfully reduces the computational cost of processing a large sparse matrix and preserves the features needed for the regression task at hand.
  arXiv  Detail & Related papers  (2023-04-21T09:18:56Z)
• Agglomeration of Polygonal Grids using Graph Neural Networks with applications to Multigrid solvers [0.0]
  We propose the use of Graph Neural Networks (GNNs) to partition the connectivity graph of a computational mesh. GNNs have the advantage to process naturally and simultaneously both the graph structure of mesh and the geometrical information. Performance in terms of quality metrics is enhanced for Machine Learning (ML) strategies, with GNNs featuring a lower computational cost online.
  arXiv  Detail & Related papers  (2022-10-31T16:30:48Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Fine-grained Graph Learning for Multi-view Subspace Clustering [2.4094285826152593]
  We propose a fine-grained graph learning framework for multi-view subspace clustering (FGL-MSC) The main challenge is how to optimize the fine-grained fusion weights while generating the learned graph that fits the clustering task. Experiments on eight real-world datasets show that the proposed framework has comparable performance to the state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-01-12T18:00:29Z)
• Graph Signal Restoration Using Nested Deep Algorithm Unrolling [85.53158261016331]
  Graph signal processing is a ubiquitous task in many applications such as sensor, social transportation brain networks, point cloud processing, and graph networks. We propose two restoration methods based on convexindependent deep ADMM (ADMM) parameters in the proposed restoration methods are trainable in an end-to-end manner.
  arXiv  Detail & Related papers  (2021-06-30T08:57:01Z)
• Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement Learning [0.0]
  A system of linear equations defines a graph on the set of unknowns. Each level of a multigrid solver requires the selection of an appropriate coarse graph along with restriction and operators that map to and from the coarse representation. It has been demonstrated that it is possible to directly learn the AMG and restriction operators, given a coarse graph selection. We propose a sparse method using a reinforcement learning agent based on graph neural networks (GNNs)
  arXiv  Detail & Related papers  (2021-06-03T13:57:32Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)
• Learning Algebraic Multigrid Using Graph Neural Networks [34.32501734380907]
  We train a single graph neural network to learn a mapping from an entire class of such matrices to prolongation operators. Experiments on a broad class of problems demonstrate improved convergence rates compared to classical AMG.
  arXiv  Detail & Related papers  (2020-03-12T12:36:48Z)

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.