Skip to main content
main-content

Über dieses Buch

The development of powerful computer algebra systems has considerably ex­ tended the scope of problems of scientific computing which can now be solved successfully with the aid of computers. However, as the field of applications of computer algebra in scientific computing becomes broader and more complex, there is a danger of separation between theory, systems, and applications. For this reason, we felt the need to bring together the researchers who now ap­ ply the tools of computer algebra for the solution of problems in scientific computing, in order to foster new and closer interactions. CASC'99 is the second conference devoted to applications of computer al­ gebra in scientific computing. The first conference in this sequence, CASC'98, was held 20-24 April 1998 in St. Petersburg, Russia. This volume contains revised versions of the papers submitted by the par­ ticipants and accepted by the program committee after a thorough reviewing process. The collection of papers included in the proceedings covers various topics of computer algebra methods, algorithms and software applied to scien­ tific computing: symbolic-numeric analysis and solving differential equations, efficient computations with polynomials, groups, matrices and other related objects, special purpose programming environments, application to physics, mechanics, optics and to other areas. In particular, a significant group of papers deals with applications of com­ puter algebra methods for the solution of current problems in group theory, which mostly arise in mathematical physics.

Inhaltsverzeichnis

Frontmatter

Solution of Ordinary Differential Equations with MathLie

Method of Canonical Variables

This article discusses Lie’s method of canonical variables to solve ordinary differential equations. The method of canonical variables is based on point symmetries and allows to construct transformations which simplify the equation prior to its solution. The method of canonical variables is closely related to the methods of first integrals and the method of first order partial differential equations. We discuss the necessary tools, the skeleton and the class of solution, providing the solution in connection with computer algebra. The procedure of canonical variables is algorithmic and implemented in MathLie. We demonstrate the application of the method on first- and second-order ordinary differential equations.

Gerd Baumann

Analysis of Stability of Rational Approximations through Computer Algebra

We present a Mathematica package to compute the interval of stability of one or more rational approximations for mathematical functions. This analysis has a strong connection with the linear stability theory of numerical methods for Ordinary Differential Equations. As an example of the application of this package, we analyze the periodicity properties of Padé approximations for the cosine function. Moreover, we show its usefulness in the derivation of new numerical methods, by applying it to maximize the periodicity interval of collocation-based methods for second order initial value problems.

Massimo Cafaro, Beatrice Paternoster

An Automatic Symbolic-Numeric Taylor Series ODE Solver

One of the basic techniques in every mathematician’s toolkit is the Taylor series representation of functions. It is of such fundamental importance and it is so well understood that its use is often a first choice in numerical analysis. This faith has not, unfortunately, been transferred to the design of computer algorithms.Approximation by use of Taylor series methods is inherently partly a symbolic process and partly numeric. This aspect has often, with reason, been regarded as a major hindrance in algorithm design. Whilst attempts have been made in the past to build a consistent set of programs for the symbolic and numeric paradigms, these have been necessarily multi-stage processes.Using current technology it has at last become possible to integrate these two concepts and build an automatic adaptive symbolic-numeric algorithm within a uniform framework which can hide the internal workings behind a modern interface.

Brian J. Dupée, James H. Davenport

About Normal Form Method

The paper describes usage of a normal form method for building an approximation of families of periodic solutions of nonlinear autonomous ordinary differential equations (ODEs). For illustration a center case and a limit circle axe chosen.

Victor F. Edneral

Computer Algebra Investigation of Equivalence in 4-node Plane Stress/Strain Finite Elements

In this investigation, with the aid of computer algebra, a diagram showing equivalences between finite element formulations or techniques, among which including two newly formulated hybrid mixed field principles, in a 4-node plane stress/strain element was obtained. In the investigation, some known equivalence relations were confirmed; some new equivalence relations, mainly between the hybrid mixed field formulations and the others, were detected. The investigation shows that with computer algebra it is much easier to conduct parameter study in simple elements and it might provide a powerful tool for exploring more complex equivalence relations in higher order elements. It is observed from the investigation that if a finite element technique is hard to fit in a conventional variational principle, it might have a counterpart in a properly modified variational principle. The obtained equivalence diagram might provide information for establishing a more generally valid mathematical principle or theorem.

