Efficient Algorithms for the Riemann-Roch Problem and for Addition in the Jacobian of a Curve

We study the effective Riemann-Roch problem of computing a basis for the linear space L(D) associated with a divisor D on a plane curve C and its applications. Our presentation begins with an extension of Noether's algorithm for this problem to plane curves with singularities. Like the original, this algorithm has a worst-case complexity of Ω(n!^|D|), where n is the degree of the curve C.We next consider representations of divisors based on Chow forms. Using these, we produce a factorization-free polynomial-time algorithm for the effective Riemann-Roch problem, which improves the complexity of Noether's algorithm by an order of magnitude. We also present further improvements which, for curves of bounded degree, yield an algorithm with complexity which is linear in the size of the given divisor. Finally, we consider applications of this problem: to the arithmetic of the Jacobian of a plane curve, to the construction of rational functions on a curve with prescribed zeroes and poles, and to the construction of curves with prescribed intersections.     

On partitions of functions on finite sets

Let D and R be finite sets with cardinality n and m respectivelyR ^D be the set of all functions from D into R, and G and H be permutation groups acting on D and R respectively. Two functions f and g in R ^D are said to be related if there exists a σ in G and a τ in H with f(σd) = τg(d) for every d in D. Since the relation is an equivalence relation, R ^D is partitioned into disjoint classes. Roughly, by using the cycle indices of G and H, de Bruijn's theorem determines the number of equivalence classes, and Pólya's theorem, with H being the identity group, gives the function counting series, Pólya-de Bruijn's theorem has many applications (for instance, see Pólya and Read [6]). The theorem and its applications, basically, centered around the partitions of functions. Here, we present an algorithm to determine which functions in R ^D belong to the same equivalent class. Our algorithm does not use the cycle indices of G and H (to compute the cycle index of a given group, in general, is difficult), but it uses the generators of G and H, and the m-nary numbers to code the functions in R ^D . Our algorithm also gives the function counting series and the number of equivalence classes. An important application is that for each positive integer n, we use our algorithm and the symmetric group S _n to determine all isomorphic and nonisomorphic graphs and directed graphs with n vertices.     

Computing medial axes of generic 3D regions bounded by B-spline surfaces

A new approach is presented for computing the interior medial axes of generic regions in R³ bounded by C⁽⁴⁾-smooth parametric B-spline surfaces. The generic structure of the 3D medial axis is a set of smooth surfaces along with a singular set consisting of edge curves, branch curves, fin points and six junction points. In this work, the medial axis singular set is first computed directly from the B-spline representation using a collection of robust higher order techniques. Medial axis surfaces are computed as a time trace of the evolving self-intersection set of the boundary under the the eikonal (grassfire) flow, where the bounding surfaces are dynamically offset along the inward normal direction. The eikonal flow results in special transition points that create, modify or annihilate evolving curve fronts of the (self-) intersection set. The transition points are explicitly identified using the B-spline representation. Evolution of the (self-) intersection set is computed by adapting a method for tracking intersection curves of two different surfaces deforming over generalized offset vector fields. The proposed algorithm accurately computes connected surfaces of the medial axis as well its singular set. This presents a complete solution along with accurate topological structure.     

Constrained circles packing test problems: all the optimal solutions known

Taking a satellite module layout design as engineering background, this paper gives constrained test problems for an unequal circle packing whose optimal solutions are all given. Given a circular container D with radius R, the test problem can be constructed in the following steps. First, M=217 circles are packed into D without overlaps by ‘packing with a tangent circle’ to get the values of radii and centroid coordinates of the circles, which are expressed by R. Then the 217 circles are arranged in descending sequence of radius and are divided into 23 groups according to the radius. Finally, seven test problems are constructed according to the circles of q=1, 2, …, 7 groups. The optimal solution to the test problems as well as its optimality and uniqueness proof are also presented. The experimental results show that the test problems can effectively evaluate performances of different evolutionary algorithms.     

Möbius变换下四次有理抛物-PH曲线的C2 Hermite插值

