Skip to main content

Über dieses Buch

CASC 2001 continues a tradition ~ started in 1998 ~ of international con­ ferences on the latest advances in the application of computer algebra systems to the solution of various problems in scientific computing. The three ear­ (CASs) lier conferences in this sequence, CASC'98, CASC'99, and CASC 2000, were held, Petersburg, Russia, in Munich, Germany, and in Samarkand, respectively, in St. Uzbekistan, and proved to be very successful. We have to thank the program committee, listed overleaf, for a tremendous job in soliciting and providing reviews for the submitted papers. There were more than three reviews per submission on average. The result of this job is reflected in the present volume, which contains revised versions of the accepted papers. The collection of papers included in the proceedings covers various topics of computer algebra methods, algorithms and software applied to scientific computing. In particular, five papers are devoted to the implementation of the analysis of involutive systems with the aid of CASso The specific examples include new efficient algorithms for the computation of Janet bases for monomial ideals, involutive division, involutive reduction method, etc. A number of papers deal with application of CASs for obtaining and vali­ dating new exact solutions to initial and boundary value problems for partial differential equations in mathematical physics. Several papers show how CASs can be used to obtain analytic solutions of initial and boundary value problems for ordinary differential equations and for studying their properties.



Jets. A Maple-Package for Formal Differential Geometry

The Maple-package jets was first designed to be an extension of the package desolv. In the current stage it became an independent package going beyond symmetries to handle different aspects of formal differential geometry, including some important parts of the variational bicomplex. We demonstrate this by computing the set of all Hamiltonian structures of a order at most 3, which are compatible with D x . This set includes among others the famous KdV-operator D xxx + 2/3uD x + 1/3u x .

Mohamed Barakat

Computing Stratifications of Quotients of Finite Groups and an Application to Shape Memory Alloys

When modeling shape memory alloys one has to construct a free energy Φ(F, Θ) which has to assume global minima on various strata of the orbit space of the symmetry group G depending on the temperature Θ. We provide an algorithm for decomposing a G-variety X (G finite) and its orbit space Z = X/G in different strata, each corresponding to a different orbit type. An application to the construction of Φ for Nickel-Titanium alloys is presented.

Thomas Bayer

A MuPAD Library for Differential Equations

We present an overview of the MuPAD library DETools for the analysis of differential equations. It has been developed within an object-oriented environment for the efficient representation of differential functions. Currently, the main ingredients of the library are a fairly general package for Lie symmetry analysis and a algebraic-geometric completion package for overdetermined systems.

Jay Belanger, Marcus Hausdorf, Werner M. Seiler

Algebraic Identification Algorithm and Application to Dynamical Systems

We present an algorithm for the identification of any unknown dynamical system and a partial validation of the produced model. The method consists in computing a dynamical system (B k ) whose behaviour approximates the exact system one’s, “up to order k”, when knowing only a finite set of input/output data. The approximated dynamical system provided is a bilinear system depending on some parameters. In order to preserve the generic feature of the computation, the algorithm produces a pair (bilinear system B, constraint C on parameters), where B is produced under constraint C. A computational tool is provided, in the form of Maple package DYNAMICMODEL. The model validation is a central problem in system identification [2]. It consists generally in a test that falsifies or not falsifies the model, using a validation data set. For this continuous and symbolic model, we propose an overestimation of the mistake resulting from the systems (B k ) at order k and we show the convergence towards the exact output system. We propose also a majoration, for a certain class (DP), of the gap between two consecutive outputs.

Farida Benmakrouha, Christiane Hespel, Gérard Jacob, Edouard Monnier

Cooperation between a Dynamic Geometry Environment and a Computer Algebra System for Geometric Discovery

The use of computer algebra is usually considered beneficial for mechanised reasoning in mathematical domains. We describe a program, in the application domain of geometric discovery, which supports this claim. When interfacing a standard dynamic geometry environment and Mathematica, we enhance the educational uses of geometric problem solving environments through the symbolic capabilities of computer algebra software.

Francisco Botana, José L. Valcarce

On the Stability of Steady Motions of Solar-Sail Satellite

A satellite with solar sail moving along a circular heliocentric orbit is considered. A complete set of steady motions for such a system has been obtained, and Lyapunov’s method has been employed to investigate their stability. The sufficient conditions are compared with the necessary ones. To the end of solving the problem, the capabilities of the software “Stability” for symbolic computations have been used [1].