Anders Eriksson, Yunhua Luo, Costin Pacoste

Symmetry Theorems for the Newtonian 4- and 5-body Problems with Equal Masses

We present a new proof of the algebraic part of a symmetry theorem for the central configurations of the newtonian planar 4-body problem with equal masses, using Gröbner bases. This approach is used to obtain a new symmetry theorem for the central configurations of the newtonian spatial 5-body problem with equal masses in the convex case. In fact we prove a more general statement of the theorem, valid for a class of potentials defined by functions with increasing and concave derivatives.

Jean-Charles Faugère, Ilias Kotsireas

Symbolic Derivation of Different Class of High-order Compact Schemes for Partial Differential Equations

A symbolic procedure for deriving finite difference approximations for partial differential equations is described. We restrict our study to high-order compact schemes in conservative and non-conservative form.

Michel Fournié

Implementation of Aerodynamic Computations with Mathematica

We present a new symbolic-numerical method for stability investigation of complex finite difference or finite volume schemes for the Euler equations on curvilinear grids. We apply the method to investigation of a three-stage Runge-Kutta finite volume scheme augmented by artificial dissipator and obtain the stability condition, which is then incorporated in the Mathematica 3.0 code for aerodynamic computations. These computations for a wide range of freestream Mach numbers confirm the validity of the obtained stability condition. Results of aerodynamic numerical computations are presented.

Victor G. Ganzha, Evgenii V. Vorozhtsov

Completion of Linear Differential Systems to Involution

In this paper we generalize the involutive methods and algorithms have been devised for polynomial ideals to differential ones generated by a finite set of linear differential polynomials in the differential polynomial ring over a zero characteristic differential field. Given a ranking of derivative terms and an involutive division, we formulate the involutivity conditions which form a basis of involutive algorithms. We present an algorithm for computation of a minimal involutive differential basis. Its correctness and termination hold for any constructive and noetherian involutive division. As two important applications we consider posing of an initial value problem for a linear differential system providing uniqueness of its solution and Lie symmetry analysis of nonlinear differential equations. In particular, this allows to determine the structure of arbitrariness in general solution of linear systems and thereby to find the size of symmetry group.

Vladimir P. Gerdt

Constrained Hamiltonian Systems and Gröbner Bases

In this paper we consider finite-dimensional constrained Hamiltonian systems of polynomial type. In order to compute the complete set of constraints and separate them into the first and second classes we apply the modern algorithmic methods of commutative algebra based on the use of Gröbner bases. As it is shown, this makes the classical Dirac method fully algorithmic. The underlying algorithm implemented in Maple is presented and some illustrative examples are given.

Vladimir P. Gerdt, Soso A. Gogilidze

Construction of Involutive Monomial Sets for Different Involutive Divisions

We consider computational and implementation issues for the completion of monomial sets to involution using different involutive divisions. Every of these divisions produces its own completion procedure. For the polynomial case it yields an involutive basis which is a special form of a Gröbner basis, generally redundant. We also compare our Mathematica implementation of Janet division to an implementation in C.

Vladimir P. Gerdt, Vladimir V. Kornyak, Matthias Berth, Günter Czichowski

Partial Inverse Heuristic for the Approximate Solution of Non-linear Equations

(Invited Talk)

