An Improved Upper Complexity Bound for the Topology Computation of a Real Algebraic Plane Curve

The computation of the topological shape of a real algebraic plane curve is usually driven by the study of the behavior of the curve around its critical points (which includes also the singular points). In this paper we present a new algorithm computing the topological shape of a real algebraic plane curve whose complexity is better than the best algorithms known. This is due to the avoiding, through a sufficiently good change of coordinates, of real root computations on polynomials with coefficients in a simple real algebraic extension of to deal with the critical points of the considered curve. In fact, one of the main features of this algorithm is that its complexity is dominated by the characterization of the real roots of the discriminant of the polynomial defining the considered curve.     

TRACING A PLANAR ALGEBRAIC CURVE

In this paper, an algorithm that determines a real algebraic curve is outlined. Its basicstep is to divide the plane into subdomain1s that include only simple branches of the algebraic curvewithout singular points. Each of the branches is then stably and efficiently traced in the particularsubdomain. Except for tracing, the algorithm requires only a couple of simple operations on poly-nomials that ran be carried out exacrly if the coefficients are rational, and the determination of the real roots of several univariate polynomials.     

On the Topology of Real Algebraic Plane Curves

We revisit the problem of computing the topology and geometry of a real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and critical points, is also relevant. A challenge is to compute efficiently this information for the given coordinate system even if the curve is not in generic position. Previous methods based on the cylindrical algebraic decomposition use sub-resultant sequences and computations with polynomials with algebraic coefficients. A novelty of our approach is to replace these tools by Gröbner basis computations and isolation with rational univariate representations. This has the advantage of avoiding computations with polynomials with algebraic coefficients, even in non-generic positions. Our algorithm isolates critical points in boxes and computes a decomposition of the plane by rectangular boxes. This decomposition also induces a new approach for computing an arrangement of polylines isotopic to the input curve. We also present an analysis of the complexity of our algorithm. An implementation of our algorithm demonstrates its efficiency, in particular on high-degree non-generic curves.     

Algorithms for solving Hermite interpolation problems using the Fast Fourier Transform

We present a method for computing the Hermite interpolation polynomial based on equally spaced nodes on the unit circle with an arbitrary number of derivatives in the case of algebraic and Laurent polynomials. It is an adaptation of the method of the Fast Fourier Transform (FFT) for this type of problems with the following characteristics: easy computation, small number of operations and easy implementation.In the second part of the paper we adapt the algorithm for computing the Hermite interpolation polynomial based on the nodes of the Tchebycheff polynomials and we also study Hermite trigonometric interpolation problems.     

Quadratically Convergent Method for Simultaneously Approaching the Roots of Polynomial Solutions of a Class of Differential Equations: Application to Orthogonal Polynomials

This paper investigates the application of the method introduced by L. Pasquini (1989) for simultaneously approaching the zeros of polynomial solutions to a class of second-order linear homogeneous ordinary differential equations with polynomial coefficients to a particular case in which these polynomial solutions have zeros symmetrically arranged with respect to the origin. The method is based on a family of nonlinear equations which is associated with a given class of differential equations. The roots of the nonlinear equations are related to the roots of the polynomial solutions of differential equations considered. Newton's method is applied to find the roots of these nonlinear equations. In (Pasquini, 1994) the nonsingularity of the roots of these nonlinear equations is studied. In this paper, following the lines in (Pasquini, 1994), the nonsingularity of the roots of these nonlinear equations is studied. More favourable results than the ones in (Pasquini, 1994) are proven in the particular case of polynomial solutions with symmetrical zeros. The method is applied to approximate the roots of Hermite–Sobolev type polynomials and Freud polynomials. A lower bound for the smallest positive root of Hermite–Sobolev type polynomials is given via the nonlinear equation. The quadratic convergence of the method is proven. A comparison with a classical method that uses the Jacobi matrices is carried out. We show that the algorithm derived by the proposed method is sometimes preferable to the classical QR type algorithms for computing the eigenvalues of the Jacobi matrices even if these matrices are real and symmetric.     

Real polynomial iterative roots in the case of nonmonotonicity height ≥ 2

It is known that a strictly piecewise monotone function with nonmonotonicity height ≥ 2 on a compact interval has no iterative roots of order greater than the number of forts. An open question is: Does it have iterative roots of order less than or equal to the number of forts? An answer was given recently in the case of "equal to". Since many theories of resultant and algebraic varieties can be applied to computation of polynomials, a special class of strictly piecewise monotone functions, in this paper we investigate the question in the case of "less than" for polynomials. For this purpose we extend the question from a compact interval to the whole real line and give a procedure of computation for real polynomial iterative roots. Applying the procedure together with the theory of discriminants, we find all real quartic polynomials of non-monotonicity height 2 which have quadratic polynomial iterative roots of order 2 and answer the question.     

