Computer Algebra in Scientific Computing

Frontmatter

A Recurrent Method for Constructing Irreducible Polynomials over Finite Fields

Abstract

In this paper we consider irreducibility of the polynomial composition of the form, \(\left(x^p-x+\delta_2\right)^n P \left( \frac{x^p-x+\delta_1}{x^p-x+\delta_2}\right)\), over \(\mathbb{F}_q\) under certain conditions. Furthermore, a computationally simple and explicit method of constructing recursive sequences of irreducible polynomials of degree np ^k : (k = 1,2,3, ⋯ ) over \(\mathbb{F}_q\) is given.

Sergey Abrahamyan, Melsik Kyureghyan

Higher-Order Linear Differential Systems with Truncated Coefficients

Abstract

We consider the following problem: given a linear differential system with formal Laurent series coefficients, we want to decide whether the system has non-zero Laurent series solutions, and find all such solutions if they exist. Let us also assume we need only a given positive integer number l of initial terms of these series solutions. How many initial terms of the coefficients of the original system should we use to construct what we need?

Supposing that the series coefficients of the original systems are represented algorithmically, we show that these questions are undecidable in general. However, they are decidable in the scalar case and in the case when we know in advance that a given system has an invertible leading matrix. We use our results in order to improve some functionality of the Maple [17] package ISOLDE [11].

S. A. Abramov, M. A. Barkatou, E. Pflügel

Topology of Families of Implicit Algebraic Surfaces Depending on a Parameter

Abstract

Given a family of algebraic surfaces, implicitly defined, depending on a parameter t, here we provide an algorithm for computing the different shapes arising in the family. The algorithm decomposes the real line into finitely many pieces (points and intervals) so that over each interval the shape is invariant, in the sense that the topology of the family can be described by means of the same simplicial complex. As a consequence, by applying known algorithms ([1], [6], [7], [11]) the different shapes in the family can be computed. The algorithm is due to a generalization of the ideas in [2] to the surface case.

Juan Gerardo Alcázar

A Modular Approach for Beam Lines Design

Abstract

We discuss advantages of numerical simulation based on symbolic presentations of beam line dynamical models. In some previous papers, some of these features were discussed. In this paper, we demonstrate how the symbolic presentation of necessary information can provide an in-depth study of different features of complex systems. For this purpose, we suggest a modular principle for all levels of the modeling and optimization procedures. This principle is based on so-called LEGO objects, which have both symbolic and numerical representation. For beam line design, it is necessary to support three types of similar objects. The first of them contains all necessary objects for beam line components description, the second contains all objects which correspond to particle beam models, and the third contains all objects corresponding to a transfer map (“a beam propagator”). In the suggested approach, the beam propagator is presented as a set of two-dimensional matrices describing different kinds of beam or beam line properties up to some approximation order. These matrices can be computed both in symbolic and numerical forms up to the necessary approximation order of the nonlinear effects. An example of practical application is demonstrated.

Serge N. Andrianov

Computations on Simple Games Using RelView

Abstract

Simple games are a powerful tool to analyze decision-making and coalition formation in social and political life. In this paper we present relational models of simple games and develop relational algorithms for solving some game-theoretic basic problems. The algorithms immediately can be transformed into the language of the Computer Algebra system RelView and, therefore, the system can be used to solve the problems and to visualize the results of the computations.

Rudolf Berghammer, Agnieszka Rusinowska, Harrie de Swart

On the Regularity Property of Differential Polynomials Modulo Regular Differential Chains

Abstract

This paper provides an algorithm which computes the normal form of a rational differential fraction modulo a regular differential chain if, and only if, this normal form exists. A regularity test for polynomials modulo regular chains is revisited in the nondifferential setting and lifted to differential algebra. A new characterization of regular chains is provided.

François Boulier, François Lemaire, Alexandre Sedoglavic

Chemical Reaction Systems, Computer Algebra and Systems Biology

(Invited Talk)

Abstract