We show how to generate many fix-point iterators of the form x i +1= F(x i ) which could solve a given non-linear equation. In particular, these iterators tend to have good global convergence, and we show examples whereby obscure solutions can be discovered. This methods are only suitable for computer algebra systems, where the equations to be solved can be manipulated in symbolic form. Also, a systematic method for finding most or all solutions to nonlinear equations that have multiple solutions is described. The most successful iterators are constructed to have a small number of occurrences of x i in F. We use grouping of polynomial terms and expressions in x, ex and In x using known inverse relations to obtain better iterators. Each iterator is tried in a limited way, in the expectation that at least one of them will succeed. This heuristic shows a very good behaviour in most cases, in particular when the answer involves extreme ranges.

Gaston H. Gonnet, Allan Bonadio

Computing Cocycles on Simplicial Complexes

In this note, working in the context of simplicial sets [17], we give a detailed study of the complexity for computing chain level Steenrod squares [20,21], in terms of the number of face operators required. This analysis is based on the combinatorial formulation given in [5]. As an application, we give here an algorithm for computing cup-i products over integers on a simplicial complex at chain level.

Rocío González-Díaz, Pedro Real

Bifurcations of Maps in the Software Package CONTENT

The qualitative behaviour of iterates of a map can be very complicated. One approach to these phenomena starts with the simplest situation, the case where the map has a fixed point. Under parameter variations, the fixed point typically moves until a bifurcation value is reached and one of three possible more complex phenomena is encountered. These are fold, flip and Neimark - Sacker bifurcations; they are called codimension one phenomena because they generically appear in problems with one free parameter.The software package CONTENT (continuation environment) combines numerical methods (integration, numerical continuation etcetera) with symbolic methods (e.g. symbolic derivatives) and allows (among other things) to numerically continue fixed points and to detect, compute and continue fold points, flip points and Neimark - Sacker points. To the best of our knowledge content is the only softwaxe that allows to detect and compute all codimension two points on such curves, including strong resonances and degenerate Neimark - Sacker bifurcations. The paper provides details on defining systems and test functions implemented in content for these purposes.We show the power of the software by studying the behaviour of an electromechanical device that exhibits a complicated bifurcation behaviour, the so - called Sommerfeld’s efFect. In this example the map is defined by the time integration of a three - dimensional dynamical system over a fixed time interval.

W. Govaerts, Yu A. Kuznetsov, B. Sijnave

Extending a Java Based Framework for Scientific Software-Components

A prototypical framework, which was used for building software components for symbolic computation, is extended as follows. First, we demonstrate that the server components can be accessed from other frameworks for collaborative scientific computing, too. Specifically, we incorporate access from the PROGRESS system. Second, we discuss several design issues that arise when encapsulating existing systems as services into the framework. Many of these issues are of a general nature but become relevant in our effort to incorporate the invariant package of MAS and the quantifier elimination package qepcad into our framework.

Manfred Göbel, Wolfgang Küchlin, Stefan Müller, Andreas Weber⋆

Symbolic-numeric Investigations for Stability Analysis of Satellite Systems

An approach for the symbolic-numeric stability analysis of satellite systems correspondingly to structure of gravitational, aerodynamical, gyrostatic and static forces is presented. The satellite system is described by Lagrange differential equations. The equations of motion form a closed system, for which the Jacobi Integral is valid. Stationary solutions of these equations are defined by the multivariate polynomial system.The algebraic polynomial system has been investigated with the help of born the numerical and symbolic analysis. The symbolic investigation was made by means of Resultant and Grobner Basis methods[7].The stationary motions of a satellite sub ject to gravitational, aerodynamical, gyrostatic and static torques is governed by nine algebraic equations with nine parameters - pro jections of torques vectors onto the frame attached to the body of the satellite. The classes of stationary solutions of these algebraic equations have been found With the help of computer algebra system Maple [S] by applying the Resultant, the Groebner Basis and Factorization methods.Computation of the surfaces of algebraic equations real solutions is performed numerically by the gradient method. The number of grid points was chosen as a function of curvature. As a result of this work 3D boundary surfaces with equal number of equilibrium positions of a satellite are constructed.On the base of this methods the problem of defining the equilibriuYn positions of a satellite in a circular orbit under the influence of external torques was solved [2],[6], [9],[10],[11].The stability of equilibrium positions are analyzed numerically with Lyapunov’s second method. The Jacobi Integral as Lyapunov’s function is used.

