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.     

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.     

Blending implicit interval curves and surfaces

This paper is concerned with blending algebraic implicit curve and surface representation where the functional representations have inaccuracies. Algebraic implicit interval curves and surfaces are first defined as interval algebraic objects. The interval Buchberger algorithm, relying on polynomial interval division, is then outlined. General blending problems for algebraic implicit curves and surfaces are considered and various continuity conditions are applied. Computational cases are developed for specific problems.     

A general Hungarian method for the algebraic transportation problem

In this paper the algebraic transportation problem is introduced which covers besides the Hitchcock and the time transportation problem several other types of transportation problems of practical relevance. To solve this algebraic transportation problem admissible transformations are considered and characterized. Thereupon a transformation algorithm is described which is a generalization of the Hungarian method for the classical transportation problem as well as of a threshold method for time transportation problems.     

连续代数扩域上多项式因式分解的Trager算法

多项式的因式分解是符号计算中最基本的算法,二十世纪六十年代开始出现的关于多项式因式分解的工作被认为是符号计算领域的起源．目前多项式的因式分解已经成熟,并已在Maple等符号计算软件中实现,但代数扩域上的因式分解算法还有待进一步改进．代数扩域上的基本算法是Trager算法．Weinberger等提出了基于Hensel提升的算法．这些算法是在单个扩域上做因式分解．而在吴零点分解定理中,多个代数扩域上的因式分解是非常基本的一步,主要用于不可约升列的计算．为了解决这一问题,吴文俊,胡森、王东明分别提出了基于方程求解的多个扩域上的因式分解算法．王东明、林东岱提出了另外一个算法Trager算法相似,将问题化为有理数域上的分解．他们应用了吴的三角化算法,因此算法的终止性依赖于吴方法的计算．支丽红则将提升技巧用于多个扩域上的因式分解算法．本文将Trager的算法直接推广为连续扩域上的因式分解,只涉及结式计算与有理数域上的因式分解,给出了多个代数扩域上的因式分解一个直接的算法．     

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.     

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.     

实分片代数曲线的某些研究

分片代数曲线作为二元样条函数的零点集合是经典代数曲线的推广. 利用代数的基本知识, 本文对实分片代数曲线的基本性质进行了初步讨论, 并且将实分片代数曲线与相应的二元样条分类进行讨论. 最后, 对实分片代数曲线上的孤立点进行了研究.     

Numerical computation of the genus of an irreducible curve within an algebraic set

The common zero locus of a set of multivariate polynomials (with complex coefficients) determines an algebraic set. Any algebraic set can be decomposed into a union of irreducible components. Given a one-dimensional irreducible component, i.e. a curve, it is useful to understand its invariants. The most important invariants of a curve are the degree, the arithmetic genus and the geometric genus (where the geometric genus denotes the genus of a desingularization of the projective closure of the curve). This article presents a numerical algorithm to compute the geometric genus of any one-dimensional irreducible component of an algebraic set.     

Accurate Numerical Determination of the Intersection Point of the Solution of a Differential Equation with a Given Algebraic Relation

In this paper, the authors present an adaptation of the simplerational extrapolation scheme (Bulirsch & Stoer, 1966) tofind the point of intersection of the solution curve of an ordinarydifferential equation with a given curve or algebraic relationship.This point could also possibly be a point of discontinuity ofthe derivative. The integration algorithm is illustrated witha simple example.     

Computation of the best Diophantine approximations and of fundamental units of algebraic fields

A global generalization of continued fraction that yields the best Diophantine approximations of any dimension is considered. In the algebraic case, this generalization underlies a method for calculating the fundamental units of algebraic rings and the periods of best approximations, as well as the identification of the fundamental domain with respect to these periods. The units of an algebraic field are understood as the units of maximal order of this field.     

Estimation of the Bezout number for piecewise algebraic curve

A piecewise algebraic curve is a curve determined by the zero set of a bivariate spline function.In this paper.a coniecture on trianguation is confirmed The relation between the piecewise linear algebraiccurve and four-color conjecture is also presented.By Morgan-Scott triangulation, we will show the instabilityof Bezout number of piecewise algebraic curves. By using the combinatorial optimization method,an upper     

Charpit System of Partial Differential Equations with Algebraic Constraints