Approximate decoupling of multivariate polynomials using weighted tensor decomposition

Many scientific and engineering disciplines use multivariate polynomials. Decomposing a multivariate polynomial vector function into a sandwiched structure of univariate polynomials surrounded by linear transformations can provide useful insight into the function while reducing the number of parameters. Such a decoupled representation can be realized with techniques based on tensor decomposition methods, but these techniques have only been studied in the exact case. Generalizing the existing techniques to the noisy case is an important next step for the decoupling problem. For this extension, we have considered a weight factor during the tensor decomposition process, leading to an alternating weighted least squares scheme. In addition, we applied the proposed weighted decoupling algorithm in the area of system identification, and we observed smaller model errors with the weighted decoupling algorithm than those with the unweighted decoupling algorithm.     

A new algorithm for fixed design regression and denoising

In this paper, we present a new algorithm to estimate a regression function in a fixed design regression model, by piecewise (standard and trigonometric) polynomials computed with an automatic choice of the knots of the subdivision and of the degrees of the polynomials on each sub-interval. First we give the theoretical background underlying the method: the theoretical performances of our penalized least-squares estimator are based on non-asymptotic evaluations of a mean-square type risk. Then we explain how the algorithm is built and possibly accelerated (to face the case when the number of observations is great), how the penalty term is chosen and why it contains some constants requiring an empirical calibration. Lastly, a comparison with some well-known or recent wavelet methods is made: this brings out that our algorithm behaves in a very competitive way in term of denoising and of compression.     

关于平面四次Bézier曲线的拐点与奇点

在计算几何中,已给出了三次Bezier曲线的保凸性的充要条件,并进行了几何解释。本文则是导出形式简洁的拐点和奇点方程并对四次Bezier曲线的拐点和奇点的分布进行讨论。按Bezier曲线的拐点个数进行分类,还得到了四次Bezier曲线有奇点的充分必要条件,并给出几个数值实例,实例说明,不但非凸的单纯特征多角形可以有凸的Bezier曲线段,而且非单纯特征多角形也可以有凸的Bezier曲线段。四次Bezier曲线的奇点和拐点是可以共存的。     

Global polynomial approximation for Symm's equation on polygons

Summary. To solve 1D linear integral equations on bounded intervals with nonsmooth input functions and solutions, we have recently proposed a quite general procedure, that is essentially based on the introduction of a nonlinear smoothing change of variable into the integral equation and on the approximation of the transformed solution by global algebraic polynomials. In particular, the new procedure has been applied to weakly singular equations of the second kind and to solve the generalized air foil equation for an airfoil with a flap. In these cases we have obtained arbitrarily high orders of convergence through the solution of very-well conditioned linear systems. In this paper, to enlarge the domain of applicability of our technique, we show how the above procedure can be successfully used also to solve the classical Symm's equation on a piecewise smooth curve. The collocation method we propose, applied to the transformed equation and based on Chebyshev polynomials of the first kind, has shown to be stable and convergent. A comparison with some recent numerical methods using splines or trigonometric polynomials shows that our method is highly competitive. Received October 1, 1998 / Revised version received September 27, 1999 / Published online June 21, 2000     

A bisection method for measuring the distance of a quadratic matrix polynomial to the quadratic matrix polynomials that are singular on the unit circle

The computation of the distance of a quadratic matrix polynomial to the quadratic matrix polynomials that are singular on the unit circle is investigated. The emphasis is placed on backward stable methods that transform the computation of the distance to a palindromic eigenvalue problem for which structure-preserving eigensolvers can be utilized in conjunction with a bisection algorithm. Reliability of the suggested methods is guaranteed by a novel error analysis.     

Counting the number of distinct real roots of certain polynomials by Bezoutian and the Galois groups over the rational number field

In this article, we count the number of distinct real roots of certain polynomials in terms of Bezoutian form. As an application, we construct certain irreducible polynomials over the rational number field which have given number of real roots and by the result of Oz Ben-Shimol [On Galois groups of prime degree polynomials with complex roots, Algebra Disc. Math. 2 (2009), pp. 99–107], we obtain an algorithm to construct irreducible polynomials of prime degree p whose Galois groups are isomorphic to S _p or A _p .     

Computing multiple roots of inexact polynomials

We present a combination of two algorithms that accurately calculate multiple roots of general polynomials.

Algorithm I transforms the singular root-finding into a regular nonlinear least squares problem on a pejorative manifold, and it calculates multiple roots simultaneously from a given multiplicity structure and initial root approximations. To fulfill the input requirement of Algorithm I, we develop a numerical GCD-finder containing a successive singular value updating and an iterative GCD refinement as the main engine of Algorithm II that calculates the multiplicity structure and the initial root approximation. While limitations exist in certain situations, the combined method calculates multiple roots with high accuracy and consistency in practice without using multiprecision arithmetic, even if the coefficients are inexact. This is perhaps the first blackbox-type root-finder with such capabilities.