Larissa Bourlakova

Application of Computer Algebra for Investigation of Group Properties of the Navier-Stokes Equations for Compressible Viscous Heat-Conducting Gas

In the paper the equations describing plane motion of a viscous heat-conducting perfect gas with polytropic equation of state are investigated. On the basis of methods of the group analysis of differential equations [1] some classes of exact solutions are constructed, namely, invariant and partially invariant. We use essentially the computer algebra systems for finding the symmetry group and for constructing the solution.

Vasiliy V. Bublik

Mathematica and Nilpotent Lie Superalgebras

The aim of this work is to study a family of Lie superalgebras which generalize Heisenberg Lie algebras. We prove the existence of a special basis for these superalgebras with arbitrary dimension of even part and dimension of odd part up to three. By using the software Mathematica 4.0 we classify these superalgebras for arbitrary dimension of even part and dimension of odd part up to two.

L. M. Camacho, J. R. Gómez, R. M. Navarro, I. Rodríguez

Neighborhoods of an Ordinary Linear Differential Equation

In this paper the notion of neighborhood of a linear ordinary differential equation with constant coefficients is introduced. The general concept of neighborhood is often used in Scientific Computation where involved data have limited accuracy. In this context we introduce the notion of pseudo-integral of a differential equation. Furthermore we use the notion of differential resultant in order to know the relations between the integrals of a linear ordinary differential equation with constant coefficients and the integrals of a linear ordinary differential equation in its neighborhood.

Giuseppa Carrà Ferro, Valentina Marotta

Invariants of Finite Groups and Involutive Division

The invariant ring of a finite matrix group is known to be well behaved for reflection groups and messy in general. Involutive division is a newly discovered tool in commutative algebra and in this note it is applied to the problem of finding a presentation of the ring of invariants of a finite matrix group. The first author has implemented the Janet-algorithm in MAPLE following [GeB 98a] and [GeB 98b], more precisely Gerdt’s involutive algorithm for Janet’s (involutive) division. The results of this are collected in two MAPLE-packages called INVOLUTIVE and JANET, the first dealing with polynomials and the second with linear partial differential equations. Both of these packages have a collection of other routines serving various purposes. There is also a loose connection with the MAPLE-package JETS by Mohammed Barakat, which deals with symmetries of differential equations, conservation laws etc.. Here we report on our experience with applying the package INVOLUTIVE to questions of invariant theory of finite groups. We outline an algorithm constructing a presentation of the ring of invariants of a finite complex matrix group and representing each invariant in a unique way as an expression in the generators. We also report on the limits with the present MAPLE implementation. As far as the invariant theory of finite groups proper is concerned, there is a MAPLE-package available to perform the tasks discussed here, cf. [Kern 98] or [Kern 99], based on Groebner basis techniques and even a very effective implementation in MAGMA.

C. F. Cid, W. Plesken

Symbolic Computation and Boundary Conditions for the Wave Equation

We develop a procedure using Maple for the estimation of the accuracy of approximate boundary conditions for the wave equation. To solve this equation in an infinite three dimensional domain, a spherical artificial boundary is introduced to restrict the computational domain Ω. To determine the nonreflecting boundary condition on ∂Ω, we start with a finite number of spherical harmonics for the Helmholtz equation. With a precise choice of nodes on the sphere, the theorem on Gauss-Jordan quadrature establishes the discrete orthogonality of the spherical harmonics when summed over these nodes. The nonreflecting boundary condition for the Helmholtz equation follows readily upon solving the exterior Dirichlet problem. The boundary condition for the time dependent wave equation follows directly by taking the inverse Fourier transform of the boundary condition for the Helmholtz equation. The boundary condition has the following properties: only the first derivatives in space and time appear; once the coefficients are updated in a simple way from the previous time step, the boundary condition involves only the nodes at the current time step. We derive using Maple some very precise estimates of the accuracy of these approximate boundary conditions.

A. S. Deakin, H. Rasmussen

Parametric Systems of Linear Congruences