In this invited paper, we survey some of the results obtained in the computer algebra team of Lille, in the domain of systems biology. So far, we have mostly focused on models (systems of equations) arising from generalized chemical reaction systems. Eight years ago, our team was involved in a joint project, with physicists and biologists, on the modeling problem of the circadian clock of the green algae Ostreococcus tauri. This cooperation led us to different algorithms dedicated to the reduction problem of the deterministic models of chemical reaction systems. More recently, we have been working more tightly with another team of our lab, the BioComputing group, interested by the stochastic dynamics of chemical reaction systems. This cooperation led us to efficient algorithms for building the ODE systems which define the statistical moments associated to these dynamics. Most of these algorithms were implemented in the MAPLE computer algebra software. We have chosen to present them through the corresponding MAPLE packages.

François Boulier, François Lemaire, Michel Petitot, Alexandre Sedoglavic

On the Stability of Equilibrium Positions in the Circular Restricted Four-Body Problem

Abstract

We consider the stability of equilibrium positions in the planar circular restricted four-body problem formulated on the basis of Lagrange’s triangular solution of the three-body problem. The stability problem is solved in a strict nonlinear formulation on the basis of Arnold–Moser and Markeev theorems. Peculiar properties of the Hamiltonian normalization are discussed, and the influence of the third and fourth order resonances on stability of the equilibrium positions has been analyzed.

Dzmitry A. Budzko, Alexander N. Prokopenya

Semi-algebraic Description of the Equilibria of Dynamical Systems

Abstract

We study continuous dynamical systems defined by autonomous ordinary differential equations, themselves given by parametric rational functions. For such systems, we provide semi-algebraic descriptions of their hyperbolic and non-hyperbolic equilibria, their asymptotically stable hyperbolic equilibria, their Hopf bifurcations. To this end, we revisit various criteria on sign conditions for the roots of a real parametric univariate polynomial. In addition, we introduce the notion of comprehensive triangular decomposition of a semi-algebraic system and demonstrate that it is well adapted for our study.

Changbo Chen, Marc Moreno Maza

Normal Forms of Two p: − q Resonant Polynomial Vector Fields

Abstract

We investigate a property of normal forms of p: − q resonant vector fields, which is related to isochronicity. The problem is reduced to studying polynomial ideals and their varieties which is performed using tools of computational algebra.

Victor Edneral, Valery G. Romanovski

On Muldowney’s Criteria for Polynomial Vector Fields with Constraints

Abstract

We study Muldowney’s extension of the classical Bendixson-Dulac criterion for excluding periodic orbits to higher dimensions for polynomial vector fields. Using the formulation of Muldowney’s sufficient criteria for excluding periodic orbits of the parameterized vector field on a convex set as a quantifier elimination problem over the ordered field of the reals we provide case studies of some systems arising in the life sciences. We discuss the use of simple conservation constraints and the use of parametric constraints for describing simple convex polytopes on which periodic orbits can be excluded by Muldowney’s criteria.

Hassan Errami, Werner M. Seiler, Thomas Sturm, Andreas Weber

Knowledge-Based Automatic Generation of Partitioned Matrix Expressions

Abstract

In a series of papers it has been shown that for many linear algebra operations it is possible to generate families of algorithms by following a systematic procedure. Although powerful, such a methodology involves complex algebraic manipulation, symbolic computations and pattern matching, making the generation a process challenging to be performed by hand. We aim for a fully automated system that from the sole description of a target operation creates multiple algorithms without any human intervention. Our approach consists of three main stages. The first stage yields the core object for the entire process, the Partitioned Matrix Expression (PME), which establishes how the target problem may be decomposed in terms of simpler sub-problems. In the second stage the PME is inspected to identify predicates, the Loop-Invariants, to be used to set up the skeleton of a family of proofs of correctness. In the third and last stage the actual algorithms are constructed so that each of them satisfies its corresponding proof of correctness. In this paper we focus on the first stage of the process, the automatic generation of Partitioned Matrix Expressions. In particular, we discuss the steps leading to a PME and the knowledge necessary for a symbolic system to perform such steps. We also introduce cl1ck, a prototype system written in Mathematica that generates PMEs automatically.