Sergey A. Gutnik

Quantization by Presentation: The Nambu-Goto String in 1+3 Dimensions

In a cautious approach to the quantization of the Nambu-Goto string in 1+3 dimensions, correspondence is required for the algebra of observables only. With the help of a presentation of this Poisson algebra the associative quantum algebra may be constructed. A defining relation of the Poisson algebra determines one of the quantum algebra up to a finite number of terms of higher order in ħ. These terms are severely restricted when one requires the correct classical limit for all the relations implied by the defining ones. The ideal generated by the associative defining relations has been computed up to degree five with the help of Mathematica routines specially designed to make use of the so(3) representation space structure of the algebra. These computations strongly support the consistency of the correspondence postulate for the algebra of observables.

Gerrit Handrich

One Algorithm of Finding Solutions for the Systems with First Integrals

We discuss the algorithm for finding the relative and absolute stability positions and invariant manifolds of systems of differential equations. The proposed approach is based on the analysis of stationary sets of first integrals of the system. Example applications of this algorithm to mechanical problems are presented. In some stages of solution the tools of computer algebra are used.

Valentin Irtegov, Tatyana Titorenko

Cohomology of Lie Superalgebras of Hamiltonian Vector Fields: Computer Analysis

In this paper we present the results of computation of cohomology for some Lie (super)algebras of Hamiltonian vector fields and related algebras. At present, the full cohomology rings for these algebras are not known even for the low dimensional vector fields. The partial “experimental” results may give some hints for solution of the whole problem. The computations have been carried out with the help of recently written program in C language. Some of the presented results are new.

Vladimir V. Kornyak

Computer Algebra Tools in Construction of Renormgroup Symmetries

The method of constructing renormgroup symmetries with perturbative group analysis is reviewed and the use of symbolic packages in finding these symmetries is discussed in application to nonlinear Schrödinger equation. New solutions of boundary value problems for the system of nonlinear optics equations are presented.

Vladimir F. Kovalev

Where Numerics Can Benefit from Computer Algebra in Finite Difference Modelling of Fluid Flows

We present several examples of the use of computer algebra systems as a tool in the development and implementation of finite difference schemes modelling fluid flows. Computer algebra is particularly important for transformations of partial differential equations, posedness and stability analysis. Automatic code generation provides a reliable way to process large implicit linear or non-linear finite difference schemes into Fortran code solving them.

Richard Liska, Burton Wendroff

Effectively Computation of Some Radicals of Submodules of Free Modules

A new characterization of the radical of a submodule is presented and it is applied to give a computational method for calculating some radicals of submodules of free modules. Two examples of this method are also included.

Agustín Marcelo, Félix Marcelo, César Rodríguez

Computations on Character Tables of Association Schemes

Association schemes are combinatorial objects that allow us solving problems in several branches of mathematics. They have been used in the study of permutation groups and graphs and also in the design of experiments. The author get in touch with this topic through Delsarte’s thesis on association schemes and coding theory [6]. All the information of an association scheme can be derived from its table of characters. In this paper we show some techniques for computing the character table and also derive other properties from it, such as the condition for the scheme to be P-polynomial etc. We also work out some characteristics of metrics which are constant over the relations of the scheme such as Lloyd polynomials. The computations are based on the relation between an association scheme and its Bose-Mesner algebra.

Edgar Martínez-Moro

Investigation of Subgroup Embeddings by the Computer Algebra Package GAP

We describe algorithms for testing subgroups of a finite group for subgroup embedding properties. The latter include abnormality, pronormality, para-normality, their weak analogies, the subnormalizer condition and weak normality (in the sense of K.H.Müller). The algorithms are based on the usage of tables of marks (Burnside matrices). This tool allows us to carry out calculations with integers instead of computations with group elements. Our implementation within the computer algebra package GAP is also considered. The respective codes are written in the GAP language. Two long-standing problems in the area were solved with the help of these programs. The respective counterexamples are described.

