Computer Algebra in Scientific Computing

Frontmatter

Linear Differential Systems with Infinite Power Series Coefficients (Invited Talk)

Abstract

Infinite power series may appear as inputs for certain mathematical problems. This paper examines two possible solutions to the problem of representation of infinite power series: the algorithmic representation (for each series, an algorithm is specified that, given an integer i, finds the coefficient of \(x^i\), — any such algorithm defines a so called computable, or constructive, series) and a representation in an approximate form, namely, in a truncated form.

S. A. Abramov

On the Asymptotic Stability of a Satellite with a Gravitational Stabilizer

Abstract

The problem of the influence of the structure of forces on the stability of the relative equilibrium of a controlled satellite with a gravitational stabilizer on the circular orbit is studied. In the space of entered parameters, the regions with different degrees of instability by Poincaré are found. Assuming an instability of a potential system, the problem of the possibility of its stabilization up to asymptotic stability is considered. A parametric analysis of the obtained inequalities with the help of “Mathematica” built-in tools for symbolic-numerical modelling is carried out.

Andrei V. Banshchikov

Sparse Interpolation, the FFT Algorithm and FIR Filters

Abstract

In signal processing, the Fourier transform is a popular method to analyze the frequency content of a signal, as it decomposes the signal into a linear combination of complex exponentials with integer frequencies. A fast algorithm to compute the Fourier transform is based on a binary divide and conquer strategy.

In computer algebra, sparse interpolation is well-known and closely related to Prony’s method of exponential fitting, which dates back to 1795. In this paper we develop a divide and conquer algorithm for sparse interpolation and show how it is a generalization of the FFT algorithm.

In addition, when considering an analog as opposed to a discrete version of our divide and conquer algorithm, we can establish a connection with digital filter theory.

Matteo Briani, Annie Cuyt, Wen-shin Lee

On New Integrals of the Algaba-Gamero-Garcia System

Abstract

We study local integrability of a plane autonomous polynomial system of ODEs depending on five parameters with a degenerate singular point at the origin. The approach is based on making use of the Power Geometry Method and the computation of normal forms. We look for the complete set of necessary conditions on parameters of the system under which the system is locally integrable near the degenerate stationary point. We found earlier that the sets of parameters satisfying these conditions consist of four two-parameter subsets in the full five-parameter co-space. Now we consider the special subcase of the case \(b^2 = 2/3\) and separate subsubcases when additional first integrals can exist. Here we have found two such integrals.

Alexander D. Bruno, Victor F. Edneral, Valery G. Romanovski

Full Rank Representation of Real Algebraic Sets and Applications

Abstract

We introduce the notion of the full rank representation of a real algebraic set, which represents it as the projection of a union of real algebraic manifolds \(V_{\mathbb {R}}(F_i)\) of \(\mathbb {R}^m\), \(m\ge n\), such that the rank of the Jacobian matrix of each \(F_i\) at any point of \(V_{\mathbb {R}}(F_i)\) is the same as the number of polynomials in \(F_i\).

By introducing an auxiliary variable, we show that a squarefree regular chain T can be transformed to a new regular chain C having various nice properties, such as the Jacobian matrix of C attains full rank at any point of \(V_{\mathbb {R}}(C)\). Based on a symbolic triangular decomposition approach and a numerical critical point technique, we present a hybrid algorithm to compute a full rank representation.

As an application, we show that such a representation allows to better visualize plane and space curves with singularities. Effectiveness of this approach is also demonstrated by computing witness points of polynomial systems having rank-deficient Jacobian matrices.

Changbo Chen, Wenyuan Wu, Yong Feng

Certifying Simple Zeros of Over-Determined Polynomial Systems

Abstract

We construct a real square system related to a given over-determined real system. We prove that the simple real zeros of the over-determined system are the simple real zeros of the related square system and the real zeros of the two systems are one-to-one correspondence with the constraint that the value of the sum of squares of the polynomials in the over-determined system at the real zeros is identically zero. After certifying the simple real zeros of the related square system with the interval methods, we assert that the certified zero is a local minimum of the sum of squares of the input polynomials. If the value of the sum of the squares of the input polynomials at the certified zero is equal to zero, then it is a zero of the input system. Notice that a complex system with complex zeros can be transformed into a real system with real zeros.