Based on an extended quantifier elimination procedure for discretely valued fields, we devise algorithms for solving multivariate systems of linear congruences over the integers. This includes determining integer solutions for sets of moduli which are all power of a fixed prime, uniform p-adic integer solutions for parametric prime power moduli, lifting strategies for these uniform p-adic solutions for given primes, and simultaneous lifting strategies for finite sets of primes. The method is finally extended to arbitrary moduli.

Andreas Dolzmann, Thomas Sturm

Bifurcation Analysis of Low Resonant Case of the Generalized Henon - Heiles System

The paper describes the computer algebra application of the normal form method to bifurcation analysis of a low resonant case of the generalized Henon - Heiles system. A behavior of all local families of periodic solutions in system parameters is determined. Corresponding approximated solutions were checked by a comparison with the numerical solutions of the system.

Victor F. Edneral

An Involutive Reduction Method to Find Invariant Solutions for Partial Differential Equations

A standard approach to solve partial diffrential equations is the construction of invariant solutions. These solutions have to fulfill an additional equation called the invariant surface condition. This condition represents the invariance of the equation under a symmetry transformation. To solve the coupled system of the differential equation and its invariant surface condition we used a Mathematica-package which combines involutive and heuristic methods to simplify and solve this coupled system. The procedure is presented by some examples.

Joachim Engelmann, Gerd Baumann

Recurrence Functions and Numerical Characteristics of Graphs

We present a general method for the description of the structural meaning of the canonical representation coefficients of a wide class of the recurrence functions of graphs. The combinatorial objects, the so-called (j,k)-placements, are used. The algorithm, which can be realized on PC and allows to reveal some relations between the numerical characteristics of graphs, is resulted.

Gani E. Ergashev, Ulugbek H. Narzullaev

A New Combinatorial Algorithm for Large Markov Chains (Extended Abstract)

We consider large Markov chains which posses specific decomposable structure, the so called Nearly Completely Decomposable Chains (NCD chains). A new theoretical approach for approximate computations of NCD chains has been recently introduced in [11,12]. The method of forest expansions gives raise to aggregation algorithms, which approximate effectively the characteristics of Markov chain. The algorithms are based on grouping the states of a Markov chain in such a way that the probability of changing the state inside the group is of greater order of magnitude than interactions between groups. In [5] the algorithm approximating stationary distribution (described by transposed system LTx = b, where L is derived from transition matrix) was presented; in this paper we illustrate that combinatorial aggregation in the case of non-transposed system (defining e.g. mean hitting time) is not less effective. This novel approach allows us to treat both types of problems in the unified manner. To our knowledge for the first time an aggregation scheme was used to calculate Markov chain characteristics other than stationary distribution.

Anna Gambin, Piotr Pokarowski

GROOME - Tool Supported Graphical Object Oriented Modelling for Computer Algebra and Scientific Computing

This paper is devoted to Object Oriented Modelling for Computer Algebra and Scientific Computing. The tool called GROOME is presented. GROOME supports object oriented problem decomposition on the basis of graphical description techniques. Such intuitive graphical description techniques are in our opinion the best medium to present the complex numerical models and methods as well as a hierarchy of them as well as relationships among them. The meaning or semantics of graphical description documents in GROOME can be completed with symbolic equations and Maple commands. Such documents can be linked together automatically and executable Maple code can be obtained.

Victor G. Ganzha, Dmytro Chibisov, Evgenii V. Vorozhtsov

Construction of Janet Bases I. Monomial Bases

Algorithms for computation of Janet bases for monomial ideals and implementation of these algorithms are presented. As data structures for finite monomial sets the binary trees called Janet trees are selected. An algorithm for construction of a Janet basis for the ideal generated by a finite monomial set is described. This algorithm contains as subalgorithms those to search for Janet divisor in a given tree and to insert monomials into the tree in the process of completion to involution. The algorithms presented have been implemented in C in the form of package for completion of monomial sets to Janet involutive ones. An example is given to illustrate practical efficiency of the monomial algorithms and their implementation.

Vladimir P. Gerdt, Yuri A. Blinkov, Denis A. Yanovich

Construction of Janet Bases II. Polynomial Bases

In this paper we give a detailed description of an algorithm for computation of polynomial Janet bases and present its implementation in C, C++ and Reduce. This algorithm extends to polynomial ideals the algorithm for computation of monomial Janet bases presented in the first part of our paper and improves the specialization to Janet division of the general algorithm for computation of involutive polynomial bases. The computational efficiency of our codes is compared with that of computer algebra system Singular which provides one of the best implementations of the Buchberger algorithm for computation of Gröbner bases.

