Adding remote computational capabilities to Dynamic Geometry Systems

A Dynamic Geometry System (DGS) is a computer application that allows the exact drawing and dynamic manipulation of geometric constructions. DGS have been the paradigm of new technologies applied to Math education, but some authors have claimed that some symbolic capabilities should be added to this systems. We present an example of communication between the commercial DGS Cabri, The Geometer’s Sketchpad and Cinderella and two Computer Algebra Systems (CAS), Mathematica and CoCoA. The tool is a web application designed to symbolically process locus, proof and discovery tasks on geometric diagrams. Named LAD (Locus–Assertion–Discovery), it is a remote add-on for the three DGS. LAD is a prototype oriented to research users. We also describe LADucation, a one-click educational version of LAD. By just uploading the file generated by the considered DGS, graphs and equations of geometric loci are computed.     

Clifford and Graßmann Hopf algebras via the BIGEBRA package for Maple

Hopf algebraic structures will replace groups and group representations as the leading paradigm in forthcoming times. K-theory, co-homology, entanglement, statistics, representation categories, quantized or twisted structures as well as more geometric topics of invariant theory, e.g., the Graßmann-Cayley bracket algebra, are all covered by the Hopf algebraic framework. The new branch of experimental mathematics allows one to easily enter these fields through direct calculations using symbolic manipulation and computer algebra system (CAS). We discuss problems which were solved when building the BIGEBRA package for Maple and CLIFFORD to handle tensor products, Graßmann and Clifford algebras, coalgebras and Hopf algebras. Recent results showing the usefulness of CAS for investigating new and involved mathematics provide us with examples. An outlook on further developments is given.     

Computing infeasibility certificates for combinatorial problems through Hilbert’s Nullstellensatz

Systems of polynomial equations with coefficients over a field K can be used to concisely model combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over the algebraic closure of the field K. In this paper, we investigate an algorithm aimed at proving combinatorial infeasibility based on the observed low degree of Hilbert’s Nullstellensatz certificates for polynomial systems arising in combinatorics, and based on fast large-scale linear-algebra computations over K. We also describe several mathematical ideas for optimizing our algorithm, such as using alternative forms of the Nullstellensatz for computation, adding carefully constructed polynomials to our system, branching and exploiting symmetry. We report on experiments based on the problem of proving the non-3-colorability of graphs. We successfully solved graph instances with almost two thousand nodes and tens of thousands of edges.     

3D Volume Rotation Using Shear Transformations

We present a group of methods for decomposing an arbitrary 3D volume rotation into a sequence of simple shear (i.e., regular shift) operations. We explore different types of shear operations: 2Dbeam shear, a shear in one coordinate based on the other two coordinates; 2Dslice shear, a shear of a volume slice (in two coordinates) according to the third coordinate; and 2Dslice–beam shear, the combination of a beam shear and a slice shear. We show that an arbitrary 3D rotation can be decomposed into four 2D beam shears. We use this decomposition as a basis to obtain the sequence of 3D rotation decomposition into four 2D slice shears or three 2D slice–beam shears. Moreover, we observe that two consecutive slice shears can be achieved by shifting beams in 3D space, a transformation we call a 3D beam shear. Therefore, an arbitrary 3D rotation can be decomposed into only two 3D beam shears. Because of the regularity and simplicity of the shear operation, these decompositions are suitable for implementations on a multipipelined hardware or a massively parallel machine. In addition, we present a resampling scheme in which only a single-pass resampling is required for performing multiple-pass shears to achieve the 3D volume rotation.     

Study of D-decompositions by the methods of computational real-valued algebraic geometry

New methods to study the D-decomposition with the use of the computational realvalued algebraic geometry were proposed. The number of domains of D-decomposition for the polynomial parametric families of polynomials and matrices was estimated. This technique which requires construction of the Gr?bner bases and cylindrical decomposition sometimes proves to be more precise than the traditional technique. The symbolic calculation system Maple v.14 and, in particular, its package RegularChains are used.     

Application of Computer Algebra Systems for Stability Analysis of Difference Schemes on Curvilinear Grids

The paper deals with problems arising in the application of the computer algebra systems for the symbolic–numeric stability analysis of difference schemes and schemes of the finite-volume method approximating the two-dimensional Euler equations for compressible fluid flows on curvilinear spatial grids. We carry out a detailed comparison of the REDUCE 3.6 and Mathematica(Versions 2.2 and 3.0) from the point of view of their applicability to the solution of the above problems. We draw a conclusion that a preference should be given for Mathematica from the viewpoint of the execution of symbolic–numeric computations. We also describe in detail our new symbolic–numeric algorithm for stability investigation, which was implemented with the aid of Mathematica. The proposed method enables us to reduce the needed computer storage at the symbolic stages by a factor of about 20 as compared with the previous algorithms. A feature of the numerical stages is the use of the arithmetic of rational numbers, which enables us to avoid the accumulation of the roundoff errors. We present the examples of the application of the proposed symbolic–numeric method for stability analysis of very complex schemes of the finite-volume method on curvilinear grids, which are widely used in computational fluid dynamics.     