Jin-San Cheng, Xiaojie Dou

Decomposing Polynomial Sets Simultaneously into Gröbner Bases and Normal Triangular Sets

Abstract

In this paper we focus on the algorithms and their implementations for decomposing an arbitrary polynomial set simultaneously into pairs of lexicographic Gröbner bases and normal triangular sets with inherent connections in between and associated zero relationship with the polynomial set. In particular, a method by temporarily changing the variable orderings to handle the failure of the variable ordering assumption is proposed to ensure splitting needed for characteristic decomposition. Experimental results of our implementations for (strong) characteristic decomposition with comparisons with available implementations of triangular decomposition are also reported.

Rina Dong, Chenqi Mou

Open Access

Symbolic Versus Numerical Computation and Visualization of Parameter Regions for Multistationarity of Biological Networks

Abstract

We investigate models of the mitogenactivated protein kinases (MAPK) network, with the aim of determining where in parameter space there exist multiple positive steady states. We build on recent progress which combines various symbolic computation methods for mixed systems of equalities and inequalities. We demonstrate that those techniques benefit tremendously from a newly implemented graph theoretical symbolic preprocessing method. We compare computation times and quality of results of numerical continuation methods with our symbolic approach before and after the application of our preprocessing.

Matthew England, Hassan Errami, Dima Grigoriev, Ovidiu Radulescu, Thomas Sturm, Andreas Weber

PDF Zum Volltext

The Polymake Interface in Singular and Its Applications

Abstract

Singular and polymake are computer algebra systems for research in algebraic geometry and polyhedral geometry respectively. We illustrate the implementation and the functionality of the polymake-interface in Singular and exhibit its application to the arithmetic of polyhedral divisors and the reconstruction of hypersurface singularities from the Milnor algebra.

Raul Epure, Yue Ren, Hans Schönemann

Computation of Some Integer Sequences in Maple

Abstract

We consider some integer sequences connected with combinatorial applications. Specifically, we consider Stirling partition and cycle numbers, associated Stirling partition and cycle numbers, and Eulerian numbers of the first and second kinds. We consider their evaluation in different contexts. One context is the calculation of a single value based on single input arguments. A more common context, however, is the calculation of a sequence of values. We compare strategies for both. Where possible, we compare with existing Maple implementations.

W. L. Fan, D. J. Jeffrey, Erik Postma

Symbolic-Numerical Algorithm for Generating Interpolation Multivariate Hermite Polynomials of High-Accuracy Finite Element Method

Abstract

A symbolic-numerical algorithm implemented in Maple for constructing Hermitian finite elements is presented. The basis functions of finite elements are high-order polynomials, determined from a specially constructed set of values of the polynomials themselves, their partial derivatives, and their derivatives along the directions of the normals to the boundaries of finite elements. Such a choice of the polynomials allows us to construct a piecewise polynomial basis continuous across the boundaries of elements together with the derivatives up to a given order, which is used to solve elliptic boundary value problems using the high-accuracy finite element method. The efficiency and the accuracy order of the finite element scheme, algorithm and program are demonstrated by the example of the exactly solvable boundary-value problem for a triangular membrane, depending on the number of finite elements of the partition of the domain and the number of piecewise polynomial basis functions.

A. A. Gusev, V. P. Gerdt, O. Chuluunbaatar, G. Chuluunbaatar, S. I. Vinitsky, V. L. Derbov, A. Góźdź

Symbolic-Numerical Algorithms for Solving the Parametric Self-adjoint 2D Elliptic Boundary-Value Problem Using High-Accuracy Finite Element Method

Abstract