In this paper the Charpit system of partial differential equations with algebraic constraints is considered. So, first the compatibility conditions of a system of algebraic equations and also of the Charpit system of partial differential equations are separately considered. For the combined system of equations of both types sufficient conditions for the existence of a solution are found. They lead to an algorithm for reducing the combined system to a Charpit system of partial differential equations of dimension less than the initial system and without algebraic constraints. Moreover, it is proved that this system identically satisfies the compatibility conditions if so does the initial system.     

Topology of real algebraic curves

The problem on the existence of an additional first integral of the equations of geodesics on noncompact algebraic surfaces is considered. This problem was discussed as early as by Riemann and Darboux. We indicate coarse obstructions to integrability, which are related to the topology of the real algebraic curve obtained as the line of intersection of such a surface with a sphere of large radius. Some yet unsolved problems are discussed.     

Symmetric Orientations of Dividing T-curves

In 1974, Rokhlim introduced complex orientations for nonsingular real algebraic plane projective curves of type I. Here we give a definition of symmetric orientations and of "type" for T-curves which are PL-curves constructed using a combinatorial method called T-construction. An important aspect of T-construction is that, under particular conditions, the constructed T-curve has the isotopy type of a nonsingular real algebraic plane projective curve. T-construction is in fact a particular case of the method of construction of real algebraic projective varieties due to O. Ya. Viro. We prove that if an algebraic curve is associated to a T-curve by the Viro process, then the type of the T-curve coincides with the type of the algebraic curve and its symmetric orientations are complex orientations as defined by Rokhlin. The main result of this paper is the classification theorem for T-curves of type I.     

The Bezout Number for Piecewise Algebraic Curves

The computation of the Bezout number, the maximum number of intersection points between two piecewise algebraic curves whose common points are finite, is considered. A piecewise algebraic curve is a curve determined by a bivariate spline function. It is found that the maximum number of intersections depends not only on the degrees and the differentiability of the spline functions, but also on the structure of the partition on which the spline functions are defined.     

Nöther-type theorem of piecewise algebraic curves on triangulation

The piecewise algebraic curve is a kind generalization of the classical algebraic curve. Nöther-type theorem of piecewise algebraic curves on the cross-cut partition is very important to construct the Lagrange interpolation sets for a bivariate spline space. In this paper, using the properties of bivariate splines, the Nöther-type theorem of piecewise algebraic curves on the arbitrary triangulation is presented.     

The Nother and Riemann-Roch type theorems for piecewise algebraic curve

A piecewise algebraic curve is a curve determined by the zero set of a bivariate spline function. In this paper, the Nother type theorems for Cμpiecewise algebraic curves are obtained. The theory of the linear series of sets of places on the piecewise algebraic curve is also established. In this theory, singular cycles are put into the linear series, and a complete series of the piecewise algebraic curves consists of all effective ordinary cycles in an equivalence class and all effective singular cycles which are equivalent specifically to any effective ordinary cycle in the equivalence class. This theory is a generalization of that of linear series of the algebraic curve. With this theory and the fundamental theory of multivariate splines on smoothing cofactors and global conformality conditions, and the results on the general expression of multivariate splines, we get a formula on the index, the order and the dimension of a complete series of the irreducible Cμpiecewise algebraic curves and the degree, the genus and the smoothness of the curves, hence the Riemann-Roch type theorem of the Cμpiecewise algebraic curve is established.     

Numerical continuation of solution at a singular point of high codimension for systems of nonlinear algebraic or transcendental equations

Numerical continuation of solution through certain singular points of the curve of the set of solutions to a system of nonlinear algebraic or transcendental equations with a parameter is considered. Bifurcation points of codimension two and three are investigated. Algorithms and computer programs are developed that implement the procedure of discrete parametric continuation of the solution and find all branches at simple bifurcation points of codimension two and three. Corresponding theorems are proved, and each algorithm is rigorously justified. A novel algorithm for the estimation of errors of tangential vectors at simple bifurcation points of a finite codimension m is proposed. The operation of the computer programs is demonstrated by test examples, which allows one to estimate their efficiency and confirm the theoretical results.     

N(o)ther-type theorem of piecewise algebraic curves on triangulation

The piecewise algebraic curve is a kind generalization of the classical algebraic curve.N(o)ther-type theorem of piecewise algebraic curves on the cross-cut partition is very important to construct the Lagrange interpolation sets for a bivariate spline space. In this paper, using the properties of bivariate splines, the N(o)ther-type theorem of piecewise algebraic curves on the arbitrary triangulation is presented.