Timezone: »
Efficient numerical solvers for sparse linear systems are crucial in science and engineering. One of the fastest methods for solving large-scale sparse linear systems is algebraic multigrid (AMG). The main challenge in the construction of AMG algorithms is the selection of the prolongation operator---a problem-dependent sparse matrix which governs the multiscale hierarchy of the solver and is critical to its efficiency. Over many years, numerous methods have been developed for this task, and yet there is no known single right answer except in very special cases. Here we propose a framework for learning AMG prolongation operators for linear systems with sparse symmetric positive (semi-) definite matrices. We train a single graph neural network to learn a mapping from an entire class of such matrices to prolongation operators, using an efficient unsupervised loss function. Experiments on a broad class of problems demonstrate improved convergence rates compared to classical AMG, demonstrating the potential utility of neural networks for developing sparse system solvers.
Author Information
Ilay Luz (Weizmann Institute of Science)
Meirav Galun (Weizmann Institute of Science)
Haggai Maron (NVIDIA Research)
I am a Research Scientist at NVIDIA Research. My main fields of interest are machine learning, optimization, and shape analysis. More specifically, I am working on applying deep learning to irregular domains (e.g., graphs, point clouds, and surfaces) and graph/shape matching problems. I completed my Ph.D. in 2019 at the Department of Computer Science and Applied Mathematics at the Weizmann Institute of Science under the supervision of Prof. Yaron Lipman.
Ronen Basri (Weizmann Institute of Science)
Irad Yavneh (Technion)
More from the Same Authors
-
2023 : Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel's Spectrum »
Amnon Geifman · Daniel Barzilai · Ronen Basri · Meirav Galun -
2023 : Expressive Sign Equivariant Networks for Spectral Geometric Learning »
Derek Lim · Joshua Robinson · Stefanie Jegelka · Haggai Maron -
2023 Oral: Equivariant Polynomials for Graph Neural Networks »
Omri Puny · Derek Lim · Bobak T Kiani · Haggai Maron · Yaron Lipman -
2023 Poster: Equivariant Polynomials for Graph Neural Networks »
Omri Puny · Derek Lim · Bobak T Kiani · Haggai Maron · Yaron Lipman -
2023 Oral: Equivariant Architectures for Learning in Deep Weight Spaces »
Aviv Navon · Aviv Shamsian · Idan Achituve · Ethan Fetaya · Gal Chechik · Haggai Maron -
2023 Poster: Equivariant Architectures for Learning in Deep Weight Spaces »
Aviv Navon · Aviv Shamsian · Idan Achituve · Ethan Fetaya · Gal Chechik · Haggai Maron -
2023 Poster: Graph Positional Encoding via Random Feature Propagation »
Moshe Eliasof · Fabrizio Frasca · Beatrice Bevilacqua · Eran Treister · Gal Chechik · Haggai Maron -
2022 Poster: Optimizing Tensor Network Contraction Using Reinforcement Learning »
Eli Meirom · Haggai Maron · Shie Mannor · Gal Chechik -
2022 Spotlight: Optimizing Tensor Network Contraction Using Reinforcement Learning »
Eli Meirom · Haggai Maron · Shie Mannor · Gal Chechik -
2022 Poster: Multi-Task Learning as a Bargaining Game »
Aviv Navon · Aviv Shamsian · Idan Achituve · Haggai Maron · Kenji Kawaguchi · Gal Chechik · Ethan Fetaya -
2022 Spotlight: Multi-Task Learning as a Bargaining Game »
Aviv Navon · Aviv Shamsian · Idan Achituve · Haggai Maron · Kenji Kawaguchi · Gal Chechik · Ethan Fetaya -
2021 Poster: Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networks »
Eli Meirom · Haggai Maron · Shie Mannor · Gal Chechik -
2021 Poster: From Local Structures to Size Generalization in Graph Neural Networks »
Gilad Yehudai · Ethan Fetaya · Eli Meirom · Gal Chechik · Haggai Maron -
2021 Spotlight: Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networks »
Eli Meirom · Haggai Maron · Shie Mannor · Gal Chechik -
2021 Spotlight: From Local Structures to Size Generalization in Graph Neural Networks »
Gilad Yehudai · Ethan Fetaya · Eli Meirom · Gal Chechik · Haggai Maron -
2020 Poster: Frequency Bias in Neural Networks for Input of Non-Uniform Density »
Ronen Basri · Meirav Galun · Amnon Geifman · David Jacobs · Yoni Kasten · Shira Kritchman -
2020 Poster: On Learning Sets of Symmetric Elements »
Haggai Maron · Or Litany · Gal Chechik · Ethan Fetaya -
2019 Poster: Learning to Optimize Multigrid PDE Solvers »
Daniel Greenfeld · Meirav Galun · Ronen Basri · Irad Yavneh · Ron Kimmel -
2019 Oral: Learning to Optimize Multigrid PDE Solvers »
Daniel Greenfeld · Meirav Galun · Ronen Basri · Irad Yavneh · Ron Kimmel