We propose new symbolic-numerical algorithms implemented in Maple-Fortran environment for solving the parametric self-adjoint elliptic boundary-value problem (BVP) in a 2D finite domain, using high-accuracy finite element method (FEM) with triangular elements and high-order fully symmetric Gaussian quadratures with positive weights, and no points are outside the triangle (PI type). The algorithms and the programs calculate with the given accuracy the eigenvalues, the surface eigenfunctions and their first derivatives with respect to the parameter of the BVP for parametric self-adjoint elliptic differential equation with the Dirichlet and/or Neumann type boundary conditions on the 2D finite domain, and the potential matrix elements, expressed as integrals of the products of surface eigenfunctions and/or their first derivatives with respect to the parameter. We demonstrated an efficiency of algorithms and program by benchmark calculations of helium atom ground state.

A. A. Gusev, V. P. Gerdt, O. Chuluunbaatar, G. Chuluunbaatar, S. I. Vinitsky, V. L. Derbov, A. Góźdź

A Symbolic Study of the Satellite Dynamics Subject to Damping Torques

Abstract

The dynamics of the rotational motion of a satellite moving in the central Newtonian force field in a circular orbit under the influence of gravitational and active damping torques is investigated with the help of computer algebra methods. The properties of a nonlinear algebraic system that determines equilibrium orientations of a satellite under the action of gravitational and active damping torques were studied. An algorithm for the construction of a Gröbner basis is proposed for determining the equilibrium orientations of a satellite with given central moments of inertia and given damping torques. The conditions of the equilibria’s existence were obtained by the analysis of real roots of algebraic equations from the constructed Gröbner basis. The domains with an equal number of equilibria were specified by using algebraic methods for the construction of discriminant hypersurfaces. The conditions of asymptotic stability of the satellite’s equilibria were determined as a result of the analysis of linearized equations of motion using Routh–Hurwitz criterion.

Sergey A. Gutnik, Vasily A. Sarychev

Characteristic Set Method for Laurent Differential Polynomial Systems

Abstract

In this paper, a characteristic set method for Laurent (differential) polynomial systems is given. In the Laurent polynomial case, the concept of Laurent regular chain is introduced and a characteristic set algorithm for Laurent polynomial system is given. In the Laurent differential polynomial case, we give a partial method to decide whether a Laurent differential chain \({\mathscr {A}}\) is Laurent regular.

Youren Hu, Xiao-Shan Gao

Sparse Polynomial Interpolation with Finitely Many Values for the Coefficients

Abstract

In this paper, we give new sparse interpolation algorithms for black box polynomial f whose coefficients are from a finite set. In the univariate case, we recover f from one evaluation \(f(\beta )\) for a sufficiently large number \(\beta \). In the multivariate case, we introduce the modified Kronecker substitution to reduce the interpolation of a multivariate polynomial to that of the univariate case. Both algorithms have polynomial bit-size complexity.

Qiao-Long Huang, Xiao-Shan Gao

On Stationary Motions of the Generalized Kowalewski Gyrostat and Their Stability

Abstract

The stationary motions of the Kowalewski gyrostat in two constant force fields are studied. It is revealed that the equations of motion of the gyrostat have the families of permanent rotations when the force fields are parallel, and the families of equilibria when these fields have special directions. It is shown that all the found solutions belong to an intersection of two invariant manifolds of codimension 2. The analysis of stability in the Lyapunov sense for these solutions is conducted.

Valentin Irtegov, Tatyana Titorenko

Computing the Integer Points of a Polyhedron, I: Algorithm

Abstract

Let K be a polyhedron in \({\mathbb R}^d\), given by a system of m linear inequalities, with rational number coefficients bounded over in absolute value by L. In this series of two papers, we propose an algorithm for computing an irredundant representation of the integer points of K, in terms of “simpler” polyhedra, each of them having at least one integer point. Using the terminology of W. Pugh: for any such polyhedron P, no integer point of its grey shadow extends to an integer point of P. We show that, under mild assumptions, our algorithm runs in exponential time w.r.t. d and in polynomial w.r.t m and L. We report on a software experimentation. In this series of two papers, the first one presents our algorithm and the second one discusses our complexity estimates.

Rui-Juan Jing, Marc Moreno Maza

Computing the Integer Points of a Polyhedron, II: Complexity Estimates

Abstract

