Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

Fast Matrix Computation of Subresultant Polynomial Remainder Sequences

We present an improved (faster) variant of the matrix-triangularization subresultant prs method for the computation of a greatest common divisor of two polynomials A and B (of degrees dA and dB, respectively) along with their polynomial remainder sequence [1]. The computing time of our fast method is 0(n2+ßlog ∥C∥2), for standard arithmetic and 0(((n1+ß+n3 log ∥C∥)(log n+ log ∥C∥)2) for the Chinese remainder method, where n = dA + dB, ∥C∥ is the maximal coefficient of the two polynomials and the best known ß < 2.356. By comparison, the computing time of the old version is 0(n5 log ∥C∥2 ).Our improvement is based on the work of Malaschonok [12] who proposed a new, recursive method for the solution of systems of linear equations in integral domains with complexity Onß over the integers (same as the complexity of matrix multiplication).In this paper we present an overview of the two methods mentioned above and show how they are combined into a fast matrix method for computing polynomial remainder sequences. An example is also presented to clarify the concepts.

Alkiviadis G. Akritas, Gennadi I. Malaschonok

About Simultaneous Representation of Two Natural Numbers by a Sum of Three Primes

I. A. Allakov, M. I. Israilov

On a Description of Irreducible Component in the Set of Nilpotent Leibniz Algebras Containing the Algebra of Maximal Nilindex, and Classification of Graded Filiform Leibniz Algebras

This paper is devoted to the study of Leibniz algebras introduced by Loday in [1-2] as an analogue of zero ”noncommutative” Lie algebras. We define the notion of zero-filiform Leibniz algebras and study their properties. There is a notion of p-filiform Lie algebras for p≥ 1 [3], which loses a sense in case p = 0, since Lie algebra has at least two generators. In the case of Leibniz algebras for p = 0 this notion substantial, and thereby, introduction of a zero-filiform algebra is quite natural. We also investigate the complex non-Lie filiform Leibniz algebras. In particular, we give some equivalent conditions of filiformity of Leibniz algebras and describe complex Leibniz algebras, which were graded in natural way.

Sh. A. Ayupov, B. A. Omirov

Application of Computer Algebra in Problems on Stabilization of Gyroscopic Systems

The paper discusses some problems of stabilization of potential systems at the expense of gyroscopic forces. The algorithms described are employed in the software ”STABILITY” [1]. This software is based on the computer algebra system ”Mathematica” [2] and is designed to investigate stability and stabilization of mechanical systems in symbolic and numeric-symbolic forms.

Banshchikov Andrey, Bourlakova Larissa

Implementing Computational Services Based on OpenMath

OpenMath is a standard for representing mathematical objects. This report describes our experiences in implementing a facility for OpenMath-based symbolic computation services to be made available over the Internet. Services can be implemented in REDUCE, Mathematica or Maple, they are accessible via a Java client or using shell scripts. Our experimental client/server system is publicly available under an Open Source license. We address some issues in the development of OpenMath-based services such as implementing Phrasebooks and different choices of input syntax.

Matthias Berth, Frank-Michael Moser, Arrigo Triulzi

Group Classification of the Navier-Stokes Equations for Compressible Viscous Heat-Conducting Gas

We consider the problems of using computer algebra systems for group classification of partial differential equations. The presence of arbitrary elements makes the solution of determining equations more difficult. It offers necessity for active human control over this process by using dialog regime. Methods of computer algebra for problems of group classification are illustrated by the example of a system of the Navier-Stokes equations for compressible viscous heat-conducting gas. This system has five arbitrary elements. The solution of the problem of finding equivalence transfonpations is presented. The group classification is carried out in some particular cases.

Vasiliy V. Bublik

Plotting Functions and Singularities with Maple and Java on a Component-based Web Architecture

In this paper we present a client/server plotting system for analytical functions that features a reliable computation and visualization of singularities. The system is part of a Web-based course on Mathematics for first-year students at the University of Tübingen. In an educational context where students of the first or second semesters are addressed, it is crucial that the plotted graphs are correct, since the students may not yet be able to interpret faulty graphs in an appropriate way. The singularities are computed by a computer algebra system which is transparently accessible through a Web interface. Our implementation of the singularity computations is more complete than the existing ones that we found as parts of various algebra systems. The rendering of the graphs and the visualization of the singularities is performed by a Java applet which can be executed within almost all of the current Javaaware Web browsers. No additional software, like plug-ins or proprietary browser extensions, has to be installed on the client machine.

Dieter Bühler, Corinne Chauvin, Wolfgang Küchlin

Stable Self-Oscillatory Regimes in Volterra Models of Three Populations

For two models of the quantitative dynamics of a predatorprey system such as the generalized three-dimensional Lotka-Voltterra models the existence of the stable self-oscillatory regimes of behavior is investigated basing on qualitative and bifurcation theories as well as on computer experiment.

T. E. Buriev, V. E. Ergashev

Computing “Small” 1-Homological Models for Commutative Differential Graded Algebras

We use homological perturbation machinery specific for the algebra category [13] to give an algorithm for computing the differential structure of a small I-homological model for commutative differential graded algebras (briefly, CDGAs). The complexity of the procedure is studied and a computer package in Mathematica is described for determining such models.

V. Álvarez, J. A. Armario, M. D. Frau, R. González-Díaz, M. J. Jiménez, P. Real, B. Silva

Effective computation of algebra of derivations of Lie algebras

By the software Mathematica 3.0 we design a program that allows calculate the algebra of derivations of any Lie algebra. As an example we use this program in a special class of Lie algebras, (n - 4)-filiform Lie algebras of dimension n.

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

An Integration and Reduction for Ordinary Non Linear Differential Equations Library

In this paper, we review the algorithmic work done in the last years by the Grenoble Computer Algebra team in the domain of differential equations. We organize in a logic manner the studies developed in different directions and we show how the modules obtained from these studies could cooperate in order to build IRONDEL, a Library for the Integration and Reduction of Ordinary Non linear Differential Equations.

J. Della Dora, F. Richard-Jung

Complexity of Derivatives Generated by Symbolic Differentiation

The computational solution of many mathematical problems involves derivatives. Programs for computing derivatives may be (1) hand-Coded, (2) set up via function calls and divided differences, or (3) obtained using symbolic differentiation. In practice, the divided differences approach is still the standard technique. But in many cases, derivatives can be computed cheaper and more accurately by symbolic differentiation. In this paper we investigate the complexity of algorithms for computing derivatives of rational functions. In particular, we deal with the forward mode and the reverse mode of symbolic differentiation. We discuss bounds on the amount of work within the described algorithms in terms of rational operations.

Herbert Fischer, Hubert Warsitz

An Assessment of the Efficiency of Computer Algebra Systems in the Solution of Scientific Computing Problems

Computer algebra systems (CASs) have become an important tool for the solution of scientific computing problems. With the increasing number of general purpose CASs, there is now a need for an assessment of the efficiency of these systems. We discuss some peculiarities associated with the analysis of CPU time efficiency in CASs, and then present results from three specific systems (Maple Vr5, Mathematica 4.0 and MuPAD 1.4) on a sample of intermediate size problems. These results show that Maple Vr5 is generally the speediest on our examples. Finally, we formulate some requirements for developing a comprehensive test suite for analyzing the efficiency of CASs.

Victor G. Ganzha, Evgenii V. Vorozhtsov, Michael Wester

On the Relation between Pommaret and Janet Bases

In this paper the relation between Pommaret and Janet bases of polynomial ideals is studied. It is proved that if an ideal has a finite Pommaret basis then the latter is a minimal Janet basis. An improved version of the related algorithm for computation of Janet bases, initially designed by Zharkov, is described. For an ideal with a finite Pommaret basis, the algorithm computes this basis. Otherwise, the algorithm computes a Janet basis which need not be minimal. The obtained results are generalized to linear differential ideals.

Vladimir P. Gerdt

An (Asymptotic) Error Bound for the Evaluation of Polynomials at Roots

Given is a univariate polynomial $$F(X) = {X^n} - {\sigma _1}{X^{n - 1}} + \ldots + {( - 1)^{n - 1}}{\sigma _{n - 1}}X + {( - 1)^n}{\sigma _n} \in \left[ X \right]$$ and a “poor” numerical solution α1, ‖ , αn ∈ ℂ of F(X) = 0 such that 1 ≤ ∣αi - xi∣ ≤ δ ∈ ℝ and F(xi) = 0 for 1 ≤ i ≤ n. We show that $$O\left( {{2^{n - 1}}n! \cdot {\delta ^{{\textstyle{{n(n - 1)} \over 2}}}}} \right)$$ is an (asymptotic) error bound for the evaluation of an arbitrary but fixed multivariate polynomial f ∈ ℂ[x1,...,x n ] at the n-tuple (α1,...,αn) instead of the n-tuple of the roots (x1,...,x n ),and that for some polynomials the (asymptotic) error bound is Ω Keywords. Analysis of algorithms, data structures, rewriting techniques, evaluation of polynomials, roots, error bounds $$\Omega \left( {n! \cdot {\delta ^{{\textstyle{{n(n - 1)} \over 2}}}}} \right)$$.

Manfred Göbel

Three Remarks on Comprehensive Gröbner and SAGBI Bases

This note presents new complexity results for the comprehensive Gröbner bases (CGB) algorithm in the special case of one main variable and two polynomials, a general remark about CGB for parameterized binomial ideals, and it introduces the concept of comprehensive SAGBI bases together with a first application in invariant theory. Keywords. Comprehensive Gröbner bases, parameterized binomial ideals, comprehensive SAGBI bases, algorithmic invariant theory, permutation groups.

Manfred G-bel, Patrick Maier

Computing the Cylindrical Algebraic Decomposition Adapted to a Set of Equalities

The Cylindrical Algebraic Decomposition algorithm, in its projection phase, proceeds by eliminating one variable from a given set of polynomials P by means of the computation of the principal subresultant coefficients of a certain set of pairs of polynomials in P (including their derivatives and reducta). Since this method produces usually a big number of polynomials, and since the process must be iterated several times, any improvement in the projection phase would convey to dramatically speed up the efficiency of the Cylindrical Algebraic Decomposition algorithm.The purpose of this paper is to present two approaches allowing, in some cases, to simplify the projection phase in the Cylindrical Algebraic Decomposition algorithm when some of the involved polynomials are prescribed to have a particular sign behaviour.

Neila Gonzalez-Campos, Laureano Gonzalez-Vega

Symbolic Algorithms of Algebraic Perturbation Theory for a Hydrogen Atom: the Stark Effect

We present symbolic algorithms realized in REDUCE 3.6 for evaluation of eigenvalues and eigenfunctions of the 3-D and 2-D hydrogen atoms in weak uniform electric fields. Algebraic perturbation theory schemes are built up using the irreducible representations of the dynamical symmetry algebras so(4,2) and so(3,2), which are connected by the tilting transformations with ‘wave functions of the 3-D and 2-D hydrogen atoms. Such a construction is based on a representation of the unperturbed Hamiltonian and polynomial perturbation operator via generators of the algebra. It was done without an assumption on the separation of independent variables of the perturbation operator and without using fractional powers of the parabolic quantum numbers in recurrence relations determining the effects of generators of the algebra on the corresponding basis. The efficiency of the proposed schemes and algorithms is demonstrated by calculations of coefficients of the Stark effect perturbations series for the hydrogen atoms with arbitrary parabolic quantum numbers.

Alexander Gusev, Valentin Samoilov, Vitaly Rostovtsev, Sergue Vinitsky

CADECOM: Computer Algebra software for functional DECOMposition

In this paper we present the Maple package Cadecom which is designed for performing computations in rational function fields. The main objects that Cadecom deals with are multivariate rational functions over any computable field, and the key tool are the functional decomposition algorithms. The functional decomposition problem has many applications in computer science, engineering (CAGD), pure mathematics or robotics. We motivate the interest of this program package by presenting applications on computing roots, simplifying sine-cosine equations, integrating rational functions, computing subfields, computing Gröbner bases and reparametrizing parametric curves. We also include a short overview of the package from the Maple system point of view.

Jaime Gutierrez, Rosario Rubio

Computeralgebra and the Systematic Construction of Finite Unlabeled Structures

This review is concerned with mathematical structures that can be defined as equivalence classes on finite sets. The method used is to replace the equivalence relation by a finite group action and then to apply all what is known about such actions, i.e. to apply a mixture of quite general methods, taken from combinatorics as well as from algebra. For this purpose group actions will be introduced, enumerative methods will be reported, but the main emphasize is put on the constructive aspects, the generation of orbits representatives, and several applications of these methods, in particular to graph theory, design theory, coding theory and to mathematical chemistry.These methods have been successfully implemented in various computeralgebra packages like MOLGEN (for the generation of molecular graphs and applications to molecular structure elucidation) as well as in DISCRETA (for the evaluation of combinatorial designs and linear codes as well as other finite discrete structures).Finally we shall discuss actions on posets, semigroups, lattices, where the action is compatible with the order of the lattice or the composition of the semigroup.

Adalbert Kerber

Heat Invariant E 2 for Nonminimal Operator on Manifolds with Torsion

Computer algebra methods are applied to the investigation of spectral asymptotics of elliptic differential operators on curved manifolds with torsion and in the presence of a gauge field. In this paper we present complete expressions for the second coefficient (E2) in the heat kernel expansion for nonminimal operators on manifolds with nonzero torsion. The expressions were computed for the general case of manifolds of arbitrary dimension n and also for the most important for E2 case n = 2. The calculations have been carried out on PC with the help of a program written in C.

Vladimir V. Kornyak

Computer Algebra for Automated Performance Modeling of Fortran Programs

Time complexity of sequential programs or segments of parallel programs can be estimated using the dynamic frequency of statements and their execution time. The execution time of single statements can be estimated by counting basic operations. The present paper deals with a method of determining the global dynamic frequency of statements by transient analysis of a Markov model. For defining the model automatically and solving the related equations, we use AUGUR which is a research tool for performance modeling of Fortran programs. While static program analysis and model generation are implemented by routine compile techniques, AUGUR uses MAPLE for evaluating expressions, defining transition matrices, and transient analysis. Routines of LAPACK are considered to demonstrate the achievable results.

Hermann Mierendorff, Helmut Schwamborn

A Parallel Symbolic-Numerical Approach to Algebraic Curve Plotting

We describe a parallel hybrid symbolic-numerical solution to the problem of reliably plotting a plane algebraic curve. The original sequential program is implemented in the software library CASA on the basis of the computer algebra system Maple. The new parallel version is based on Distributed Maple, a distributed programming extension written in Java. We describe the mathematical foundations of the algorithm, give sequential algorithmic improvements and discuss our parallelization approach.

Christian Mittermaier, Wolfgang Schreiner, Franz Winkler

Parametric Analysis for a Nonlinear System

The paper suggests an investigation of one system of differential equations with parameter carried out on the basis of the author’s theorem on signdefiniteness of nonuniform structures [1,2].

M. A. Novickov

Extended Splicing System and Semigroup of Dominoes

Tom Head[5] introduced the novel idea of splicing system as a generative device for representing the string restructuring that takes place during the interactions of linear biopolymers in the presence of precisely specified enzymatic activities and thus established a new relationship between formal language theory and the study of informational macromolecules. In this paper, we discuss the relationship existing between the extended splicing system and the semigroup of dominoes, a special algebraic structure acting on linked strings.

Pethuru Raj, Naohiro Ishii

Newton Polyhedra and the Reversible System of Ordinary Differential Equations

We investigate a reversible system of fourth-order ODEs by using the method of Newton polyhedron. We discuss the program for IBM PC, which computes the Newton polyhedron of the system under study and all of its corresponding objects. The results of the program runs are presented as a table of correspondences.

A. Soleev, I. Yarmukhamedov

Condition Analysis of Overdetermined Algebraic Problems

In analogy to numerical linear algebra, the evolving numerical polynomial algebra studies the modifications of classical polynomial algebra necessary to accomodate inaccurate data and inexact computation. A standard part of this endeavor is a condition analysis of the problems to be solved, i.e. an assessment of the sensitivity of their results with respect to variations in their data. In this paper, we extend this condition analysis to overdetermined problems, like greatest common divisors, multivariate factorization etc. Here we must consider the fact that results exist only for data from restricted low-dimensional domains. The discontinuous dependence of the results on the data, however, is “smoothed” by their limited accuracy so that a condition analysis becomes meaningful. As usual, the condition numbers indicate the accuracy with which results may be specified.

Hans J. Stetter

An Algebraic Approach to Offsetting and Blending of Solids

We propose to broaden the framework of CSG to a representation of solids as boolean combinations of polynomial equations and inequalities describing regular closed semialgebraic sets of points in 3-space. As intermediate results of our operations we admit arbitrary semialgebraic sets. This allows to overcome well-known problems with the computation of blendings via offsets. The operations commonly encountered in solid modelers plus offsetting and constant radius blending can be reduced to quantifier elimination problems, which can be solved by exact symbolic methods. We discuss the general properties of such offsets and blendings for arbitrary regular closed semialgebraic sets in real n-space. Our computational examples demonstrate the capabilities of the REDLOG package for the discussed operations on solids within our framework.

Thomas Sturm

Application of Computer Algebra Methods to Some Problems of Theoretical and Applied Celestial Mechanics

Applications of computer algebra methods to some problems of dynamical astronomy are described. It is shown, how with the help of computer algebra it is possible to solve different important problems of applied celestial mechanics: in particular, to develop efficient analytical and semianalytical theories of motion of celestial bodies, to construct efficient algorithms for computation of some special functions of celestial mechanics, to solve some problems of asteroid dynamics. Possibilities to use computer-algebraic methods for efficient solution of other topical problems of dynamics of Hamiltonian systems are discussed.

Akmal Vakhidov

Computing the Frobenius Normal Form of a Sparse Matrix

We probabilistically determine the Frobenius form and thus the characteristic polynomial of a matrix $$A \in {^{n \times n}}$$ by O(μnlog(n)) multiplications of A by vectors and 0 (μn2 log2 (n)loglog(n)) arithmetic operations in the field F . The parameter μ.L is the number of distinct invariant factors of A, it is less than $$3{{\sqrt n } \mathord{\left/ {\vphantom {{\sqrt n } 2}} \right. \kern-\nulldelimiterspace} 2}$$in the worst case. The method requires O(n) storage space in addition to that needed for the matrix A.

Gilles Villard

Lessons Learned from Using CORBA for Components in Scientific Computing

The use of component architectures to solve the problem of reuse and interoperability in scientific computing has been investigated by various research groups during the last years. Moreover, architectures for Internet accessible mathematical services have been proposed. In this paper we give a brief abstract requirements analysis with respect to these problems and show that there is an existing technology that solves most of the requirements. The Common Object Request Broker Architecture (CORBA) provides a component framework that can be used for Internet accessible mathematical services and also for the efficient reuse of medium grained size functionality. We give some examples on the use of CORBA with respect to both applications. We provide measurement data which show that components of a granularity of less than {100} ms can be reused with an acceptibly small overhead.

Andreas Weber, Gabor Simon, Wolfgang Küchlin, Jörg Hoss

Deciding Linear-Transcendental Problems

We present a decision procedure for linear-transcendental problems formalized in a suitable first-order language. The problems are formalized by formulas with arbitrary quantified linear variables and a block of quantifiers with respect to mixed linear-transcendental variables. Variables may range both over the reals and over the integers. The transcendental functions admitted are characterized axiomatically; they include the exponential function applied to a polynomial, hyperbolic functions and their inverses, and the arcustangent. The decision procedure is explicit and implementable; it is based on mixed real-integer linear elimination, the symbolic test point method, elementary analysis, and Lindemann’s theorem. As a byproduct we obtain sample solutions for existential formulas and a qualitative description of the connected components of the satisfaction set wrt. a mixed linear-transcendental variable. Potential applications include reachability problems for linear differential systems.

Volker Weispfenning

Backmatter

Weitere Informationen