Vladimir P. Gerdt, Yuri A. Blinkov, Denis A. Yanovich

Low-Dimensional Quasi-Filiform Lie Algebras with Great Length

We consider the connected integer gradations on a type of n dimensional nilpotent Lie algebras. We study the case where the number of non trivial subspaces is n - 1 for those gradations, when the nilindex of the algebras is n - 2 (quasi-filiform Lie algebras). We show how Symbolic Calculus can be useful to obtain the classification of such a family of graded algebras, which is determined for n ≤ 15.

J. R. Gómez, A. Jiménez-Merchán, J. Reyes

Algebraic Methods for Sectioning Parametric Surfaces

This paper is devoted to show how the already widely used Scientific Computing Systems (in our case Maple) integrating symbolic and numeric capabilities can be used to develop Problem Solving Environments very useful to solve problems into a CAD/CAM framework before they are integrated into a concrete CAD/CAM system. It is shown and motivated how algebraic techniques and Scientific Computing Systems can be very useful in Computer Aided Geometric Design by presenting how generic implicitation can be used to solve problems arising when computing the planar section of a parametric surface and to the computation (topologically exact) of a revolution surface sectioning.

Jesus Espinola, Laureano Gonzalez-Vega, Ioana Necula

The Methods of Computer Algebra and the Arnold-Moser Theorem

It is well known that the problem of stability of the particular solutions of Hamilton systems in Lyapunov sense cannot be solved within the framework of the classical stability theory. For Hamilton systems with two degrees of freedom the above problem is investigated within the framework of the KAM theory on the basis of the well-known theorem of Arnold-Moser about stability in the so-called “elliptic case”. We formulate and investigate the problem of the stability of equilibrium state for dynamic models termed restricted problems of many (n > 3) bodies. All necessary analytical transformations, switching of linearization of the differential equations, and the normalization of hamiltonians after Birkhoff are executed with the help of the System of Symbolical Calculations (SSC) “Mathematica”.

E. A. Grebenikov

Symbolic Algorithms of Algebraic Perturbation Theory: Hydrogen Atom in the Field of Distant Charge

We present symbolic algorithms implemented in REDUCE 3.6 for evaluation of eigenvalues and eigenfunctions of a hydrogen atom in the field of a distant point charge. These solutions are presented as perturbation series by a small parameter. This parameter is the inverse value of the separation between the distant point charge and the hydrogen like atom nucleus. Algebraic perturbation theory schemes are built up using the irreducible representations of the dynamical symmetry algebra so(4,2). The representations are connected by the tilting transformations with wave functions of the discrete spectrum of the hydrogen atom in an arbitrary bound state characterized by a set of parabolic or spherical quantum numbers. Such a construction is based on a reduction of the unperturbed Hamiltonian and polynomial perturbation operators via generators of the algebra. The efficiency of the proposed perturbation scheme and symbolic algorithm is demonstrated by calculating the coefficients of the high order perturbation series via the parabolic quantum numbers.

Alexander Gusev, Valentin Samoilov, Vitaly Rostovtsev, Sergue Vinitsky

Perturbation versus Differentiation Indices

We discuss the relation between perturbation and differentiation indices for overdetermined systems of differential equations based on the formal theory. We show how the Cartan normal form of an involutive system can be used to extend the notion of an underlying equation from differential algebraic equations to partial differential equations. This allows us to generalise results of Campbell and Gear on the relation between perturbation and differentiation indices to systems of partial differential equations.

Marcus Hausdorf, Werner M. Seiler

Employment of the Gröbner Bases in Analysis of Systems Having Algebraic First Integrals

The paper discusses some problems of analysis of the phase space of mechanical systems having algebraic first integrals with the aid of the Gröbner bases. An attempt has been made to perform the analytical computations needed in this case by the system of computer algebra available.

Valentin Irtegov, Tatyana Titorenko

“Coalgebra” Structures on 1-Homological Models for Commutative Differential Graded Algebras