Let K be a polyhedron in \({{{\mathbb R}}}^d\), given by a system of m linear inequalities, with rational number coefficients bounded over in absolute value by L. In this series of two papers, we propose an algorithm for computing an irredundant representation of the integer points of K, in terms of “simpler” polyhedra, each of them having at least one integer point. Using the terminology of W. Pugh: for any such polyhedron P, no integer point of its grey shadow extends to an integer point of P. We show that, under mild assumptions, our algorithm runs in exponential time w.r.t. d and in polynomial w.r.t m and L. We report on a software experimentation. In this series of two papers, the first one presents our algorithm and the second one discusses our complexity estimates.

Rui-Juan Jing, Marc Moreno Maza

Non-linearity and Non-convexity in Optimal Knots Selection for Sparse Reduced Data

Abstract

The problem of fitting sparse reduced data in arbitrary Euclidean space is discussed in this work. In our setting, the unknown interpolation knots are determined upon solving the corresponding optimization task. This paper outlines the non-linearity and non-convexity of the resulting optimization problem and illustrates the latter in examples. Symbolic computation within Mathematica software is used to generate the relevant optimization scheme for estimating the missing interpolation knots. Experiments confirm the theoretical input of this work and enable numerical comparisons (again with the aid of Mathematica) between various schemes used in the optimization step. Modelling and/or fitting reduced sparse data constitutes a common problem in natural sciences (e.g. biology) and engineering (e.g. computer graphics).

Ryszard Kozera, Lyle Noakes

The Convergence Conditions of Interval Newton’s Method Based on Point Estimates

Abstract

Both Smale’s alpha theory and Rump’s interval theorem provide the conditions which guarantee the existence of a simple solution of a square nonlinear system. In this paper, we generalize the conclusion provided by Rall to reveal the relationship between Smale’s alpha theory and Rump’s interval theorem. By point estimates, we propose the conditions under which the condition of Rump’s interval theorem holds. Furthermore, using only the information of the given system at the initial approximate point, we give the convergence conditions of interval Newton’s algorithm proposed by Rump.

Zhe Li, Baocheng Wan, Shugong Zhang

Normalization of Indexed Differentials Based on Function Distance Invariants

Abstract

This paper puts forward the method of function distance invariant, and develops an efficient normalization algorithm for indexed differentials. The algorithm allows us to determine the equivalence of indexed differentials in , and is mainly based on two algorithms. One is an index replacement algorithm. The other is a normalization algorithm with respect to monoterm symmetries, whose complexity is lower than known algorithms.

Jiang Liu

Symbolic-Numeric Integration of the Dynamical Cosserat Equations

Abstract

We devise a symbolic-numeric approach to the integration of the dynamical part of the Cosserat equations, a system of nonlinear partial differential equations describing the mechanical behavior of slender structures, like fibers and rods. This is based on our previous results on the construction of a closed form general solution to the kinematic part of the Cosserat system. Our approach combines methods of numerical exponential integration and symbolic integration of the intermediate system of nonlinear ordinary differential equations describing the dynamics of one of the arbitrary vector-functions in the general solution of the kinematic part in terms of the module of the twist vector-function. We present an experimental comparison with the well-established generalized \(\alpha \)-method illustrating the computational efficiency of our approach for problems in structural mechanics.

Dmitry A. Lyakhov, Vladimir P. Gerdt, Andreas G. Weber, Dominik L. Michels

Algorithms for Zero-Dimensional Ideals Using Linear Recurrent Sequences

Abstract

Inspired by Faugère and Mou’s sparse FGLM algorithm, we show how using linear recurrent multi-dimensional sequences can allow one to perform operations such as the primary decomposition of an ideal, by computing of the annihilator of one or several such sequences.

Vincent Neiger, Hamid Rahkooy, Éric Schost

Symbolic-Numerical Analysis of the Relative Equilibria Stability in the Planar Circular Restricted Four-Body Problem

Abstract