V. I. Mysovskikh

An Investigation into Stability of Conservative Mechanical Systems Using Analytic Calculations

The report is devoted to Beletsky’s problem of obtaining slightest sufficient conditions for stability of “cylindrical” precessions of dynamically symmetrical satellite. Investigation was carried out dependending on values of motion parameter α and inertia momenta A,B,C(A = B) with respect to principal central axes of a satellite.

M. A. Novickov

Superfast Computations with Singular Structured Matrices over Abstract Fields

An effective superfast divide-and-conquer algorithm of Morf, 1980, and Bitmead and Anderson, 1980, computes the solution x = T−1 b to a strongly non- singular Toeplitz or Toeplitz-like linear system Tx = b. The algorithm is called superfast because it runs in almost linear time, versus cubic time of Gaussian elimination and quadratic time of some known faster solutions. Recently, the algorithm was extended to similar superfast computations with n x n Cauchy and Cauchy-like matrices. We use randomization to extend this approach to superfast solution of a singular Cauchy-like linear system of equations over any field of constants and, futhermore, to superfast computation of the rank of a Cauchy-like matrix and a basis for its null space. We also ameliorate slightly Kaltofen’s superfast solver of singular Toeplitz-like linear systems in an arbitrary field. The algorithms can be easily extended to similar computations with singular Hankel-like and Vandermonde-like matrices. The applications include rational and polynomial interpolation, Pade approximation and decoding Reed-Solomon and algebraic-geometric codes.

V. Y. Pan, A. Zheng, M. Abu Tabanjeh, Z. Chen, S. Providence

From Modeling to Simulation with Symbolic Computation: An Application to Design and Performance Analysis of Complex Optical Devices

The design and performance analysis of a complex optical instrument, such as an interferometer, leads to the study of a very large model: a set of equations that relate the parameters of the instrument. Problems are then to compute performances with respect to some fixed parameters or to find optimal values of parameters with respect to some required performances. Due to complexity of the models involved, there is no cpmletely automatic method to solve these problems. However, Computer Algebra, through the CIRCE package presented in this paper, can be an invaluable tool to define and store models, to express some parameters or performances as functions of other parameters, and then to generate dedicated numerical simulation.

Yves A. Papegay

A Symbolic Numeric Environment for Analyzing Measurement Data in Multi-Model Settings (Extended Abstract)

We have built a complete system which allows the analysis of measurement data arising from scientific experiments. Within the system, it is possible to fit parameter-dependent curves to given data points numerically in order to obtain estimates of experimental quantities. The system provides moreover a convenient tool to test different theoretical models against a given experiment: We use the computer algebra system Maple not only as a graphical interface to visualize the data but mainly as a symbolic calculator to investigate and to implement solutions of the underlying theory. The system has been used successfully in a project with researchers from the department of chemistry.

Christoph Richard, Andreas Weber

Geometric Interpretation of Strong Inconsistency in Knowledge Based Systems

This paper distinguishes between two different kinds of inconsistency of rule-based Knowledge Based Systems (KBSs) constructed on multi-valued logics, which we have denoted “weak inconsistency” and “strong inconsistency”, respectively. While “weak inconsistency” is the inconsistency studied in the verification related references listed at the end of the article, “strong inconsistency” is introduced in this paper. “Strong inconsistency” is a particular case of “weak inconsistency”. An interesting interpretation in terms of polynomial ideals and (discrete) algebraic varieties is provided. Finally, an implementation in the Computer Algebra System (CAS) Maple is included. This implementation provides both a visualization of “strong inconsistency” and symbolic results (directly handling truth tables).

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

Indices and Solvability for General Systems of Differential Equations

(Invited Talk)