Diego Fabregat-Traver, Paolo Bientinesi

Involutive Division Generated by an Antigraded Monomial Ordering

Abstract

In the present paper we consider a class of involutive monomial divisions pairwise constructed by the partition of variables into multiplicative and nonmultiplicative generated by a total monomial ordering. If this ordering is admissible or the inverse of an admissible ordering, then the involutive division generated possesses all algorithmically important properties such as continuity, constructivity, and noetherianity. Among all such divisions, we single out those generated by antigraded monomial orderings. We demonstrate, by example of the antigraded lexicographic ordering, that the divisions of this class are heuristically better than the classical Janet division. The last division is pairwise generated by the pure lexicographic ordering and up to now has been considered as computationally best.

Vladimir P. Gerdt, Yuri A. Blinkov

Symbolic-Numerical Algorithms to Solve the Quantum Tunneling Problem for a Coupled Pair of Ions

Abstract

Symbolic-numerical algorithms for solving a boundary value problem (BVP) for the 2D Schrödinger equation with homogeneous third type boundary conditions to study the quantum tunneling model of a coupled pair of nonidentical ions are described. The Kantorovich reduction of the above problem with non-symmetric long-range potentials to the BVPs for sets of the second order ordinary differential equations (ODEs) is given by expanding solution over the one-parametric set of basis functions. Symbolic algorithms for evaluation of asymptotics of the basis functions, effective potentials, and linear independent solutions of the ODEs in the form of inverse power series of independent variable at large values are given by using appropriate etalon equations. Benchmark calculation of quantum tunneling problem of coupled pair of identical ions through Coulomb-like barrier is presented.

A. A. Gusev, S. I. Vinitsky, O. Chuluunbaatar, V. P. Gerdt, V. A. Rostovtsev

Symbolic-Numeric Investigation of the Aerodynamic Forces Influence on Satellite Dynamics

Abstract

An approach for symbolic-numeric stability analysis of equilibrium orientations of a satellite in a circular orbit under the influence of gravitational and aerodynamic forces is considered. The stationary motions of a satellite are governed by a system of nonlinear algebraic equations. A computer algebra method based on an algorithm for the construction of a Groebner basis and the resultant concept is proposed for determining all equilibrium orientations of a satellite with a given aerodynamic torque and given principal central moments of inertia. It is shown that equilibrium orientations are determined by real solutions of algebraic equation of the twelfth degree. Evolution of domains with a fixed number of equilibria is investigated in detail. The stability analysis of equilibria is performed on the basis of Lyapunov theorem. The equilibrium orientations and their stability are analyzed numerically.

Sergey A. Gutnik

Practical Divide-and-Conquer Algorithms for Polynomial Arithmetic

Abstract

We investigate two practical divide-and-conquer style algorithms for univariate polynomial arithmetic. First we revisit an algorithm originally described by Brent and Kung for composition of power series, showing that it can be applied practically to composition of polynomials in ℤ[x] given in the standard monomial basis. We offer a complexity analysis, showing that it is asymptotically fast, avoiding coefficient explosion in ℤ[x]. Secondly we provide an improvement to Mulders’ polynomial division algorithm. We show that it is particularly efficient compared with the multimodular algorithm. The algorithms are straightforward to implement and available in the open source FLINT C library. We offer a practical comparison of our implementations with various computer algebra systems.

William Hart, Andrew Novocin

Fast and Robust Symbolic Model Order Reduction with Analog Insydes

Abstract

Nowadays analog circuits become more and more complex. The growing number of devices hinder to understand the full behavior of these and new methods are required to support the design. This paper presents two new methods for handling complex nonlinear analog circuits which are available in the new release Analog Insydes 2011, the Mathematica toolbox for symbolic modeling, analysis and reduction of analog circuits. The transient symbolic model order reduction allows the approximation of behavioral models keeping static and dynamic properties. The new solving algorithm for symbolic equation systems based on sequential equations accelerates the simulation of the reference system as well as the verification of the reduced models. Furthermore, it increases the robustness of the solver permitting analyzes of significantly larger symbolic systems. As example, a voltage controller circuit is reduced using the introduced methods.