New algorithms for the Perspective-Three-Point Problem

In this paper,two approaches are used to solve the Perspective-Three-Point Problem(P3)):the symbolic computation approach and the geometric approach.In the symbolic computation approach,we use Wu-Ritt‘s zero decomposition algorithm to give a complete triangular decomposition for the P3P equation system.This decomposition provides the firest complete analytical solution to the P3P problem.In the geometric approach,we give some pure geometric criteria for the number of real physical solutions.The complete solution classification for two special cases with three and four paramters is also given.     

与历史无关的三维参数化模型构造方法

针对解析曲面构成的B-rep模型，提出了一种陈述性三维几何约束模型的构造方法．基于位置和姿态自由度解耦思想给出了几何实体的外形描述，借助空间矢量正交或平行条件定义了基本约束单元，并推导出常见工程约束的代数方程．讨论了陈述式约束模型自动构造过程，开发了三维模型变形设计原型系统，并验证该方法的可行性。     

3D object recognition using invariants of 2D projection curves

This paper presents a new method for recognizing 3D objects based on the comparison of invariants of their 2D projection curves. We show that Euclidean equivalent 3D surfaces imply affine equivalent 2D projection curves that are obtained from the projection of cross-section curves of the surfaces onto the coordinate planes. Planes used to extract cross-section curves are chosen to be orthogonal to the principal axes of the defining surfaces. Projection curves are represented using implicit polynomial equations. Affine algebraic and geometric invariants of projection curves are constructed and compared under a variety of distance measures. Results are verified by several experiments with objects from different classes and within the same class.     

三维几何约束求解的变分算法

研究了运动学变分原理在三维几何约束求解中的应用，提出了变分求解算法．该算法采用相对坐标，将求解域从笛卡儿空间转换到相对坐标空间．对于约束开环，依次选取相对坐标即可获得满足几何约束的刚体位姿；对于约束闭环，通过切断闭环铰，将约束闭环转化为等价的广义开环与切断铰约束代数方程，其切断铰约束代数方程的相对坐标雅克比矩阵解析式可通过变分关系显式获得．最后通过实例验证，说明该算法具有较高的求解效率与稳定性．     

A Symbolic-Numerical Method for Finding a Real Solution of an Arbitrary System of Nonlinear Algebraic Equations

In this paper, the author presents a new method for iteratively finding a real solution of an arbitrary system of nonlinear algebraic equations, where the system can be overdetermined or underdetermined and its Jacobian matrix can be of any (positive) rank. When the number of equations is equal to the number of variables and the Jacobian matrix of the system is nonsingular, the method is similar to the well-known Newton's method.The method is a hybrid symbolic-numerical method, in that we utilize some extended procedures from classical computer algebra together with ideas and algorithmic techniques from numerical computation, namely Newton's method and pseudoinverse matrices. First the symbolic techniques are used to transform an arbitrary system of algebraic equations into a set of regular systems. By regular system we mean a system whose Jacobian matrix is of full row rank. Newton-like numerical techniques are then used to find a real solution for each regular system obtained from the symbolic part of the method.The method has a wide range of applicability. It is especially useful for applications in which we need to find some particular solutions from a nonzero-dimensional manifold of real solutions of a system of equations, i.e. the system has infinitely many solutions.We find some mild conditions for the asymptotic convergence of the numerical part of our method. We prove that the asymptotic convergence of the new method is still quadratic while the robustness of the numerical part can be enhanced by techniques like damping as in the regular case. The method has been implemented in Maple andMathematica . Several examples are presented to show that the method works nicely.     

On the Gröbner basis triangularization of constraint equations in natural coordinates

