Efficient algorithms for computing rational first integrals and Darboux polynomials of planar polynomial vector fields
Copyright policy )Efficient algorithms for computing rational first integrals and Darboux polynomials of planar polynomial vector fields
We present fast algorithms for computing rational first integrals with bounded degree of a planar polynomial vector field. Our approach is inspired by an idea of Ferragut and Giacomini. We improve upon their work by proving that rational first integrals can be computed via systems of linear equations instead of systems of quadratic equations. This leads to a probabilistic algorithm with arithmetic complexity $\bigOsoft(N^{2 ω})$ and to a deterministic algorithm solving the problem in $\bigOsoft(d^2N^{2 ω+1})$ arithmetic operations, where $N$ denotes the given bound for the degree of the rational first integral, and where $d \leq N$ is the degree of the vector field, and $ω$ the exponent of linear algebra. We also provide a fast heuristic variant which computes a rational first integral, or fails, in $\bigOsoft(N^{ω+2})$ arithmetic operations. By comparison, the best previous algorithm uses at least $d^{ω+1}\, N^{4ω+4}$ arithmetic operations. We then show how to apply a similar method to the computation of Darboux polynomials. The algorithms are implemented in a Maple package which is available to interested readers with examples showing its efficiency.
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computer Science - Symbolic Computation, FOS: Computer and information sciences, [NLIN.NLIN-SI] Nonlinear Sciences [physics]/Exactly Solvable and Integrable Systems [nlin.SI], FOS: Physical sciences, [MATH.MATH-CA]Mathematics [math]/Classical Analysis and ODEs [math.CA], Symbolic Computation (cs.SC), Symbolic computation and algebraic computation, Rational first integral, 510, spectrum, Computer Science - Data Structures and Algorithms, Classical Analysis and ODEs (math.CA), FOS: Mathematics, [NLIN.NLIN-SI]Nonlinear Sciences [physics]/Exactly Solvable and Integrable Systems [nlin.SI], Analysis of algorithms, Data Structures and Algorithms (cs.DS), [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], algorithm, Nonlinear Sciences - Exactly Solvable and Integrable Systems, [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], [MATH.MATH-CA] Mathematics [math]/Classical Analysis and ODEs [math.CA], 004, Mathematics - Classical Analysis and ODEs, Explicit solutions, first integrals of ordinary differential equations, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Darboux polynomials, Exactly Solvable and Integrable Systems (nlin.SI)
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computer Science - Symbolic Computation, FOS: Computer and information sciences, [NLIN.NLIN-SI] Nonlinear Sciences [physics]/Exactly Solvable and Integrable Systems [nlin.SI], FOS: Physical sciences, [MATH.MATH-CA]Mathematics [math]/Classical Analysis and ODEs [math.CA], Symbolic Computation (cs.SC), Symbolic computation and algebraic computation, Rational first integral, 510, spectrum, Computer Science - Data Structures and Algorithms, Classical Analysis and ODEs (math.CA), FOS: Mathematics, [NLIN.NLIN-SI]Nonlinear Sciences [physics]/Exactly Solvable and Integrable Systems [nlin.SI], Analysis of algorithms, Data Structures and Algorithms (cs.DS), [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], algorithm, Nonlinear Sciences - Exactly Solvable and Integrable Systems, [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], [MATH.MATH-CA] Mathematics [math]/Classical Analysis and ODEs [math.CA], 004, Mathematics - Classical Analysis and ODEs, Explicit solutions, first integrals of ordinary differential equations, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Darboux polynomials, Exactly Solvable and Integrable Systems (nlin.SI)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).18 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!