Matthias Hauser, Christian Salzig, Alexander Dreyer

On Invariant Manifolds of Lagrange Systems

Abstract

This paper is a continuation of the previous work [1]. In the present paper we propose a new approach for obtaining and qualitative analysis of invariant manifolds of Lagrange systems, which possess cyclic first integrals. The main idea consists in the use of “extended” characteristic functions. The proposed approach is demonstrated by examples of concrete mechanical systems. The computer algebra system (CAS) “Mathematica” is applied for computations.

Valentin Irtegov, Tatyana Titorenko

Construction of Explicit Optimal Value Functions by a Symbolic-Numeric Cylindrical Algebraic Decomposition

Abstract

Recently parametric treatment of constraint solving and optimization problems has received considerable attention in science and engineering. In this paper we show an efficient and systematic algorithm for parametric programming, i.e. computing exact optimal value functions, based on a specialized symbolic-numeric cylindrical algebraic decomposition. We also present some practical application examples from system and control theory.

Hidenao Iwane, Akifumi Kira, Hirokazu Anai

Convection in a Porous Medium and Mimetic Scheme in Polar Coordinates

Abstract

Analytical investigation of natural convection of the incompressible fluid in the porous media based on the Darcy hypothesis (Lapwood convection) gives intriguing branching off of one-parameter family of convective patterns. This scenario may be suppressed in computations when governing equations are approximated by schemes which do not preserve the cosymmetry property. We consider the problem in polar coordinates and construct a mimetic finite-difference scheme using computer algebra tools. The family of steady states is computed and it is demonstrated that this family disappears under non-mimetic approximation.

Bülent Karasözen, Anastasia Trofimova, Vyacheslav Tsybulin

Computations in Finite Groups and Quantum Physics

Abstract

Mathematical core of quantum mechanics is the theory of unitary representations of symmetries of physical systems. We argue that quantum behavior is a natural result of extraction of “observable” information about systems containing “unobservable” elements in their descriptions. Since our aim is physics where the choice between finite and infinite descriptions can not have any empirical consequences, we consider the problem in the finite background. Besides, there are many indications from observations — from the lepton mixing data, for example — that finite groups underly phenomena in particle physics at the deep level. The “finite” approach allows to reduce any quantum dynamics to the simple permutation dynamics and, thus, to express quantum observables in terms of permutation invariants of symmetry groups and their integer characteristics such as sizes of conjugate classes, sizes of group orbits, class coefficients, and dimensions of representations. Our study has been accompanied by computations with finite groups, their representations and invariants. We have used both our C implementation of algorithms for working with groups and computer algebra system GAP.

Vladimir V. Kornyak

Regular and Singular Boundary Problems in Maple

Abstract

We describe a new maple package for treating boundary problems for linear ordinary differential equations, allowing two-/multi-point as well as Stieltjes boundary conditions. For expressing differential operators, boundary conditions, and Green’s operators, we employ the algebra of integro-differential operators. The operations implemented for regular boundary problems include computing Green’s operators as well as composing and factoring boundary problems. Our symbolic approach to singular boundary problems is new; it provides algorithms for computing compatibility conditions and generalized Green’s operators.

Anja Korporal, Georg Regensburger, Markus Rosenkranz

Algebraic Structures as Typed Objects

Abstract

Following the research direction of strongly typed, generic, object oriented computer algebra software, we examine the modeling of algebraic structures as typed objects in this paper. We discuss the design and implementation of algebraic and transcendental extension fields together with the modeling of real algebraic and complex algebraic extension fields. We will show that the modeling of the relation between algebraic and real algebraic extension fields using the delegation design concept has advantages over the modeling as sub-types using sub-class implementation. We further present a summary of design problems, which we have encountered so far with our implementation in Java and present possible solutions in Scala.