We study the stability of relative equilibrium positions in the planar circular restricted four-body problem formulated on the basis of the Euler collinear solution of the three-body problem. The stability problem is solved in a strict nonlinear formulation in the framework of the KAM theory. We obtained algebraic equations determining the equilibrium positions and showed that there are 18 different equilibrium configurations of the system for any values of the two system parameters \(\mu _1\), \(\mu _2\). Canonical transformation of Birkhoff’s type reducing the Hamiltonian of the system to the normal form is constructed in a general symbolic form. Combining symbolic and numerical calculations, we showed that only 6 equilibrium positions are stable in Lyapunov’s sense if parameters \(\mu _1\) and \(\mu _2\) are sufficiently small, and the corresponding points in the plane \(O\mu _1\mu _2\) belong to the domain bounded by the second order resonant curve. It was shown also that the third order resonance results in instability of the equilibrium positions while in case of the fourth order resonance, either stability or instability can take place depending on the values of parameters \(\mu _1\) and \(\mu _2\). All relevant symbolic and numerical calculations are done with the aid of the computer algebra system Wolfram Mathematica.

Alexander N. Prokopenya

The Method of Collocations and Least Residuals Combining the Integral Form of Collocation Equations and the Matching Differential Relations at the Solution of PDEs

Abstract

To increase the accuracy of computations by the method of collocations and least residuals (CLR) it is proposed to increase the number of degrees of freedom with the aid of the following two techniques: an increase in the number of basis vectors and the integration of the linearized partial differential equations (PDEs) over the subcells of each cell of a spatial computational grid. The implementation of these modifications, however, leads to the necessity of increasing the amount of symbolic computations needed for obtaining the work formulas of the new versions of the CLR method. The computer algebra system (CAS) Mathematica has proved to be successful at the execution of all these computations. It is shown that the proposed new symbolic-numeric versions of the CLR method possess a higher accuracy than the previous versions of this method. Furthermore, the version of the CLR method, which employs the integral form of collocation equations, needs a much lesser number of iterations for its convergence than the “differential” CLR method.

Vasily P. Shapeev, Evgenii V. Vorozhtsov

A Special Homotopy Continuation Method for a Class of Polynomial Systems

Abstract

A special homotopy continuation method, as a combination of the polyhedral homotopy and the linear product homotopy, is proposed for computing all the isolated solutions to a special class of polynomial systems. The root number bound of this method is between the total degree bound and the mixed volume bound and can be easily computed. The new algorithm has been implemented as a program called LPH using C++. Our experiments show its efficiency compared to the polyhedral or other homotopies on such systems. As an application, the algorithm can be used to find witness points on each connected component of a real variety.

Yu Wang, Wenyuan Wu, Bican Xia

Penalty Function Based Critical Point Approach to Compute Real Witness Solution Points of Polynomial Systems

Abstract

We present a critical point method based on a penalty function for finding certain solution (witness) points on real solutions components of general real polynomial systems. Unlike other existing numerical methods, the new method does not require the input polynomial system to have pure dimension or satisfy certain regularity conditions.

This method has two stages. In the first stage it finds approximate solution points of the input system such that there is at least one real point on each connected solution component. In the second stage it refines the points by a homotopy continuation or traditional Newton iteration. The singularities of the original system are removed by embedding it in a higher dimensional space.

In this paper we also analyze the convergence rate and give an error analysis of the method. Experimental results are also given and shown to be in close agreement with the theory.

Wenyuan Wu, Changbo Chen, Greg Reid

Computing Multiple Zeros of Polynomial Systems: Case of Breadth One (Invited Talk)

Abstract

Given a polynomial system f with a multiple zero x whose Jacobian matrix at x has corank one, we show how to compute the multiplicity structure of x and the lower bound on the minimal distance between the multiple zero x and other zeros of f. If x is only given with limited accuracy, we give a numerical criterion to guarantee that f has \(\mu \) zeros (counting multiplicities) in a small ball around x. Moreover, we also show how to compute verified and narrow error bounds such that a slightly perturbed system is guaranteed to possess an isolated breadth-one singular solution within computed error bounds. Finally, we present modified Newton iterations and show that they converge quadratically if x is close to an isolated exact singular solution of f. This is joint work with Zhiwei Hao, Wenrong Jiang, Nan Li.

Lihong Zhi

Backmatter