目的 曲线插值问题在机器人设计、机械工业、航天工业等诸多现代工业领域都有广泛的应用，而已知端点数据的Hermite插值是计算机辅助几何设计中一种常用的曲线构造方法，本文讨论了一种偶数次有理等距曲线，即四次抛物-PH曲线的C² Hermite插值问题。方法 基于M bius变换引入参数，利用复分析的方法构造了四次有理抛物-PH曲线的C² Hermite插值，给出了具体插值算法及相应的Bézier曲线表示和控制顶点的表达式。结果 通过给出"合理"的端点插值数据，以数值实例表明了该算法的有效性，所得12条插值曲线中，结合最小绝对旋转数和弹性弯曲能量最小化两种准则给出了判定满足插值条件最优曲线的选择方法，并以具体实例说明了与其他插值方法的对比分析结果。结论 本文构造了M bius变换下的四次有理抛物-PH曲线的C² Hermite插值，在保证曲线次数较低的情况下，达到了连续性更高的插值条件，计算更为简单，插值效果明显，较之传统奇数次PH曲线具有更加自然的几何形状，对偶数次PH曲线的相关研究具有一定意义。     

Subdivision methods for solving polynomial equations

This paper presents a new algorithm for solving a system of polynomials, in a domain of Rⁿ${\mathbb{R}}^n$. It can be seen as an improvement of the Interval Projected Polyhedron algorithm proposed by Sherbrooke and Patrikalakis [Sherbrooke, E.C., Patrikalakis, N.M., 1993. Computation of the solutions of nonlinear polynomial systems. Comput. Aided Geom. Design 10 (5), 379–405]. It uses a powerful reduction strategy based on univariate root finder using Bernstein basis representation and Descarte’s rule  . We analyse the behavior of the method, from a theoretical point of view, shows that for simple roots, it has a local quadratic convergence speed and gives new bounds for the complexity of approximating real roots in a box of Rⁿ${\mathbb{R}}^n$. The improvement of our approach, compared with classical subdivision methods, is illustrated on geometric modeling applications such as computing intersection points of implicit curves, self-intersection points of rational curves, and on the classical parallel robot benchmark problem.     

The solution of multi-parameter systems of equations with application to problems in nonlinear elasticity

Systems of nonlinear equations governed by more than one parameter are discussed with particular attention to bifurcation behaviour. The procedure adopted is to add to the original system of n equations (m − 1) further equations, in the case of m parameters, and to seek solution curves in R^n+m to this augmented system. Two types of additional equations are considered: one describes a piecewise linear path in the space of parameters, and the second constrains the solution curve to be a locus of singular points. These ideas are all subsequently applied to the systems of equations arising from finite element approximations of boundary value problems in nonlinear elasticity. The behaviour of a nonlinear elastic thick-walled cylinder subjected to internal pressure and axial extension is discussed.     

Diagonal polynomials and diagonal orders on multidimensional lattices

HereR andN denote the real numbers and the nonnegative integers, respectively. Alsos(x)=x ₁+···+x _n whenx=(x ₁, …,x _n) inR ⁿ. A mapf:R ⁿ →R is call adiagonal function of dimensionn iff|N ⁿ is a bijection ontoN and, for allx, y inN ⁿ, f(x)<f(y) whens(x)<s(y). Morales and Lew [6] constructed 2 ⁿ⁻² inequivalent diagonal polynomial functions of dimensionn for eachn>1. Here we use new combinatorial ideas to show that numberd _n of such functions is much greater than 2 ⁿ⁻² forn>3. These combinatorial ideas also give an inductive procedure to constructd _n+1 diagonal orderings of {1, …,n}.     

Positively invariant sets of discrete-time systems with constrained inputs

Linear discrete-time dynamical systems x_k + _I = Ax_k + _k with constrained inputs c_k ∈ ω, for which the matrix A possesses the property of leaving a proper cone AK + positively invariant, i.e. AK + ? K + . Necessary and sufficient conditions guarantee that a non-empty set 𝒟(K; a, b) ? Rⁿ, obtained from the intersection of translated proper cones, is positively invariant for motions of the system. Both the homogeneous and inhomogeous cases are considered. In the latter case, the external behaviour of motions, i.e. for trajectories originating from x₀ ? Rⁿ/𝒟(K; a, b) (respectively,x_o ? Rⁿ) is studied in terms of attractive and contractivity of the set 𝒟(K; a, b). The global attractivity conditions of 𝒟(K; a, b) are also given. It is shown how the results presented can be used to solve the saturated state feedback regulator problem.     

Error Analysis for hp-FEM Semi-Lagrangian Second Order BDF Method for Convection-Dominated Diffusion Problems

