skip to main content


Title: Numerical Continuation on a Graphical Processing Unit for Kinematic Synthesis
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
Award ID(s):
1636017
NSF-PAR ID:
10194733
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Journal of Computing and Information Science in Engineering
Volume:
20
Issue:
6
ISSN:
1530-9827
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. The Homotopy Continuation (HC) method is known as a prevailing and robust approach for solving numerically complicated polyno- mial systems with guarantees of a global solution. In recent years we are witnessing tremendous advances in the theoretical and al- gorithmic foundations of HC. Furthermore, there are very efficient implementations of several variants of HC that solve large polyno- mial systems that we could not even imagine some years ago. The success of HC has motivated approaching even larger problems or gaining real-time performance. We propose to accelerate the HC computation significantly through a parallel implementation of path tracker in both straight line coefficient HC and parameter HC on a Graphical Processing Unit (GPU). The implementation involves computing independent tracks to convergence simulta- neously, as well as a parallel linear system solver and a parallel evaluation of Jacobian matrices and vectors. We evaluate the per- formance of our implementation using both popular benchmarking polynomial systems as well as polynomial systems of computer vi- sion applications. The experiments demonstrate that our GPU-HC provides as high as 28× and 20× faster than the multi-core Julia in polynomial benchmark problems and polynomial systems for computer vision applications, respectively. Code is made publicly available in https://rb.gy/cvcwgq. 
    more » « less
  2. 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
  3. This study presents new results on a method to solve large kinematic synthesis systems termed Finite Root Generation. The method reduces the number of startpoints used in homotopy continuation to find all the roots of a kinematic synthesis system. For a single execution, many start systems are generated with corresponding startpoints using a random process such that startpoints only track to finite roots. Current methods are burdened by computations of roots to infinity. New results include a characterization of scaling for different problem sizes, a technique for scaling down problems using cognate symmetries, and an application for the design of a spined pinch gripper mechanism. We show that the expected number of iterations to perform increases approximately linearly with the quantity of finite roots for a given synthesis problem. An implementation that effectively scales the four-bar path synthesis problem by six using its cognate structure found 100% of roots in an average of 16,546 iterations over ten executions. This marks a roughly six-fold improvement over the basic implementation of the algorithm. 
    more » « less
  4. Suppose $F:=(f_1,\ldots,f_n)$ is a system of random $n$-variate polynomials with $f_i$ having degree $\leq\!d_i$ and the coefficient of $x^{a_1}_1\cdots x^{a_n}_n$ in $f_i$ being an independent complex Gaussian of mean $0$ and variance $\frac{d_i!}{a_1!\cdots a_n!\left(d_i-\sum^n_{j=1}a_j \right)!}$. Recent progress on Smale's 17$\thth$ Problem by Lairez --- building upon seminal work of Shub, Beltran, Pardo, B\"{u}rgisser, and Cucker --- has resulted in a deterministic algorithm that finds a single (complex) approximate root of $F$ using just $N^{O(1)}$ arithmetic operations on average, where $N\!:=\!\sum^n_{i=1}\frac{(n+d_i)!}{n!d_i!}$ ($=n(n+\max_i d_i)^{O(\min\{n,\max_i d_i)\}}$) is the maximum possible total number of monomial terms for such an $F$. However, can one go faster when the number of terms is smaller, and we restrict to real coefficient and real roots? And can one still maintain average-case polynomial-time with more general probability measures? We show the answer is yes when $F$ is instead a binomial system --- a case whose numerical solution is a key step in polyhedral homotopy algorithms for solving arbitrary polynomial systems. We give a deterministic algorithm that finds a real approximate root (or correctly decides there are none) using just $O(n^3\log^2(n\max_i d_i))$ arithmetic operations on average. Furthermore, our approach allows Gaussians with arbitrary variance. We also discuss briefly the obstructions to maintaining average-case time polynomial in $n\log \max_i d_i$ when $F$ has more terms. 
    more » « less
  5. 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