Heinz Kredel, Raphael Jolly

On Two-Generated Non-commutative Algebras Subject to the Affine Relation

Abstract

We consider algebras over a field \({\mathbb K}\), generated by two variables x and y subject to the single relation yx = q xy + αx + βy + γ for \(q\in{\mathbb K}^*\) and \(\alpha, \beta, \gamma \in {\mathbb K}\). We prove, that among such algebras there are precisely five isomorphism classes. The representatives of these classes, which are ubiquitous operator algebras, are called model algebras. We derive explicit multiplication formulas for y ^m ·x ⁿ in terms of standard monomials x ⁱ y ^j for many algebras of the considered type. Such formulas are used in e. g. establishing formulas of binomial type and in an implementation of non-commutative multiplication in a computer algebra system. By using the formulas we also study centers and ring-theoretic properties of the non-commutative model algebras.

Viktor Levandovskyy, Christoph Koutschan, Oleksandr Motsak

Acceleration of the Inversion of Triangular Toeplitz Matrices and Polynomial Division

Abstract

Computing the reciprocal of a polynomial in z modulo a power z ⁿ is well known to be closely linked to polynomial division and equivalent to the inversion of an n×n triangular Toeplitz matrix. The degree k of the polynomial is precisely the bandwidth of the matrix, and so the matrix is banded iff k ≪ n. We employ the above equivalence and some elementary but novel and nontrivial techniques to obtain minor yet noticeable acceleration of the solution of the cited fundamental computational problems.

Brian J. Murphy

Computing a Basin of Attraction to a Target Region by Solving Bilinear Semi-Definite Problems

Abstract

In this paper, we present a sum of squares programming based method for computing a basin of attraction to a target region as large as possible by iteratively searching for Lyapunov-like functions. We start with the basic mathematical notions and show how attraction to a target region can be ensured by Lyapunov-like functions. Then, we present an initial framework for getting an increasing sequence of basins of attraction by iteratively computing Lyapunov-like functions. This framework can be realized by solving bilinear semi-definite problems based on sums of squares decomposition. We implement our algorithm and test it on some interesting examples. The computation results show the usefulness of our method.

Zhikun She, Bai Xue

Symbolic-Numeric Solution of Ill-Conditioned Polynomial Systems (Survey Talk Overview) (Invited Talk)

Abstract

This is a survey talk about some recent symbolic-numeric techniques to solve ill-conditioned multivariate polynomial systems. In particular, we will concentrate on systems that are over-constrained or have roots with multiplicities, and are given with inexact coefficients. First I give some theoretical background on polynomial systems with inexact coefficients, ill-posed and ill-conditioned problems, and on the objectives when trying to solve these systems. Next, I will describe a family of iterative techniques which, for a given inexact system of polynomials and given root structure, computes the nearest system which has roots with the given structure. Finally, I present a global method to solve multivariate polynomial systems which are near root multiplicities and thus have clusters of roots. The method computes a new system which is “square-free”, i.e. it has exactly one root in each cluster near the arithmetic mean of the cluster. This method is global in the sense that it works simultaneously for all clusters.

The results presented in the talk are joint work with Itnuit Janovitz-Freireich, Bernard Mourrain, Scott Pope, Lajos Rónyai, Olivier Ruatta, and Mark Sciabica.

Agnes Szanto

Symbolic-Manipulation Constructions of Hilbert-Space Metrics in Quantum Mechanics

Abstract

The recently formulated quantum-mechanics problem of the determination of the Hilbert-space metric Θ which renders a given Hamiltonian H self-adjoint is addressed. Via an exactly solvable example of the so called Gegenbauerian quantum-lattice oscillator it is demonstrated that the construction (basically, the solution of the so called Dieudonné’s operator equation) and analysis of suitable Θ = Θ(H) (i.e., the determination of their domain’s “exceptional-point” boundary) may enormously be facilitated via symbolic algebraic manipulations and via the MAPLE-supported numerics and graphics.

Miloslav Znojil

Backmatter