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
-
-
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
-
The approximate path synthesis of four-bar linkages with symmetric coupler curves is presented. This includes the formulation of a polynomial optimization problem, a characterization of the maximum number of critical points, a complete numerical solution by homotopy continuation, and application to the design of straight line generators. Our approach specifies a desired curve and finds several optimal four-bar linkages with a coupler trace that approximates it. The objective posed simultaneously enforces kinematic accuracy, loop closure, and leads to polynomial first order necessary conditions with a structure that remains the same for any desired trace leading to a generalized result. Ground pivot locations are set as chosen parameters, and it is shown that the objective has a maximum of 73 critical points. The theoretical work is applied to the design of straight line paths. Parameter homotopy runs are executed for 1440 different choices of ground pivots for a thorough exploration. These computations found the expected linkages, namely, Watt, Evans, Roberts, Chebyshev, and other previously unreported linkages which are organized into a 2D atlas using the UMAP algorithm.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.