Efficient dynamic simulation code is essential in many situations (including hardware-in-the-loop and model-predictive control applications), and highly beneficial in others (such as design optimization, sensitivity analysis, parameter identification, and controller tuning tasks). When the number of modeling coordinates n exceeds the degrees-of-freedom of the system f, as is often the case when closed kinematic chains are present, the governing dynamic equations consist of n second-order ordinary differential equations (ODEs) coupled with m=n?f algebraic constraint equations. This set of n+m index-3 differential-algebraic equations can be difficult to solve in an efficient yet accurate manner. Embedding (or generalized coordinate partitioning) can be used to obtain f ODEs (one for each independent acceleration), which are generally more amenable to numerical integration; however, the dependent positions are typically computed from the independent positions at each time step. Newton–Raphson iteration is often used for solving the position-level kinematics, but only provides solutions to within a specified tolerance, and can require several iterations to converge. In this work, Gröbner bases are used to obtain recursively solvable symbolic solutions for the dependent positions, which can then be evaluated to within machine precision using a fixed number of arithmetic operations. Natural coordinates are particularly attractive in this context, since the resulting constraint equations are maximally quadratic polynomials and are, therefore, easily triangularized. The proposed approach is suitable for use in an automated formulation procedure and, as demonstrated by three examples, is capable of generating highly efficient simulation code with minimal additional effort required at the formulation stage.     

A two-level topological model for 3D features in CityGML

CityGML, as the standard for the representation and exchange of 3D city models, contains rich information in terms of geometry, semantics, topology and appearance. With respect to topology, CityGML adopts the XLink approach to represent topological relationships between different geometric aggregates or thematic features; however, it is limited to shared objects. This paper proposes a two-level model for representing 3D topological relationships in CityGML: high-level (semantic-level) topology between semantic features and low-level (geometric-level) topology between geometric primitives. Five topological relationships are adopted in this model: touch, in, equal, overlap and disjoint. The semantic-level topology is derived from the geometric-level topology on the basis of the shared geometric primitives. To maintain the 3D topology, topological consistency rules are presented. An Application Domain Extension, called TopoADE, is proposed for the implementation of the topological model. The TopoADE consists of three modules: Topology, Feature and Geometry. Finally, 3D city models with LoD1 to LoD4 are used to test this model. Experimentation on those data sets indicates a validation of the proposed topological model in CityGML.     

Solving the recognition problem for six lines using the Dixon resultant

The “Six-line Problem” arises in computer vision and in the automated analysis of images. Given a three-dimensional (3D) object, one extracts geometric features (for example six lines) and then, via techniques from algebraic geometry and geometric invariant theory, produces a set of 3D invariants that represents that feature set. Suppose that later an object is encountered in an image (for example, a photograph taken by a camera modeled by standard perspective projection, i.e. a “pinhole” camera), and suppose further that six lines are extracted from the object appearing in the image. The problem is to decide if the object in the image is the original 3D object. To answer this question two-dimensional (2D) invariants are computed from the lines in the image. One can show that conditions for geometric consistency between the 3D object features and the 2D image features can be expressed as a set of polynomial equations in the combined set of two- and three-dimensional invariants. The object in the image is geometrically consistent with the original object if the set of equations has a solution. One well known method to attack such sets of equations is with resultants. Unfortunately, the size and complexity of this problem made it appear overwhelming until recently. This paper will describe a solution obtained using our own variant of the Cayley–Dixon–Kapur–Saxena–Yang resultant. There is reason to believe that the resultant technique we employ here may solve other complex polynomial systems.     

Three-dimensional simulation of magneto-hydrodynamic implosion of multi-wire cylindrical liners by the FLUX-3D code

A three-dimensional magneto-hydrodynamic model of conductive radiating plasma, underlying the Euler (in the cylindrical coordinates r-φ-z) program code FLUX-3D, developed at the Russian Federal Nuclear Center VNIIEF, is presented. Finite-difference methods for solving the equations of the model on a stationary regular spatial grid are described. Results of numerical 3D simulation of a multi-wire Z-pinch in conditions of the Shot-51 experiment on electrophysical facility Z (USA) in the full (2π) azimuth angle are presented. The computation geometry has been approximated to the real experimental configuration, in which the electromagnetic energy was supplied to the chamber by a vacuum coaxial transmission line. In the numerical simulation, the dynamics of the acceleration of plasma ablated from tungsten wires as a function of the number of wires in the initial cylindrical assembly was studied. In addition, results of 3D calculations of the current implosion of multi-wire Z-pinch for two kinds of artificial perturbations on the plasma ablation intensity are presented. The reasons of the difference in the soft X-ray radiation pulses generated in these cases are discussed.     

遗传算法在三维网格模型数字水印中的应用

在数字水印的研究中,为保护版权信息特性,提高精确性和抗噪能力,提出了一种遗传算法的三维网格模型变换域盲水印算法。先将三维模型转化为二维数值矩阵,然后进行二维分块DCT变换生成系数矩阵,利用遗传算法寻找满足适应度函数的最佳嵌入系数,适应度函数使嵌入水印后的模型变形最小。并要嵌入矩阵的位置信息及相应的DCT系数,进行仿真。结果表明,算法可抵抗平移、旋转、各向一致缩放攻击、顶点重排序攻击、噪声攻击。证明对简化方法具有一定的鲁棒性,为设计提供参考。