More Like this

1. Locating the Closest Singularity in a Polynomial Homotopy

   Verschelde, J; Viswanathan, K. (July 2023, Computer Algebra in Scientific Computing. 24th International Workshop, CASC 2022 Gebze, Turkey, August 22–26, 2022 Proceedings)

   Boulier, F.; England, M; Sadykov, T. M.; Vorozhtsov, E. V. (Ed.)

   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
2. Ramification points of homotopies: Enumeration and general theory

   https://doi.org/10.1515/advgeom-2025-0025  

   Sommese, Andrew J; Hauenstein, Jonathan D; Hills, Caroline; Wampler, Charles W (October 2025, Advances in Geometry)

   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
3. Exponential Automatic Amortized Resource Analysis

   https://doi.org/10.1007/978-3-030-45231-5_19  

   Kahn, David M.; Hoffmann, Jan (April 2020, FoSSaCS 2020: Foundations of Software Science and Computation Structures)

   Automatic amortized resource analysis (AARA) is a type-based technique for inferring concrete (non-asymptotic) bounds on a program's resource usage. Existing work on AARA has focused on bounds that are polynomial in the sizes of the inputs. This paper presents and extension of AARA to exponential bounds that preserves the benefits of the technique, such as compositionality and efficient type inference based on linear constraint solving. A key idea is the use of the Stirling numbers of the second kind as the basis of potential functions, which play the same role as the binomial coefficients in polynomial AARA. To formalize the similarities with the existing analyses, the paper presents a general methodology for AARA that is instantiated to the polynomial version, the exponential version, and a combined system with potential functions that are formed by products of Stirling numbers and binomial coefficients. The soundness of exponential AARA is proved with respect to an operational cost semantics and the analysis of representative example programs demonstrates the effectiveness of the new analysis. 

   more » « less
4. Parallel Path Tracking for Homotopy Continuation using GPU

   Chiang-Heng Chien; Hongyi Fan; Ahmad Abdelfattah; Elias Tsigaridas; Stanimire Tomov; Benjamin Kimia (July 2022, Proceedings of the International Symposium on Symbolic and Algebraic Computation)

   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
5. Variationally correct neural residual regression for parametric PDEs: on the viability of controlled accuracy

   https://doi.org/10.1093/imanum/draf073  

   Bachmayr, Markus; Dahmen, Wolfgang; Oster, Mathias (October 2025, IMA Journal of Numerical Analysis)

   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