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.     

Computing complex and real tropical curves using monodromy

Tropical varieties capture combinatorial information about how coordinates of points in a classical variety approach zero or infinity. We present algorithms for computing the rays of a complex and real tropical curve defined by polynomials with constant coefficients. These algorithms rely on homotopy continuation, monodromy loops, and Cauchy integrals. Several examples are presented which are computed using an implementation that builds on the numerical algebraic geometry software Bertini.     

On Computing Zeros of a Bivariate Bernstein Polynomial

1.IntroductionIn[6]and[4],theproblemoffindingtheintersectionofacubicB6zierpatchandaplanewasconsidered.[6]consideredarectangular,and[41atriangularpatch.SincetheBernsteinoperatorB.:f-Bn(f)preserveslinearfunctions,theproblemwassimplifiedtothecomputationofzerosofabivariateBernsteinpolynomialB.(f).BothpaPersproducedsimpleandefficientcomputationalalgorithms.Itisbaseduponthefollowingidea:determinethepointswhereinsidethesupportthetopologyofzerosofB.(f)changes.Thiswasdonebyrestrictingthebivariatepo…     

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.     

Real plane algebraic curves

We study real algebraic plane curves, at an elementary level, using as little algebra as possible. Both cases, affine and projective, are addressed. A real curve is infinite, finite or empty according to the fact that a minimal polynomial for the curve is indefinite, semi-definite nondefinite or definite. We present a discussion about isolated points. By means of the P operator, these points can be easily identified for curves defined by minimal polynomials of order bigger than one. We also discuss the conditions that a curve must satisfy in order to have a minimal polynomial. Finally, we list the most relevant topological properties of affine and projective, complex and real plane algebraic curves.     

To solving multiparameter problems of algebra. 10. Computing zeros of a scalar polynomial

The paper considers the problem of computing zeros of scalar polynomials in several variables. The zeros of a polynomial are subdivided into the regular (eigen-and mixed) zeros and the singular ones. An algorithm for computing regular zeros, based on a decomposition of a given polynomial into a product of primitive polynomials, is suggested. The algorithm is applied to solving systems of nonlinear algebraic equations. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 346, 2007, pp. 119–130.     

A new tangentially stabilized 3D curve evolution algorithm and its application in virtual colonoscopy

In this paper we develop a new efficient and stable Lagrangian numerical method for computing the evolution of 3D curves driven in the normal plane by a driving force and curvature. This new method contains asymptotically uniform tangential redistribution of grid points designed originally for 3D curve evolution in this paper which makes our computations stable and is crucial for the presented application. Together with the design of new tangentially stabilized algorithm for 3D evolving curves, we develop a new method for the fully automatic finding of the optimal trajectory of the camera in the virtual colonoscopy. The proposed method consists of three steps: 3D segmentation of the colon from CT images, finding an initial trajectory guess inside the segmented 3D subvolumes, and driving the initial 3D curve to its optimal position. To that goal, a suitable intrinsic advection-diffusion partial differential equation with a driving force is designed and solved numerically in fast and robust way in order to find a smooth uniformly discretized 3D curve representing the ideal path of the camera in the virtual colonoscopy.     

Inversion of Analytic Functions via Canonical Polynomials: A Matrix Approach

An alternative to Lagrange inversion for solving analytic systems is our technique of dual vector fields. We implement this approach using matrix multiplication that provides a fast algorithm for computing the coefficients of the inverse function. Examples include calculating the critical points of the sinc function. Maple procedures are included which can be directly translated for doing numerical computations in Java or C. A preliminary version of this paper has been presented at AISC 2006.     

Real intersection points of piecewise algebraic curves

The piecewise algebraic curve, as the set of zeros of a bivariate spline function, is a generalization of the classical algebraic curve. In this work, we present an algorithm for computing the real intersection points of piecewise algebraic curves. It is primarily based on the interval zeros of the univariate interval polynomial in Bernstein form. An illustrative example is provided to show that the proposed algorithm is flexible.     

An Effective Version of Belyi's Theorem

We compute bounds on covering maps that arise in Belyi's Theorem. In particular, we construct a library of height properties and then apply it to algorithms that produce Belyi maps. Such maps are used to give coverings from algebraic curves to the projective line ramified over at most three points. The computations here give upper bounds on the degree and coefficients of polynomials and rational functions over the rationals that send a given set of algebraic numbers to the set {0,1,∞} with the additional property that the only critical values are also contained in {0,1,∞}.     

Complex algebraic plane curves via their links at infinity

Summary Considering that the study of plane cuves has an over 2000 year history and is the seed from which modern algebraic geometry grew, surprisingly little is known about the topology of affine algebraic plane curves. We topologically classify regular algebraic plane curves in complex affine 2-space using splice diagrams: certain decorated trees that code Puiseux data at infinity. (The regularity condition — that the curve be a typical fiber of its defining polynomial — can conjecturally be avoided.) We also show that the splice diagram determines such algebraic information as the minimal degree of the curve, even in the irregular case. Among other things, this enables algebraic classification of regular algebraic plane curves with given topology.     

Determination of the limits for multivariate rational functions

The purpose of this paper is to solve the problem of determining the limits of multivariate rational functions.It is essential to decide whether or not limxˉ→0f g=0 for two non-zero polynomials f,g∈R[x1,...,xn]with f(0,...,0)=g(0,...,0)=0.For two such polynomials f and g,we establish two necessary and sufcient conditions for the rational functionf g to have its limit 0 at the origin.Based on these theoretic results,we present an algorithm for deciding whether or not lim(x1,...,xn)→(0,...,0)f g=0,where f,g∈R[x1,...,xn]are two non-zero polynomials.The design of our algorithm involves two existing algorithms:one for computing the rational univariate representations of a complete chain of polynomials,another for catching strictly critical points in a real algebraic variety.The two algorithms are based on the well-known Wu’s method.With the aid of the computer algebraic system Maple,our algorithm has been made into a general program.In the final section of this paper,several examples are given to illustrate the efectiveness of our algorithm.     

A New Approach for Solving a Class of Delay Fractional Partial Differential Equations

In this article, a new numerical approach has been proposed for solving a class of delay time-fractional partial differential equations. The approximate solutions of these equations are considered as linear combinations of Müntz–Legendre polynomials with unknown coefficients. Operational matrix of fractional differentiation is provided to accelerate computations of the proposed method. Using Padé approximation and two-sided Laplace transformations, the mentioned delay fractional partial differential equations will be transformed to a sequence of fractional partial differential equations without delay. The localization process is based on the space-time collocation in some appropriate points to reduce the fractional partial differential equations into the associated system of algebraic equations which can be solved by some robust iterative solvers. Some numerical examples are also given to confirm the accuracy of the presented numerical scheme. Our results approved decisive preference of the Müntz–Legendre polynomials with respect to the Legendre polynomials.     

Decompositions of binomial ideals

We present Binomials, a package for the computer algebra system Macaulay 2, which specializes well-known algorithms to binomial ideals. These come up frequently in algebraic statistics and commutative algebra, and it is shown that significant speedup of computations like primary decomposition is possible. While central parts of the implemented algorithms go back to a paper of Eisenbud and Sturmfels, we also discuss a new algorithm for computing the minimal primes of a binomial ideal. All decompositions make significant use of combinatorial structure found in binomial ideals, and to demonstrate the power of this approach we show how Binomials was used to compute primary decompositions of commuting birth and death ideals of Evans et al., yielding a counterexample for their conjectures.     

Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra

This article concerns the computational problem of counting the lattice points inside convex polytopes, when each point must be counted with a weight associated to it. We describe an efficient algorithm for computing the highest degree coefficients of the weighted Ehrhart quasi-polynomial for a rational simple polytope in varying dimension, when the weights of the lattice points are given by a polynomial function h. Our technique is based on a refinement of an algorithm of A.?Barvinok in the unweighted case (i.e., h≡1). In contrast to Barvinok’s method, our method is local, obtains an approximation on the level of generating functions, handles the general weighted case, and provides the coefficients in closed form as step polynomials of the dilation. To demonstrate the practicality of our approach, we report on computational experiments which show that even our simple implementation can compete with state-of-the-art software.     

The Euclidean Distance Degree of an Algebraic Variety

The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. For instance, for varieties of low-rank matrices, the Eckart–Young Theorem states that this map is given by the singular value decomposition. This article develops a theory of such nearest point maps from the perspective of computational algebraic geometry. The Euclidean distance degree of a variety is the number of critical points of the squared distance to a general point outside the variety. Focusing on varieties seen in applications, we present numerous tools for exact computations.     

On spherical expansions of zonal functions on Euclidean spheres

This paper describes a new approach to the problem of computing spherical expansions of zonal functions on Euclidean spheres. We derive an explicit formula for the coefficients of the expansion expressing them in terms of the Taylor coefficients of the profile function rather than (as done usually) in terms of its integrals against Gegenbauer polynomials. Our proof of this result is based on a polynomial identity equivalent to the canonical decomposition of homogeneous polynomials and uses only basic properties of this decomposition together with simple facts concerning zonal harmonic polynomials. As corollaries, we obtain direct and apparently new derivations of the so-called plane wave expansion and of the expansion of the Poisson kernel for the unit ball. Received: 26 January 2007     

由吴方法计算零维系统的有理单元表示

本文提出一个计算零维系统的有理单元表示的新算法.无需进行Grbner基运算,我们的算法仅运用了著名的吴方法.基于吴方法,我们的算法在Maple平台上被编制成一个通用程序RUR-Wu,可快速地计算出零维系统的有理单元表示.作为一个应用,本文提出了一个有效方法,用来计算某些多项式的整体最小值.此外,本文给出了几个实例,用来表明算法的效率.     

Monodromy and irreducibility criteria with algorithmic applications in characteristic zero

Consider a projective algebraic variety V, which is the set of all common zeros of homogeneous polynomials of degrees less than d in n + 1 variables over a field of characteristic zero. We suggest an algorithm that decides whether two (or more) given points of V belong to the same irreducible component of V. We also show how to construct, for each s < n, an (s + 1)-dimensional plane in the projective space such that the intersection of every irreducible component of dimension n — s of V with the constructed plane is transversal and is an irreducible curve. These algorithms are deterministic and polynomial in dⁿ and the input size. Bibliography: 9 titles.Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 292, 2002, pp. 130–152.This revised version was published online in April 2005 with a corrected cover date and article title.     

Decomposition of algebraic sets and applications to weak centers of cubic systems

There are many methods such as Gröbner basis, characteristic set and resultant, in computing an algebraic set of a system of multivariate polynomials. The common difficulties come from the complexity of computation, singularity of the corresponding matrices and some unnecessary factors in successive computation. In this paper, we decompose algebraic sets, stratum by stratum, into a union of constructible sets with Sylvester resultants, so as to simplify the procedure of elimination. Applying this decomposition to systems of multivariate polynomials resulted from period constants of reversible cubic differential systems which possess a quadratic isochronous center, we determine the order of weak centers and discuss the bifurcation of critical periods.