Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRational Solutions of Underdetermined Polynomial Equations
69
0
0.0
(
0
)
Added by
Thomas Wolf
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper we report on an application of computer algebra in which mathematical puzzles are generated of a type that had been widely used in mathematics contests by a large number of participants worldwide. The algorithmic aspect of our work provides a method to compute rational solutions of single polynomial equations that are typically large with $10^2 ldots 10^5$ terms and that are heavily underdetermined. This functionality was obtained by adding modules for a new type of splitting of equations to the existing package CRACK that is normally used to solve polynomial algebraic and differential systems.
rate research
Read More
Mahler equations relate evaluations of the same function $f$ at iterated $b$th powers of the variable. They arise in particular in the study of automatic sequences and in the complexity analysis of divide-and-conquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with number-theoretic questions. A difficulty in the manipulation of Mahler equations is the exponential blow-up of degrees when applying a Mahler operator to a polynomial. In this work, we present algorithms for solving linear Mahler equations for series, polynomials, and rational functions, and get polynomial-time complexity under a mild assumption. Incidentally, we develop an algorithm for computing the gcrd of a family of linear Mahler operators.
This paper is concerned with certifying that a given point is near an exact root of an overdetermined or singular polynomial system with rational coefficients. The difficulty lies in the fact that consistency of overdetermined systems is not a continuous property. Our certification is based on hybrid symbolic-numeric methods to compute the exact rational univariate representation (RUR) of a component of the input system from approximate roots. For overdetermined polynomial systems with simple roots, we compute an initial RUR from approximate roots. The accuracy of the RUR is increased via Newton iterations until the exact RUR is found, which we certify using exact arithmetic. Since the RUR is well-constrained, we can use it to certify the given approximate roots using alpha-theory. To certify isolated singular roots, we use a determinantal form of the isosingular deflation, which adds new polynomials to the original system without introducing new variables. The resulting polynomial system is overdetermined, but the roots are now simple, thereby reducing the problem to the overdetermined case. We prove that our algorithms have complexity that are polynomial in the input plus the output size upon successful convergence, and we use worst case upper bounds for termination when our iteration does not converge to an exact RUR. Examples are included to demonstrate the approach.
We study the rational solutions of the Abel equation $x=A(t)x^3+B(t)x^2$ where $A,Bin C[t]$. We prove that if $deg(A)$ is even or $deg(B)>(deg(A)-1)/2$ then the equation has at most two rational solutions. For any other case, an upper bound on the number of rational solutions is obtained. Moreover, we prove that if there are more than $(deg(A)+1)/2$ rational solutions then the equation admits a Darboux first integral.
Quantifier elimination over the reals is a central problem in computational real algebraic geometry, polynomial system solving and symbolic computation. Given a semi-algebraic formula (whose atoms are polynomial constraints) with quantifiers on some variables, it consists in computing a logically equivalent formula involving only unquantified variables. When there is no alternation of quantifiers, one has a one block quantifier elimination problem. This paper studies a variant of the one block quantifier elimination in which we compute an almost equivalent formula of the input. We design a new probabilistic efficient algorithm for solving this variant when the input is a system of polynomial equations satisfying some regularity assumptions. When the input is generic, involves $s$ polynomials of degree bounded by $D$ with $n$ quantified variables and $t$ unquantified ones, we prove that this algorithm outputs semi-algebraic formulas of degree bounded by $mathcal{D}$ using $O {widetilde{~}}left ((n-s+1) 8^{t} mathcal{D}^{3t+2} binom{t+mathcal{D}}{t} right )$ arithmetic operations in the ground field where $mathcal{D} = 2(n+s) D^s(D-1)^{n-s+1} binom{n}{s}$. In practice, it allows us to solve quantifier elimination problems which are out of reach of the state-of-the-art (up to $8$ variables).
In this paper, the partially party-time ($PT$) symmetric nonlocal Davey-Stewartson (DS) equations with respect to $x$ is called $x$-nonlocal DS equations, while a fully $PT$ symmetric nonlocal DSII equation is called nonlocal DSII equation. Three kinds of solutions, namely breather, rational and semi-rational solutions for these nonlocal DS equations are derived by employing the bilinear method. For the $x$-nonlocal DS equations, the usual ($2+1$)-dimensional breathers are periodic in $x$ direction and localized in $y$ direction. Nonsingular rational solutions are lumps, and semi-rational solutions are composed of lumps, breathers and periodic line waves. For the nonlocal DSII equation, line breathers are periodic in both $x$ and $y$ directions with parallels in profile, but localized in time. Nonsingular rational solutions are ($2+1$)-dimensional line rogue waves, which arise from a constant background and disappear into the same constant background, and this process only lasts for a short period of time. Semi-rational solutions describe interactions of line rogue waves and periodic line waves.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