We present in this paper an analysis of a semi-Lagrangian second order Backward Difference Formula combined with hp-finite element method to calculate the numerical solution of convection diffusion equations in ℝ². Using mesh dependent norms, we prove that the a priori error estimate has two components: one corresponds to the approximation of the exact solution along the characteristic curves, which is O(Dt²+h^m+1(1+\frac\mathopen|logh|Dt))O(\Delta t^{2}+h^{m+1}(1+\frac{\mathopen{|}\log h|}{\Delta t})); and the second, which is O(Dt^p+|| [(u)\vec]-[(u)\vec]_h||_L^￥)O(\Delta t^{p}+\| \vec{u}-\vec{u}_{h}\|_{L^{\infty}}), represents the error committed in the calculation of the characteristic curves. Here, m is the degree of the polynomials in the finite element space, [(u)\vec]\vec{u} is the velocity vector, [(u)\vec]_h\vec{u}_{h} is the finite element approximation of [(u)\vec]\vec{u} and p denotes the order of the method employed to calculate the characteristics curves. Numerical examples support the validity of our estimates.     

Equivalence of distinct characterizations for rational rotation-minimizing frames on quintic space curves

A rotation-minimizing frame on a space curve r(t) is an orthonormal basis (f₁,f₂,f₃) for R³, where f₁=r^′/|r^′| is the curve tangent, and the normal-plane vectors f₂,f₃ exhibit no instantaneous rotation about f₁. Such frames are useful in spatial path planning, swept surface design, computer animation, robotics, and related applications. The simplest curves that have rational rotation-minimizing frames (RRMF curves) comprise a subset of the quintic Pythagorean-hodograph (PH) curves, and two quite different characterizations of them are currently known: (a) through constraints on the PH curve coefficients; and (b) through a certain polynomial divisibility condition. Although (a) is better suited to the formulation of constructive algorithms, (b) has the advantage of remaining valid for curves of any degree. A proof of the equivalence of these two different criteria is presented for PH quintics, together with comments on the generalization to higher-order curves. Although (a) and (b) are both sufficient and necessary criteria for a PH quintic to be an RRMF curve, the (non-obvious) proof presented here helps to clarify the subtle relationships between them.     

On Bounding Solutions of Underdetermined Systems

Sufficient conditions for the existence and uniqueness of a solution x* D (R ⁿ ) of Y(x) = 0 where : R ⁿ R ^m (m n) with C ²(D) where D R ⁿ is an open convex set and Y = (x)⁺ are given, and are compared with similar results due to Zhang, Li and Shen (Reliable Computing 5(1) (1999)). An algorithm for bounding zeros of f (·) is described, and numerical results for several examples are given.     

Theoretically-based algorithms for robustly tracking intersection curves of deforming surfaces

This paper applies singularity theory of mappings of surfaces to 3-space and the generic transitions occurring in their deformations to develop algorithms for continuously and robustly tracking the intersection curves of two deforming parametric spline surfaces, when the deformation is represented as a family of generalized offset surfaces. The set of intersection curves of two deforming surfaces over all time is formulated as an implicit 2-manifold I in an augmented (by time domain) parametric space R⁵. Hyperplanes corresponding to some fixed time instants may touchI at some isolated transition points, which delineate transition events, i.e. the topological changes to the intersection curves. These transition points are the 0-dimensional solution to a rational system of five constraints in five variables, and can be computed efficiently and robustly with a rational constraint solver using subdivision and hyper-tangent bounding cones. The actual transition events are computed by contouring the local osculating paraboloids. Away from any transition points, the intersection curves do not change topology and evolve according to a simple evolution vector field that is constructed in the Euclidean space in which the surfaces are embedded.     

μ-Bases and singularities of rational planar curves

We provide a technique to detect the singularities of rational planar curves and to compute the correct order of each singularity including the infinitely near singularities without resorting to blow ups. Our approach employs the given parametrization of the curve and uses a μ-basis for the parametrization to construct two planar algebraic curves whose intersection points correspond to the parameters of the singularities including infinitely near singularities with proper multiplicity. This approach extends Abhyankar's method of t-resultants from planar polynomial curves to rational planar curves. We also derive the classical result that for a rational planar curve of degree n the sum of all the singularities with proper multiplicity is (n−1)(n−2)/2. Examples are provided to flesh out our results.     

Ellipse-based principal component analysis for self-intersecting curve reconstruction from noisy point sets

