GAPS: Generator for Automatic Polynomial Solvers

• URL: http://arxiv.org/abs/2004.11765v1
• Date: Fri, 24 Apr 2020 14:11:28 GMT
• Title: GAPS: Generator for Automatic Polynomial Solvers
• Authors: Bo Li and Viktor Larsson
• Abstract summary: Given a system repeated with different coefficient instances, the traditional Gr"obner basis or normal form based solution is very inefficient. By precomputing such structures offline, Gr"obner basis as well as the system solutions can be solved automatically and efficiently online. The most recent tool autogen from Larsson et al. is a representative of these tools with state-of-the-art performance in solver efficiency.
• Score: 39.33174230839823
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Minimal problems in computer vision raise the demand of generating efficient automatic solvers for polynomial equation systems. Given a polynomial system repeated with different coefficient instances, the traditional Gr\"obner basis or normal form based solution is very inefficient. Fortunately the Gr\"obner basis of a same polynomial system with different coefficients is found to share consistent inner structure. By precomputing such structures offline, Gr\"obner basis as well as the polynomial system solutions can be solved automatically and efficiently online. In the past decade, several tools have been released to generate automatic solvers for a general minimal problems. The most recent tool autogen from Larsson et al. is a representative of these tools with state-of-the-art performance in solver efficiency. GAPS wraps and improves autogen with more user-friendly interface, more functionality and better stability. We demonstrate in this report the main approach and enhancement features of GAPS. A short tutorial of the software is also included.

Related papers

• Online Stability Improvement of Groebner Basis Solvers using Deep Learning [29.805408457645886]
  We show that different variable or monomial orderings lead to different elimination templates. We then prove that the original set of coefficients may contain sufficient information to train a selection of a good solver.
  arXiv  Detail & Related papers  (2024-01-17T16:51:28Z)
• Automatic Solver Generator for Systems of Laurent Polynomial Equations [1.7188280334580197]
  Given a family of triangulation (Laurent) systems with the same monomial structure but varying coefficients, find a solver that computes solutions for any family as fast as possible. We propose an automatic solver generator for systems of Laurent equations.
  arXiv  Detail & Related papers  (2023-07-01T12:12:52Z)
• RGCVAE: Relational Graph Conditioned Variational Autoencoder for Molecule Design [70.59828655929194]
  Deep Graph Variational Autoencoders are among the most powerful machine learning tools with which it is possible to address this problem. We propose RGCVAE, an efficient and effective Graph Variational Autoencoder based on: (i) an encoding network exploiting a new powerful Graph Isomorphism Network; (ii) a novel probabilistic decoding component.
  arXiv  Detail & Related papers  (2023-05-19T14:23:48Z)
• Sparse resultant based minimal solvers in computer vision and their connection with the action matrix [17.31412310131552]
  We show that for some camera geometry problems our extra-based method leads to smaller and more stable solvers than the state-of-the-art Grobner basis-based solvers. It provides a competitive alternative to popularner basis-based methods for minimal problems in computer vision.
  arXiv  Detail & Related papers  (2023-01-16T14:25:19Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  We find that a low-depth Transformer can represent the computations of any finite-state automaton. We show that a Transformer with $O(log T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We further investigate the brittleness of these solutions and propose potential mitigations.
  arXiv  Detail & Related papers  (2022-10-19T17:45:48Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  Book presents several efforts to tackle this challenge with important scientific implications. It provides alternative optimization schemes that scale well in terms of computational complexity. We present sparsity-exploiting hierarchies of relaxations, for either unconstrained or constrained problems.
  arXiv  Detail & Related papers  (2022-08-23T18:56:05Z)
• Mind Your Solver! On Adversarial Attack and Defense for Combinatorial Optimization [111.78035414744045]
  We take an initiative on developing the mechanisms for adversarial attack and defense towards optimization solvers. We present a simple yet effective defense strategy to modify the graph structure to increase the robustness of solvers.
  arXiv  Detail & Related papers  (2021-12-28T15:10:15Z)
• Efficient and Modular Implicit Differentiation [68.74748174316989]
  We propose a unified, efficient and modular approach for implicit differentiation of optimization problems. We show that seemingly simple principles allow to recover many recently proposed implicit differentiation methods and create new ones easily.
  arXiv  Detail & Related papers  (2021-05-31T17:45:58Z)
• Computing stable resultant-based minimal solvers by hiding a variable [20.402488757146692]
  Computer vision applications require robust estimation of camera geometry from a minimal number of input data measurements. In this paper, we study an interesting alternative sparse-based method for solving sparse systems of equations by hiding one variable. We show that for the studied problems, our resultant based approach leads to more stable solvers than the state-of-the-art Gr"obner bases-based solvers.
  arXiv  Detail & Related papers  (2020-07-17T07:40:10Z)

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.