We present a certified algorithm based on subdivision for computing an isotopic approximation to any number of algebraic curves in the plane. Our algorithm is based on the certified curve approximation algorithm of Pl...
详细信息
We present a certified algorithm based on subdivision for computing an isotopic approximation to any number of algebraic curves in the plane. Our algorithm is based on the certified curve approximation algorithm of Plantinga and Vegter. The main challenge in this algorithm is to correctly and efficiently identify and isolate all intersections between the curves. To overcome this challenge, we introduce a new and simple test that guarantees the global correctness of our output. A main step in our algorithm for approximating any number of curves is to correctly approximate a pair of curves. In addition to developing the details of this special case, we provide complexity analyses for both the number of steps and the bit-complexity of this algorithm using both worst-case bounds as well as those based on continuous amortization and condition numbers. (c) 2025 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
The coefficient sequences of multivariate rational functions appear in many areas of combinatorics. Their diagonal coefficient sequences enjoy nice arithmetic and asymptotic properties, and the field of analytic combi...
详细信息
The coefficient sequences of multivariate rational functions appear in many areas of combinatorics. Their diagonal coefficient sequences enjoy nice arithmetic and asymptotic properties, and the field of analytic combinatorics in several variables (ACSV) makes it possible to compute asymptotic expansions. We consider these methods from the point of view of effectivity. In particular, given a rational function, ACSV requires one to determine a (generically) finite collection of points that are called critical and minimal. Criticality is an algebraic condition, meaning it is well treated by classical methods in computer algebra, while minimality is a semi-algebraic condition describing points on the boundary of the domain of convergence of a multivariate power series. We show how to obtain dominant asymptotics for the diagonal coefficient sequence of multivariate rational functions under some genericity assumptions using symbolic-numeric techniques. To our knowledge, this is the first completely automatic treatment and complexity analysis for the asymptotic enumeration of rational functions in an arbitrary number of variables. (C) 2020 Elsevier Ltd. All rights reserved.
We consider the problem of symbolic-numeric integration of symbolic functions, focusing on rational functions. Using a hybrid method allows the reliable yet efficient computation of symbolic antiderivatives while avoi...
详细信息
We consider the problem of symbolic-numeric integration of symbolic functions, focusing on rational functions. Using a hybrid method allows the reliable yet efficient computation of symbolic antiderivatives while avoiding issues of ill-conditioning to which numerical methods are susceptible. We propose two alternative methods for exact input that compute the rational part of the integral using Hermite reduction and then compute the transcendental part two different ways using a combination of exact integration and efficient numerical computation of roots. The symbolic computation is done within bpas, or Basic Polynomial Algebra Subprograms, which is a highly optimized environment for polynomial computation on parallel architectures, while the numerical computation is done using the highly optimized multiprecision rootfinding package MPSolve. We provide for both algorithms computable expressions for the first-order term of a structured forward and backward error and show how, away from singularities, tolerance proportionality is achieved by adjusting the precision of the rootfinding tasks.
Let S subset of R-n be a compact basic semi-algebraic set defined as the real solution set of multivariate polynomial inequalities with rational coefficients. We design an algorithm which takes as input a polynomial s...
详细信息
ISBN:
(纸本)9781450360845
Let S subset of R-n be a compact basic semi-algebraic set defined as the real solution set of multivariate polynomial inequalities with rational coefficients. We design an algorithm which takes as input a polynomial system defining S and an integer p >= 0 and returns the n-dimensional volume of S at absolute precision 2(-p). Our algorithm relies on the relationship between volumes of semi-algebraic sets and periods of rational integrals. It makes use of algorithms computing the Picard-Fuchs differential equation of appropriate periods, properties of critical points, and high-precision numerical integration of differential equations. The algorithm runs in essentially linear time with respect to p. This improves upon the previous exponential bounds obtained by Monte-Carlo or moment-based methods. Assuming a conjecture of Dimca, the arithmetic cost of the algebraic subroutines for computing Picard-Fuchs equations and critical points is singly exponential in n and polynomial in the maximum degree of the input.
Analytic combinatorics studies the asymptotic behavior of sequences through the analytic properties of their generating functions. This article provides effective algorithms required for the study of analytic combinat...
详细信息
ISBN:
(纸本)9781450343800
Analytic combinatorics studies the asymptotic behavior of sequences through the analytic properties of their generating functions. This article provides effective algorithms required for the study of analytic combinatorics in several variables, together with their complexity analyses. Given a multivariate rational function we show how to compute its smooth isolated critical points, with respect to a polynomial map encoding asymptotic behaviour, in complexity singly exponential in the degree of its denominator. We introduce a numerical Kronecker representation for solutions of polynomial systems with rational coefficients and show that it can be used to decide several properties (0 coordinate, equal coordinates, sign conditions for real solutions, and vanishing of a polynomial) in good bit complexity. Among the critical points, those that are minimal-a property governed by inequalities on the moduli of the coordinates-typically determine the dominant asymptotics of the diagonal coefficient sequence. When the Taylor expansion at the origin has all non-negative coefficients (known as the 'combinatorial case') and under regularity conditions, we utilize this Kronecker representation to determine probabilistically the minimal critical points in complexity singly exponential in the degree of the denominator, with good control over the exponent in the bit complexity estimate. Generically in the combinatorial case, this allows one to automatically and rigorously determine asymptotics for the diagonal coefficient sequence. Examples obtained with a preliminary implementation show the wide applicability of this approach.
Given a planar curve defined by means of a real rational parametrization, we prove that the affine values of the parameter generating the real singularities of the offset are real roots of a univariate polynomial that...
详细信息
Given a planar curve defined by means of a real rational parametrization, we prove that the affine values of the parameter generating the real singularities of the offset are real roots of a univariate polynomial that can be derived from the parametrization of the original curve, without computing or making use of the implicit equation of the offset. By using this result, a finite set containing all the real singularities of the offset, and in particular all the real self-intersections of the offset, can be computed. We also report on experiments carried out in the computer algebra system Maple, showing the efficiency of the algorithm for moderate degrees. (C) 2015 Elsevier B.V. All rights reserved.
We present a certified and complete algorithm to compute arrangements of real planar algebraic curves. It computes the decomposition of the plane induced by a finite number of algebraic curves in terms of a cylindrica...
详细信息
We present a certified and complete algorithm to compute arrangements of real planar algebraic curves. It computes the decomposition of the plane induced by a finite number of algebraic curves in terms of a cylindrical algebraic decomposition. From a high-level perspective, the overall method splits into two main subroutines, namely an algorithm denoted BISOLVE to isolate the real solutions of a zero-dimensional bivariate system, and an algorithm denoted GEoTop to compute the topology of a single algebraic curve. Compared to existing approaches based on elimination techniques, we considerably improve the corresponding lifting steps in both subroutines. As a result, generic position of the input system is never assumed, and thus our algorithm never demands for any change of coordinates. In addition, we significantly limit the types of symbolic operations involved, that is, we only use resultant and gcd computations as purely symbolic operations. The latter results are achieved by combining techniques from different fields such as (modular) symbolic computation, numerical analysis and algebraic geometry. We have implemented our algorithms as prototypical contributions to the C++-project CGAL. We exploit graphics hardware to expedite the remaining symbolic computations. We have also compared our implementation with the current reference implementations, that is, LGP and Maple's ISOLATE for polynomial system solving, and CGAL'S bivariate algebraic kernel for analyses and arrangement computations of algebraic curves. For various series of challenging instances, our exhaustive experiments show that the new implementations outperform the existing ones. (C) 2013 Elsevier B.V. All rights reserved.
The goal of this paper is to present and experiment the computer aided analysis of phase portraits of some ordinary differential equations. The latter are piecewise affine, and have been primitively introduced as coar...
详细信息
ISBN:
(纸本)9781595932761
The goal of this paper is to present and experiment the computer aided analysis of phase portraits of some ordinary differential equations. The latter are piecewise affine, and have been primitively introduced as coarse-grained models of gene regulatory networks. Their simple formulation allows for numerical investigation, but their typical phase portrait is still largely unknown. They have been shown to present all the main aspects of nonlinear dynamics, including chaos. But it is still of interest to simulate random versions of these models, and to count and classify their attractors. This paper presents algorithms that allow for an automatic treatment of this kind, and apply it to four-dimensional sample systems. Contrary to previous studies, the latter have several thresholds in each direction, a fact whose consequences on the number and nature of attractors is discussed.
In the present work, we extend the standard idea of numerical parameterization (i.e., parameterization by the numerical solution of initial-value problems (IVPs) for ordinary differential equations (ODEs) to affine va...
详细信息
ISBN:
(纸本)9781581138276
In the present work, we extend the standard idea of numerical parameterization (i.e., parameterization by the numerical solution of initial-value problems (IVPs) for ordinary differential equations (ODEs) to affine varieties in ℂ;n for n≥2. We use these results with an efficient implementation in Maple to explore the use of numerical parameterization for the visualization of Riemann surfaces.
暂无评论