To measure the sensitivity of the multiple roots, a structure-preserving condition number is proposed and error bounds are established. According to our computational experiments and error analysis, a polynomial being ill-conditioned in the conventional sense can be well conditioned with the multiplicity structure being preserved, and its multiple roots can be computed with high accuracy.

     

Polynomial complexity algorithms for computational problems in the theory of algebraic curves

It is proved that the classical algorithm for constructing Newton-Puiseux expansions for the roots of polynomials using the method of Newton polygons is of polynomial complexity in the notation length of the expansion coefficients. This result is used, in the case of a ground field of characteristic O, to construct polynomial-time algorithms for factoring polynomials over fields of formal power series, and for fundamental computational problems in the theory of algebraic curves, such as curve normalization.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 176, pp. 127–150, 1989.     

Two‐dimensional shifted Legendre polynomial collocation method for electromagnetic waves in dielectric media via almost operational matrices

In this paper, a numerical solution of fractional partial differential equations (FPDEs) for electromagnetic waves in dielectric media will be discussed. For the solution of FPDEs, we developed a numerical collocation method using an algorithm based on two‐dimensional shifted Legendre polynomials approximation, which is proposed for electromagnetic waves in dielectric media. By implementing the partial Riemann–Liouville fractional derivative operators, two‐dimensional shifted Legendre polynomials approximation and its operational matrix along with collocation method are used to convert FPDEs first into weakly singular fractional partial integro‐differential equations and then converted weakly singular fractional partial integro‐differential equations into system of algebraic equation. Some results concerning the convergence analysis and error analysis are obtained. Illustrative examples are included to demonstrate the validity and applicability of the technique. Copyright © 2017 John Wiley & Sons, Ltd.     

Number of zeros of interval polynomials

In this paper, we develop a rigorous algorithm for counting the real interval zeros of polynomials with perturbed coefficients that lie within a given interval, without computing the roots of any polynomials. The result generalizes Sturm’s Theorem for counting the roots of univariate polynomials to univariate interval polynomials.     

Biorthogonal decompositions of the Radon transform by multivariate interpolation

The concept of biorthogonal and singular value decompositions is a valuable tool in the examination of ill-posed inverse problems such as the inversion of the Radon transform. By application of the theory of multivariate interpolation, e. g. the set of Lagrange polynomials with respect to the space of homogeneous spherical polynomials, we determine new biorthogonal decompositions of the Radon transform. We consider the case of functions with support in the unit ball and the case of functions with support ?^r. In both cases we assume that the functions are square integrable with respect to some weight functions. In the important special case of square integrable functions with respect to the unit ball the structure of the biorthogonal decompositions is easier in comparison with the known singular and biorthogonal decompositions. Especially the calculation of the unknown expansion coefficients can be done by using arbitrary fundamental systems (μ-resolving data set in terms of tomography with a minimum number of nodes) and simplifies essentially. The decompositions are based on a system of zonal (ridge) Gegenbauer (ultraspherical) polynomials which are used in the theory of the Radon transform and in the field of numerical algorithms for the inversion of the transform.     

Interpolation of harmonic functions based on Radon projections

We consider an algebraic method for reconstruction of a harmonic function in the unit disk via a finite number of values of its Radon projections. The approach is to seek a harmonic polynomial which matches given values of Radon projections along some chords of the unit circle. We prove an analogue of the famous Marr’s formula for computing the Radon projection of the basis orthogonal polynomials in our setting of harmonic polynomials. Using this result, we show unique solvability for a family of schemes where all chords are chosen at equal distance to the origin. For the special case of chords forming a regular convex polygon, we prove error estimates on the unit circle and in the unit disk. We present an efficient reconstruction algorithm which is robust with respect to noise in the input data and provide numerical examples.     

Simple algorithms for approximating all roots of a polynomial with real roots

We present a simple algorithm for approximating all roots of a polynomial p(x) when it has only real roots. The algorithm is based on some interesting properties of the polynomials appearing in the Extended Euclidean Scheme for p(x) and p′(x). For example, it turns out that these polynomials are orthogonal; as a consequence, we are able to limit the precision required by our algorithm in intermediate steps. A parallel implementation of this algorithm yields a P-uniform NC₂ circuit, and the bit complexity of its sequential implementation is within a polylog factor of the bit complexity of the best known algorithm for the problem.     

Factorizations of tropical and sign polynomials

In this text, we study factorizations of polynomials over the tropical hyperfield and the sign hyperfield, which we call tropical polynomials and sign polynomials, respectively. We classify all irreducible polynomials in either case. We show that tropical polynomials factor uniquely into irreducible factors, but that unique factorization fails for sign polynomials. We describe division algorithms for tropical and sign polynomials by linear terms that correspond to roots of the polynomials.