Surface reconstruction from cross cuts usually requires curve reconstruction from planar noisy point samples. The output curves must form a possibly disconnected 1-manifold for the surface reconstruction to proceed. This article describes an implemented algorithm for the reconstruction of planar curves (1-manifolds) out of noisy point samples of a self-intersecting or nearly self-intersecting planar curve C. C:[a,b]⊂R→R ² is self-intersecting if C(u)=C(v), u≠v, u,v∈(a,b) (C(u) is the self-intersection point). We consider only transversal self-intersections, i.e. those for which the tangents of the intersecting branches at the intersection point do not coincide (C′(u)≠C′(v)). In the presence of noise, curves which self-intersect cannot be distinguished from curves which nearly self-intersect. Existing algorithms for curve reconstruction out of either noisy point samples or pixel data, do not produce a (possibly disconnected) Piecewise Linear 1-manifold approaching the whole point sample. The algorithm implemented in this work uses Principal Component Analysis (PCA) with elliptic support regions near the self-intersections. The algorithm was successful in recovering contours out of noisy slice samples of a surface, for the Hand, Pelvis and Skull data sets. As a test for the correctness of the obtained curves in the slice levels, they were input into an algorithm of surface reconstruction, leading to a reconstructed surface which reproduces the topological and geometrical properties of the original object. The algorithm robustly reacts not only to statistical non-correlation at the self-intersections (non-manifold neighborhoods) but also to occasional high noise at the non-self-intersecting (1-manifold) neighborhoods.     

Cosmological dynamics in sixth-order gravity

We consider the cosmological dynamics in a generalized modified theory of gravity with an R□R term added to the action of the form R + R ^N . The influence of the R□R term on the known solutions of modified gravity is described. We show that in the particular case of N = 3 the two non-Einsteinian terms are equally important in power-law solutions. These solutions and their stability have been studied using the dynamical system approach. Some results for the case of N ≠ 3 (including stability of the de Sitter solution in the theory under investigation) have been obtained using other methods.     

Time-varying continuous nonlinear systems: uniform asymptotic stability

The framework of the presented research is a large class of time-varying nonlinear systems with continuous motions. The study of the uniform asymptotic stability of the zero equilibrium state developed here goes back to, and relies on, the very foundations of the Lyapunov stability concept and the (second) Lyapunov method. Stability domains are first defined and examined. Then, their qualitative features are used to establish complete solutions to the problem of uniform asymptotic stability of the equilibrium for various subclasses of the systems. The solutions present conditions that are both necessary and sufficient for: (1) the uniform asymptotic stability, (2) an exact direct one-shot construction of a system Lyapunov function and (3) for a direct accurate one-shot determination of the asymptotic stability domain. In addition, the solutions establish a novel Lyapunov-method based approach to the asymptotic stability analysis. This enables an arbitrary selection of a function p(·) from a defined functional family to determine a Lyapunov function (·), [(·)], by solving D ⁺(·) = ? p(·) or, equivalently, D ⁺ (·) = ? p(·)[1 ? (·)], respectively. Illustrative examples are presented.     

Efficient randomized generation of optimal algorithms for multiplication in certain finite fields

LetN _max(q) denote the maximum number of points of an elliptic curve over F _q . Given a prime powerq=p ^f and an integern satisfying 1/2q+1<n(N _max(q)–2)/2, we present an algorithm which on inputq andn produces an optimal bilinear algorithm of length 2n for multiplication in F _q ⁿ /F _q . The algorithm takes roughlyO(q ⁴+n ⁴logq) F _q -operations or equivalentlyO((q ⁴+n ⁴logq)f ²log² p) bit-operations to compute the output data.     

An alternative solution to the H∞-optimal control problem

In this paper we present an alternative solution to the problem min _{X ε H^n×n∞} |A + BXC|_∞ where A, B, rmand C are rational matrices in H^n×n_∞. The solution circumvents the need to extract the matrix inner factors of B and C, providing a multivariable extension of Sarason's H^∞-interpolation theory [1] to the case of matrix-valued B(s) and C(s). The result has application to the diagonally-scaled optimization problem int |D(A + BXC)D⁻¹|_∞, where the infimum is over D, X εH^n×n_∞, D diagonal.     

Maintaining dynamic sequences under equality tests in polylogarithmic time

We present a randomized and a deterministic data structure for maintaining a dynamic family of sequences under equality tests of pairs of sequences and creations of new sequences by joining or splitting existing sequences. Both data structures support equality tests inO(1) time. The randomized version supports new sequence creations inO(log² n) expected time wheren is the length of the sequence created. The deterministic solution supports sequence creations inO(logn(logmlog^* m+logn)) time for themth operation. This work was supported by the ESPRIT Basic Research Actions Program, under Contract No. 7141 (Project ALCOM II).