Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe D-plus Discriminant and Complexity of Root Clustering
69
0
0.0
(
0
)
Added by
Jing Yang
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We give a separation bound for the complex roots of a trinomial $f in mathbb{Z}[X]$. The logarithm of the inverse of our separation bound is polynomial in the size of the sparse encoding of $f$; in particular, it is polynomial in $log (deg f)$. It is known that no such bound is possible for 4-nomials (polynomials with 4 monomials). For trinomials, the classical results (which are based on the degree of $f$ rather than the number of monomials) give separation bounds that are exponentially worse.As an algorithmic application, we show that the number of real roots of a trinomial $f$ can be computed in time polynomial in the size of the sparse encoding of~$f$. The same problem is open for 4-nomials.
This paper revisits an algorithm for isolating real roots of univariate polynomials based on continued fractions. It follows the work of Vincent, Uspen- sky, Collins and Akritas, Johnson and Krandick. We use some tricks, especially a new algorithm for computing an upper bound of positive roots. In this way, the algorithm of isolating real roots is improved. The complexity of our method for computing an upper bound of positive roots is O(n log(u+1)) where u is the optimal upper bound satisfying Theorem 3 and n is the degree of the polynomial. Our method has been implemented as a software package logcf using C++ language. For many benchmarks logcf is two or three times faster than the function RootIntervals of Mathematica. And it is much faster than another continued fractions based software CF, which seems to be one of the fastest available open software for exact real root isolation. For those benchmarks which have only real roots, logcf is much faster than Sleeve and eigensolve which are based on numerical computation.
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
In an earlier article together with Carlos DAndrea [BDKSV2017], we described explicit expressions for the coefficients of the order-$d$ polynomial subresultant of $(x-alpha)^m$ and $(x-beta)^n $ with respect to Bernsteins set of polynomials ${(x-alpha)^j(x-beta)^{d-j}, , 0le jle d}$, for $0le d<min{m, n}$. The current paper further develops the study of these structured polynomials and shows that the coefficients of the subresultants of $(x-alpha)^m$ and $(x-beta)^n$ with respect to the monomial basis can be computed in linear arithmetic complexity, which is faster than for arbitrary polynomials. The result is obtained as a consequence of the amazing though seemingly unnoticed fact that these subresultants are scalar multiples of Jacobi polynomials up to an affine change of variables.
In semi-supervised fuzzy clustering, this paper extends the traditional pairwise constraint (i.e., must-link or cannot-link) to fuzzy pairwise constraint. The fuzzy pairwise constraint allows a supervisor to provide the grade of similarity or dissimilarity between the implicit fuzzy vectors of a pair of samples. This constraint can present more complicated relationship between the pair of samples and avoid eliminating the fuzzy characteristics. We propose a fuzzy discriminant clustering model (FDC) to fuse the fuzzy pairwise constraints. The nonconvex optimization problem in our FDC is solved by a modified expectation-maximization algorithm, involving to solve several indefinite quadratic programming problems (IQPPs). Further, a diagonal block coordinate decent (DBCD) algorithm is proposed for these IQPPs, whose stationary points are guaranteed, and the global solutions can be obtained under certain conditions. To suit for different applications, the FDC is extended into various metric spaces, e.g., the Reproducing Kernel Hilbert Space. Experimental results on several benchmark datasets and facial expression database demonstrate the outperformance of our FDC compared with some state-of-the-art clustering models.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
