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. 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
3. 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
4. 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
5. Vassiliev measures of complexity of open and closed curves in 3-space

   https://doi.org/10.1098/rspa.2021.0440  

   Panagiotou, Eleni; Kauffman, Louis H. (October 2021, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences)

   In this article, we define Vassiliev measures of complexity for open curves in 3-space. These are related to the coefficients of the enhanced Jones polynomial of open curves in 3-space. These Vassiliev measures are continuous functions of the curve coordinates; as the ends of the curve tend to coincide, they converge to the corresponding Vassiliev invariants of the resulting knot. We focus on the second Vassiliev measure from the enhanced Jones polynomial for closed and open curves in 3-space. For closed curves, this second Vassiliev measure can be computed by a Gauss code diagram and it has an integral formulation, the double alternating self-linking integral. The double alternating self-linking integral is a topological invariant of closed curves and a continuous function of the curve coordinates for open curves in 3-space. For polygonal curves, the double alternating self-linking integral obtains a simpler expression in terms of geometric probabilities. 

   more » « less