In [3] “small” 1-homological model H of a commutative differential graded algebra is described. Homological Perturbation Theory (HPT) [7-9] provides an explicit description of an A∞-coalgebra structure (Δ123,...) of H. In this paper, we are mainly interested in the determination of the map Δ2 : H - HH ⊗ H as a first step in the study of this structure. Developing the techniques given in [20] (inversion theory), we get an important improvement in the computation of Δ2 with regard to the first formula given by HPT. In the case of purely quadratic algebras, we sketch a procedure for giving the complete Hopf algebra structure of its 1-homology.

M. J. Jiménez, P. Real

Conservative Finite Difference Schemes for Cosymmetric Systems

We consider the application of computer algebra for the derivation of the formula for the preservation of the cosymmetry property through discretization of partial differential equations. The finite difference approximations of differential operators for both regular and staggered grids are derived and applied to the planar filtration-convection problem.

Bülent Karasözen, Vyacheslav G. Tsybulin

A Mathematica Solver for Two-Point Singularly-Perturbed Boundary Value Problems

This paper introduces a Mathematica solver which constructs approximate symbolic solutions of second-order singularly-perturbed boundary value problems. The employed symbolic technique is based on the method of matched asymptotic expansion and the Nipp polyhedron algorithm for finding appropriate scalings in local approximating systems. The main command BVPSolve uses the standard Mathematica syntax of the Solve-type commands. The package finds approximate solutions of second-order linear, quasilinear and semilinear singularly perturbed boundary value problems. Several illustrative examples are shown. The package can be used in research and teaching. It can also be used for initialising numerical solvers for boundary-value problems.

Raya Khanin

A New Algorithm for Computing Cohomologies of Lie Superalgebras

In this paper two versions of a new algorithm for computing cohomologies of Lie (super)algebras are described. The algorithm is based on splitting the full cochain complex into smaller subcomplexes. This approach makes the computation essentially more efficient since in most cases the dimensions of full cochain spaces included in the complexes are very high and these high-dimensional spaces can be divided into much smaller subspaces. Examples illustrating the work of the algorithm are given.

Vladimir V. Kornyak

Parallel Computing with Mathematica

The MathLink communication protocol can be used to control several Mathematica kernel processes from within Mathematica. This feature allows the implementation of an environment for parallel programming, the Parallel Computing Toolkit, using processes with distributed memory. The toolkit is written completely in Mathematica in a machine-independent way, allowing its use in heterogeneous networks without common file systems, as well as on multi-processor machines. All library and application code is distributed through MathLink. Mathematica’s high-level language allows for the easy and natural expression of parallel programming paradigms and for the parallelization of other than purely numeric computations. Examples presented include virtual shared memory, fault-tolerance, and automatic parallelization of functional programming constructs.

Roman Mäder

Solution of Systems of Linear Diophantine Equations

Two new methods to solve linear systems of Diophantine equations are proposed - modular (CRT) and p-adic (Hensel). Each of them allows to obtain solutions of a system with the size n x m with the complexity O(nßm). For quasi-square systems, the p-adic method allows to obtain solution with the complexity O(n3), and the modular method with complexity O(nß+1). Both estimates have the accuracy up to the logarithmic multipliers, ß being the power in the estimation of matrix multiplication time.

Gennadi I. Malaschonok

SYMOPT: Symbolic Parametric Mathematical Programming

We present the Reduce-package Symopt that is devoted to symbolic parametric mathematical programming i.e. the solution of parametric optimization problems. This paper formulates problem types that are solvable with Symopt, explains the solving methods, demonstrates various types of usage and the handling of solving processes depending on the users options.

Isolde Mazzucco

Representing Graph Properties by Polynomial Ideals

Computer algebra provides means to obtain a diversity of results in many areas of science. In this paper we explore the possibility of representing properties of graphs by polynomial ideals. We show that several properties (emptiness, colorability) admit such representation, but we also work out limitations of this approach.

Michal Mnuk

Parametric G1-Blending of Several Surfaces

In this paper we present a symbolic algorithm for blending parametrically with G1-continuity a collection of rational surfaces with rational clipping intersections. The method provides a family of parametrizations that depends on a set of parameters, which number can be controlled in advance, and that can be used further in the modeling process. For this purpose, we introduce the notion of curves being in good position, that can always be assumed w.l.o.g., and we prove the main property of a set of rational curves in good position, that guarantees that the method always provides a correct solution.

Sonia Pérez-Díaz, Rafael Sendra

A Method of Logic Deduction and Verification in KBS Using Positive Integers