We consider general systems of ordinary and partial differential equations from a geometric point of view. This leads to simple interpretations of various index concepts introduced for differential algebraic equations. Especially, we obtain natural generalisations of these concepts to partial differential equations.

Werner M. Seiler

Decomposing Systems of Polynomial Equations

The notion of sequential decomposition of k-correspondences is introduced. This is motivated by the use of functional decompositions of polynomials, rational functions, and rational mappings for the simplification of the solution of certain systems of polynomial equations. Sequential decompositions of k-correspondences can be used to express the “generic solution” of certain kinds of polynomial equations in a simpler way, in some sense. It is shown how Gröbner basis techniques can be applied to compute this kind of decompositions effectively.

Rainer Steinwandt

Polynomials with Coefficients of Limited Accuracy

In Scientific Computing, data often have a limited accuracy. With polynomial modelling functions, this affects the meaningful accuracy of their zeros. We derive constructive criteria for judging the validity of approximate zeros relative to inaccuracies in the polynomials.

Hans J. Stetter

Localization of Roots of a Polynomial not Represented in Canonical Form

The root isolation problem for the polynomial equation not represented in the canonical form can sometimes be solved without evaluation of the coefficients of powers of the variable. We investigate the approach based on representing first the equation in the equivalent determinantal (Hankel or block Hankel) form, and employing then Hermite’s root separation method. We illustrate this for the problems of eigenvalues localization, estimation of sensitivity of the roots of the parameter dependent polynomial and nonlinear optimization.

Alexei Yu Uteshev

On Normalization of a Class of Polynomial Hamiltonians: From Ordinary and Inverse Points of View

In this paper, the normalization of a class of polynomial Hamiltonians based on the symbolic computing is disscussed from both the ordinary and the inverse direction-points of view. The truncated three-particle Toda linear chain(3- TLC) and the regularized system of a planar hydrogen atom with the linear Stark effect (HLSE) are taken as examples to demonstrate the symbolic-computational approach to the ordinary and the inverse normalization problems.

Yoshio Uwano, Nikolai Chekanov, Vitaly Rostovtsev, Sergue Vinitsky

On Multivariate Polynomial Decomposition

In this paper, we discuss the decomposition problem for multivariate polynomials and the possible definitions of decomposable/indecomposable polynomial. We also present a polynomial time algorithm for decomposing multivariate polynomials over an arbitrary field.

Joachim von zur Gathen, Jaime Gutierrez, Rosario Rubio

Complexity of Monomial Evaluations and Duality

We give a matrix representation for the problem of joint evaluation of monomial sets. This approach leads to a relation between the problem of evaluation of m monomials in p variables and p monomials in m variables. A relation between multiplicative complexities of these dual problems is given.

Nikolai N. Vassiliev

On the Simplification of Nonlinear DAE Systems in Analog Circuit Design

The behavior of nonlinear analog circuits is described by a set of differential algebraic equations (DAE). In this paper we present a symbolic simplification algorithm for such DAE systems which generates an approximative system. Besides the mathematical background we explain several local and global simplification techniques that axe applied to the system. Each modification step is controlled by an error calculation. To achieve a maximum number of simplifications and to avoid unnecessary modifications an optimized order, the so called ranking, is needed. We will present two different ranking methods and will show the results on an example.

Tim Wichmann, Ralf Popp, Walter Hartong, Lars Hedrich

Symbolic Analysis of Computational Algorithms with SYDNA

The paper presents SYDNA (SYmbolic-Driven Numerical Analysis), a computer algebra library dedicated to the analysis and synthesis of numerical algorithms. The system provides a framework for expressing different parts of complex problem solving procedures. Numerical algorithms are specified using a higher- order functor system, which maximizes code reusability. Efficient implementations are generated by fully instantiating the functors at compile-time, optimizing specifications through program transformations and code generation.

Radu Zapotinschi

Backmatter

Weitere Informationen