Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the asymptotic and practical complexity of solving bivariate systems over the reals
251
0
0.0
(
0
)
Added by
Dimitrios Diochnos
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper is concerned with exact real solving of well-constrained, bivariate polynomial systems. The main problem is to isolate all common real roots in rational rectangles, and to determine their intersection multiplicities. We present three algorithms and analyze their asymptotic bit complexity, obtaining a bound of $sOB(N^{14})$ for the purely projection-based method, and $sOB(N^{12})$ for two subresultant-based methods: this notation ignores polylogarithmic factors, where $N$ bounds the degree and the bitsize of the polynomials. The previous record bound was $sOB(N^{14})$. Our main tool is signed subresultant sequences. We exploit recent advances on the complexity of univariate root isolation, and extend them to sign evaluation of bivariate polynomials over two algebraic numbers, and real root counting for polynomials over an extension field. Our algorithms apply to the problem of simultaneous inequalities; they also compute the topology of real plane algebraic curves in $sOB(N^{12})$, whereas the previous bound was $sOB(N^{14})$. All algorithms have been implemented in MAPLE, in conjunction with numeric filtering. We compare them against FGB/RS, system solvers from SYNAPS, and MAPLE libraries INSULATE and TOP, which compute curve topology. Our software is among the most robust, and its runtimes are comparable, or within a small constant factor, with respect to the C/C++ libraries. Key words: real solving, polynomial systems, complexity, MAPLE software
rate research
Read More
Given a black box function to evaluate an unknown rational polynomial f in Q[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine the sparsity t, the shift s (a rational), the exponents 0 <= e1 < e2 < ... < et, and the coefficients c1,...,ct in Q{0} such that f(x) = c1(x-s)^e1+c2(x-s)^e2+...+ct(x-s)^et. The computed sparsity t is absolutely minimal over any shifted power basis. The novelty of our algorithm is that the complexity is polynomial in the (sparse) representation size, and in particular is logarithmic in deg(f). Our method combines previous celebrated results on sparse interpolation and computing sparsest shifts, and provides a way to handle polynomials with extremely high degree which are, in some sense, sparse in information.
We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $epsilon$ in (0,1/3), the $epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials entirely supported on polynomials of degree at most $d$ such that for all $z in {0,1}^n$, we have $Pr_{P sim D} [P(z) = f(z) ] geq 1- epsilon$. It is known from the works of Tarui ({Theoret. Comput. Sci.} 1993) and Beigel, Reingold, and Spielman ({ Proc. 6th CCC} 1991), that the $epsilon$-error probabilistic degree of the OR function is at most $O(log n.log 1/epsilon)$. Our first observation is that this can be improved to $O{log {{n}choose{leq log 1/epsilon}}}$, which is better for small values of $epsilon$. In all known constructions of probabilistic polynomials for the OR function (including the above improvement), the polynomials $P$ in the support of the distribution $D$ have the following special structure:$P = 1 - (1-L_1).(1-L_2)...(1-L_t)$, where each $L_i(x_1,..., x_n)$ is a linear form in the variables $x_1,...,x_n$, i.e., the polynomial $1-P(x_1,...,x_n)$ is a product of affine forms. We show that the $epsilon$-error probabilistic degree of OR when restricted to polynomials of the above form is $Omega ( log a/log^2 a )$ where $a = log {{n}choose{leq log 1/epsilon}}$. Thus matching the above upper bound (up to poly-logarithmic factors).
Let $p(x)$ be an integer polynomial with $mge 2$ distinct roots $rho_1,ldots,rho_m$ whose multiplicities are $boldsymbol{mu}=(mu_1,ldots,mu_m)$. We define the D-plus discriminant of $p(x)$ to be $D^+(p):= prod_{1le i<jle m}(rho_i-rho_j)^{mu_i+mu_j}$. We first prove a conjecture that $D^+(p)$ is a $boldsymbol{mu}$-symmetric function of its roots $rho_1,ldots,rho_m$. Our main result gives an explicit formula for $D^+(p)$, as a rational function of its coefficients. Our proof is ideal-theoretic, based on re-casting the classic Poisson resultant as the symbolic Poisson formula. The D-plus discriminant first arose in the complexity analysis of a root clustering algorithm from Becker et al. (ISSAC 2016). The bit-complexity of this algorithm is proportional to a quantity $log(|D^+(p)|^{-1})$. As an application of our main result, we give an explicit upper bound on this quantity in terms of the degree of $p$ and its leading coefficient.
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.
In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves $gamma_1$ and $gamma_2$ on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy between $gamma_1$ and $gamma_2$ where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very theoretical questions in quantitative homotopy theory to more practical applications such as similarity measures on meshes and graph searching problems. We prove that Homotopy Height is in the complexity class NP, and the corresponding exponential algorithm is the best one known for this problem. This result builds on a structural theorem on monotonicity of optimal homotopies, which is proved in a companion paper. Then we show that this problem encompasses the Homotopic Frechet distance problem which we therefore also establish to be in NP, answering a question which has previously been considered in several different settings. We also provide an O(log n)-approximation algorithm for Homotopy Height on surfaces by adapting an earlier algorithm of Har-Peled, Nayyeri, Salvatipour and Sidiropoulos in the planar setting.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