Classic propositional Boolean algebra is modelized in this paper as a subset of IN (the divisors of a certain product of prime numbers) with operations gcd and lcm. The isomorphism is constructed in a way that recalls Gödel numbers. This approach can be used to study logic deduction and to check the consistency of Rule-Based Knowledge Based Systems. An implementation in the Computer Algebra system Maple, that uses intensively exact arithmetic, is included as an appendix. Although the growth of the integers involved makes this implementation interesting only if the number of propositional variables is not greater than 8, we think its simplicity makes it very interesting to illustrate KBS behaviour.

E. Roanes-Lozano, E. Roanes-Macías, L. M. Laita

Progressive Long Waves on a Slope (A New Solution to the Euler Equation?)

Computer algebra system is used for deriving and studying high-order Boussinesq-type equations for long periodic nonlinear waves climbing a sloping beach. Potential and surface elevation for wave motion are expanded in Fourier series up to the fourth harmonic inclusively. Coefficients of these series are explicitly presented as polynomials in Bessel functions. One may speculate that the obtained expressions are the first terms of the expanded exact solution to the Euler equation for surface waves.

Alexander Shermenev

The Method of Newton Polyhedra for Investigating Singular Positions of Some Mechanisms

In the paper the singular positions of a displacement function of the plane mechanism with three degrees of freedom are investigated. The singularities of this function are subdivided into two types. The singularities of the displacement function as a function of control coordinates belong to the first type. The second type singularities are such singularities, in the neighbourhood of which the coordinates of position and control do not form an n- dimensional manifold (n is the number of degrees of freedom).

Akhmadjon Soleev, Adizjon S. Barotov

Algebraic Predicates for Empirical Data

It is widely assumed that the assignment of truth values to non-trivial algebraic predicates containing numerical data is possible only if the data are exact and if exact computation is employed. But in many application areas the answers to questions like “Are all zeros of that (model) polynomial in the left half-plane?” are of principal importance. We develop a framework in which algebraic predicates with empirical data are assigned a positive real number in place of a truth value. This validity value permits an interpretation which is more informative that the classical “yes - no” answer. It depends continuously on the data and can thus be computed approximately by floating-point arithmetic. A number of non-trivial examples support the usefulness of our approach.

Hans J. Stetter

Fractional Driftless Fokker-Planck Equation with Power Law Diffusion Coefficients

A generalized fractional drift less Fokker-Planck equation is discussed with a diffusion constant depending on the space coordinates by a power law.The solution of this equation contains Lévy asymptotics for some special power law diffusion constants.

Norbert Südland, Gerd Baumann, Theo F. Nonnenmacher

Factorization of Overdetermined Systems of Linear Partial Differential Equations with Finite-Dimensional Solution Space

We give an improved algorithm for factorization, i.e. decomposition of such systems with rational function coefficients into lowerorder systems. This algorithm is based on the recent algorithm of Z. Li and F. Schwarz for construction of hyperexponential solutions. An analogue of the Loewy-Ore theory of factorization is exposed. We also prove an analogue of a result by E. Landau on uniqueness of the number and orders of irreducible factors.

Serguei P. Tsarev

Semilinear Motion Planning Among Moving Objects in REDLOG

We study motion planning for rigid objects moving within a non-static, time dependent two or three-dimensional environment. As in a previous paper [19], both the object to be moved and the free space are both semilinear sets with no convexity assumptions. The admissible motions are finite continuous sequences of translations with fixed speeds along finitely many prescribed directions. But now the free space can change in a piecewise linear way with time. So the problem of path finding becomes a problem of finding a piecewise linear time-dependent trajectory of the given semilinear object from a given initial position to a semilinear set of admissible final positions that may change semilinearly with time. Moreover the trajectory is limited to a prescribed time interval. By a strong generalization of the static case we show how to model and solve this problem for a bounded number of translations by linear real quantifier elimination. The worst case complexity of the algorithms is similar as in the static case. Experimental results using the elimination facilities of the Redlog package of Reduce show the practical relevance of the approach. This concerns in particular semilinear motion planning within a static environment with additional moving objects. Applications include automatic motion planning of an automobile or aircraft within moving traffic, and automatic motion planning of a carrier for material in a factory with other moving carriers.

Volker Weispfenning


Weitere Informationen