An official website of the United States government
Numerical algebraic geometry provides tools for approximating solutions of polynomial systems. One such tool is the parameter homotopy, which can be an extremely efficient method to solve numerous polynomial systems that differ only in coefficients, not monomials. This technique is frequently used for solving a parameterized family of polynomial systems at multiple parameter values. This article describes Paramotopy, a parallel, optimized implementation of this technique, making use of the Bertini software package. The novel features of this implementation include allowing for the simultaneous solutions of arbitrary polynomial systems in a parameterized family on an automatically generated or manually provided mesh in the parameter space of coefficients, front ends and back ends that are easily specialized to particular classes of problems, and adaptive techniques for solving polynomial systems near singular points in the parameter space.
more »
« less
Locating the Closest Singularity in a Polynomial Homotopy
A polynomial homotopy is a family of polynomial systems, where the systems in the family depend on one parameter. If for one value of the parameter we know a regular solution, then what is the nearest value of the parameter for which the solution in the polynomial homotopy is singular? For this problem we apply the ratio theorem of Fabry. Richardson extrapolation is effective to accelerate the convergence of the ratios of the coefficients of the series expansions of the solution paths defined by the homotopy. For numerical stability, we recondition the homotopy. To compute the coefficients of the series we propose the quaternion Fourier transform. We locate the closest singularity comput- ing at a regular solution, avoiding numerical difficulties near a singularity.
more »
« less
- Award ID(s):
- 1854513
- PAR ID:
- 10463303
- Editor(s):
- Boulier, F.; England, M; Sadykov, T. M.; Vorozhtsov, E. V.
- Date Published:
- Journal Name:
- Computer Algebra in Scientific Computing. 24th International Workshop, CASC 2022 Gebze, Turkey, August 22–26, 2022 Proceedings
- Page Range / eLocation ID:
- 333-352
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Ramification points arise from singularities along solution paths of a homotopy. This paper considers ramification points of homotopies, elucidating the total number of ramification points and providing general theory regarding the properties of the set of ramification points over the same branch point. The general approach utilized in this paper is to view homotopies as lines in the parameter spaces of families of polynomial systems on a projective manifold. With this approach, the number of singularities of systems parameterized by pencils is computed under broad conditions. General conditions are given for when the singularities of the systems parameterized by a line in a space of polynomial systems have multiplicity two. General conditions are also given for there to be at most one singularity in the solution set of any system parameterized by such a line. Several examples are included to demonstrate the theoretical results.more » « less
-
Abstract This paper is about learning the parameter-to-solution map for systems of partial differential equations (PDEs) that depend on a potentially large number of parameters covering all PDE types for which a stable variational formulation (SVF) can be found. A central constituent is the notion of variationally correct residual loss function, meaning that its value is always uniformly proportional to the squared solution error in the norm determined by the SVF, hence facilitating rigorous a posteriori accuracy control. It is based on a single variational problem, associated with the family of parameter-dependent fibre problems, employing the notion of direct integrals of Hilbert spaces. Since in its original form the loss function is given as a dual test norm of the residual; a central objective is to develop equivalent computable expressions. The first critical role is played by hybrid hypothesis classes, whose elements are piecewise polynomial in (low-dimensional) spatio-temporal variables with parameter-dependent coefficients that can be represented, for example, by neural networks. Second, working with first-order SVFs we distinguish two scenarios: (i) the test space can be chosen as an $$L_{2}$$-space (such as for elliptic or parabolic problems) so that residuals can be evaluated directly as elements of $$L_{2}$$; (ii) when trial and test spaces for the fibre problems depend on the parameters (as for transport equations) we use ultra-weak formulations. In combination with discontinuous Petrov–Galerkin concepts the hybrid format is then instrumental to arrive at variationally correct computable residual loss functions. Our findings are illustrated by numerical experiments representing (i) and (ii), namely elliptic boundary value problems with piecewise constant diffusion coefficients and pure transport equations with parameter-dependent convection fields.more » « less
-
The problem of geolocation of a radiofrequency transmitter via time difference of arrival (TDOA) and frequency difference of arrival (FDOA) is given as a system of polynomial equations. This allows for the use of homotopy continuation-based methods from numerical algebraic geometry. A novel geolocation algorithm employs numerical algebraic geometry techniques in conjunction with the random sample consensus (RANSAC) method. This is all developed and demonstrated in the setting of only FDOA measurements, without loss of generality. Additionally, the problem formulation as polynomial systems immediately provides lower bounds on the number of receivers or measurements required for the solution set to consist of only isolated points.more » « less
-
Abstract This paper presents an implementation of a homotopy path tracking algorithm for polynomial numerical continuation on a graphical processing unit (GPU). The goal of this algorithm is to track homotopy curves from known roots to the unknown roots of a target polynomial system. The path tracker solves a set of ordinary differential equations to predict the next step and uses a Newton root finder to correct the prediction so the path stays on the homotopy solution curves. In order to benefit from the computational performance of a GPU, we organize the procedure so it is executed as a single instruction set, which means the path tracker has a fixed step size and the corrector has a fixed number iterations. This trade-off between accuracy and GPU computation speed is useful in numerical kinematic synthesis where a large number of solutions must be generated to find a few effective designs. In this paper, we show that our implementation of GPU-based numerical continuation yields 85 effective designs in 63 s, while an existing numerical continuation algorithm yields 455 effective designs in 2 h running on eight threads of a workstation.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
