10-TH WORKSHOP ON COMPUTER ALGEBRA

DUBNA 2006

May 23-24, 2006, Dubna

Programme (Rus)

The 10-th two-day workshop on Computer Algebra will be held on May 23-24, 2006. This workshop is a traditional joint meeting of The Seminar on Computer Algebra of Moscow State University with the seminar on computational and applied mathematics of the Laboratory of Information Technologies of the Joint Institute for Nuclear Research. It is the continuation of a series of workshops which started in 1997 by Computer Science Faculty of MSU, Skobeltsyn Institute of Nuclear Physics of MSU and Joint Institute for Nuclear Research. The workshop is conceived with the purpose of presenting topics of current interest and providing a stimulating environment for scientific discussion on new developments in computer algebra.

The participation will take place BY REQUESTS only. Participants have to fill the following forms (including abstracts and personal data) in Russian and English (see bellow). The requests should be sent to Alla Bogolubskaya (abogol at jinr.ru), NOT LATER than May 15.

The duration of reports is 20 mins including discussion. Invited 30 mins reports will take place also. Participants who plan to visit Dubna for one day only should inform Alla Bogolubskaya about preferable date of the visit.

Current hotel prices now are 745 rub/night - a single room, and 480 rub/night - a single room in (1+2 block), and 405 rub/night - a place in double room and 250 rub. - a place on a campus.

The transport timetable is at the site: http://www.dubna.ru/transport.php

Most interesting reports will be published (after a review treatment) in "Programmirovanie" Journal. The full version of papers (better in Russian) should be passed to Sergei Abramov in during of the seminar (NOT LATER!) in printed form (as a paper) AND as a file in PostScript or PDF format.

 

Please, spread this information as wide as possible.

First Name: _____________________

Second Name: ___________________

Family Name: ____________________

Affiliation: _______________________

Position: ________________________

Abstract (including the title and a list of authors but without a list of references).

 

 

LIST OF ABSTRACTS

 

  On the Summation of Hypergeometric Sequences
    S.A.Abramov (Computing Centre of RAS)
     
   

We consider hypergeometric sequences, i.e., sequences which satisfy a first order linear homogeneous recurrence equation with relatively prime polynomial coefficients. A necessary and sufficient condition is proposed for validity of the discrete Newton-Leibniz formula when there exists a primitive in the form of a hypergeometric sequence (which can be defined, e.g., by Gosper's algorithm almost for all integer values of the argument).

 

  Implementation of F4 Algorithm in CAS Axiom
    Baratov R.A., Pankratiev E.V. (Department of Mechanics and Mathematics, MSU)
     
   

Algorithm F4 proposed by Faugere is one of the most efficient methods for determining Groebner bases of polynomial ideals. Three implementations of this algorithm are known including an implementation in CAS Maple. CAS Axiom is at present the most powerful free system of computer algebra. In the talk, an implementation of F4 algorithm in this system is described.

 

  A program for evaluation of spectrum and wave functions of C2V symmetric 2D Schroedinger equation
    I.N. Belyaeva, S.I. Vinitsky, A.A. Gusev (SCAR JINR), A.N. Makarenko, V.A. Rostovtsev, and N.A. Chekanov
     
   

The symbolic-numeric algorithm for solving the two-dimensional Schroedinger equation with C2V invariant hamiltonian by the self-consistent basis method is presented. For this hamiltonian with potential energy surface having two local minimuma and one saddle point the energy levels and corresponded wave functions are calculated.

 

  KUMMER-LIOUVILLE TRANSFORMATION AND FACTORIZATION OF LINEAR DIFFERENTIAL OPERATORS
    L.M.Berkovich (Samara, Samara State University)
     
   

The most known methods of n-th order linear differential operators factorizations are based on turning off linear differential operator of the first order by left or by right. By the way, the "root" of the factorization satisfies the general (n-1)th order Riccati equation of the 1st or the 2nd kind. Factorization of the important class of linear differential equations, that can be reduced by the Kummer-Liouville transformation to equations with constant coefficients, are considered in the present article

 

  INTEGRATING OF NONLINEAR AUTONOMOUS DIFFERENTIAL EQUATIONS, THAT PERMITS EXACT LINEARIZATION
    L.M.Berkovich, S.A.Yevlakhov (Samara, Samara State University)
     
   

Using factorization and exact linearization methods, authors have implemented the algorithm for solving nonlinear autonomous differential equations of the 2nd order. The algorithm allows to find out both general solutions and one-parametric families of partial solutions.


  Analytical methods in theory of gravitating superdense configurations with realistic state equation
    E.V.Bespalko, S.A. Miheev (Tver State University), I.V.Puzinin (JINR, Dubna), V.P.Tsvetkov (Tver State University)
     
   

Algorithm of symbolic computing was made up for solution hydrostatic equilibrium equation of stationary rotating gravitating superdense configurations with use state equations of nuclear substance in forms of Bete-Jonson, Raid, Openheimer-Volkov.It has been shown existence of bifurcation points, in which there is a branch of asymmetric decisions concerning an axis of rotation for distribution of density. It is carried out analytical research of decisions near to these points. As a result the problem about bifurcation point was reduced to a question on existence of real decisions in physical area of a cubic parabola.

 

  New approach to evaluation of entire functions of a wide class
    Alexey Bogolubsky (Department of Mechanics and Mathematics, MSU) , Sergey Skorokhodov (Computing Centre of RAS)
     
   

We consider the class of entire functions which satisfy linear differential equations of arbitrary order, and the problem of evaluating these functions in case of large absolute value of the argument. Solution of this problem is often complicated by the presence of essential singularity at $z=\infty$ point, which leads to catastrophical cancellation of meaningful digits. New highly efficient method of overcoming this difficulty is proposed, based on the usage of symbolic analysis of the series coefficients relation and their inverse summation. Application of the method is demonstrated in detail on the complex problem of generalized hypergeometric function $_pF_q({\bf a, b}; z), q \ge p$ evaluation and investigation of its zeros localization.

 

  Search of Additional Integrals by the Normal Form Method
    V.F.Edneral (Moscow State University)
     
   

The report illustrates a use of a necessary condition of existence of additional first integrals for the special case of the Euler-Poisson system of equations at fixed resonances 1:2 and 1:3. The condition is formulated in the lowest terms of a resonant normal form of the system.

 

  The History of Symbolic Manipulation and it's Applications in Mechanics
    G.B.Efimov (Keldysh Institute of Applied Mathematics), M.V.Grosheva (Institute of Mechanics MSU)
     
   

The monographs of M.V. Grosheva, G.B. Efimov, V.A. Samsonov. “The History of Symbolic Manipulation and it's Applications in Mechanics” is presented. The book is devoted to the history of development of computer symbolic algebraic manipulations (SAM) and analytical computational systems (computer algebra) in Russia The main stages of elaboration and applications of soviet SAM are considered, the leaders of each stage are mentioned, the main con­ferences and seminars are listed. The attention is paid to the experience of SAM usage in the areas of learning and education. The classification of problems to be solved and systems for their solution is done. To demonstrate the variety of SAM applications, especially in mechanics, a cycle of computational experiment is presented. Numerous investigations on SAM usage in mechanics are considered. The oldest computational center, KIAM, was used as an example to demonstrate the way of SAM development in Soviet Union. The attention is paid, to the most part, to the early history, the last works are presented as some examples.

 

  LINDA: Maple-program for finding classical solutions of Duffing's equation and for calculation of spectrum it's quantum analogue
    Florinsky V. V., Chekanov N. A. (Belgorod State University)
     
   

Semiclassical quantization of Duffing's equation is discussed. The formula for energy spectrum of small-perturbed oscillator is obtained. The computer program solving this problem for any order of small parameter is worked out.

 

  On Selection Strategy for Non-multiplicative Prolongations in Computing Janet Bases
    V.P.Gerdt (Laboratory of Information Technologies, Joint Institute for Nuclear Research), Yu.A.Blinkov (Department of Mathematics and Mechanics, Saratov State University)
     
   

We consider three different modifications of our involutive algorithm for computing polynomial Janet bases. These modifications are related to degree compatible monomial orders and specify selection strategies for non-multiplicative prolongations. By using the standard data base of polynomial benchmarks for Groebner bases software we compare the modifications and confront them with Magma that implements Faugere's F4 algorithm.

 

  Fibonacci-Padovan Sequences and MacWilliams Transform Matrices
    N. Gogin, A. Myllari (University of Turku, Turku, Finland)
     
   

MacWilliams transform that is closely related to the classic MacWilliams formula for generating functions of the weight spectra of dual codes is well-known tool in problems of the algebraic coding theory and algebraic combinatorics. From other side, (integer) matrices of these transforms have many remarkable algebraic-combinatorical properties. Here, somehow unexpected connection between these matrices and classic integer sequences of Fibonacci, Lucas and Padovan is established: namely, here is proved that a summarizing along some naturally selected planes in the “pyramid” constructed of these matrices leads to a new integer sequence that proves to be a convolution of Fibonacci numbers and signed Padovan numbers. This convolution in its turn can be expressed linearly by Lucas and Padovan sequences.

 

  Bounding orders in Rosenfeld-Groebner algorithm
    Marina Kondratieva, Oleg Golubitsky, Marc Moreno Maza, and Alexey Ovchinnikov ( Moscow State University and North Carolina State University )
     
   

Even for ordinary differential equations the Rosenfeld-Groebner algorithm is of high experimental complexity. But theoretical complexity estimates are not obtained yet. We provide a bound for orders of polynomials in this algorithm which is a way to approach the complexity.

 

  Finiteness Issues on Differential Standard Bases
    M.V. Kondratieva, E.V. Pankratiev, D. Trushin and A.I. Zobnin (Department of Mechanics and Mathematics, Moscow State University)
     
   

Finite differential standard bases of differential ideals allow one to solve algorithmically a lot of problems concerning differential equations. They are generalizations of Groebner bases for polynomial ideals. Unfortunately, not every ideal has finite differential standard basis. It is interesting to know when it is finite. Recently a finiteness criterion has been obtained for some class of orderings and the case of one differential indeterminate: there exists a finite differential standard basis iff the ideal contains a quasi-linear polynomial (i.e., a polynomial that is solved for its leading derivative). We consider the case of ideals generated by one differential polynomial of the first order. In this case, the finiteness of standard bases is closely connected to the property of the ideal to be radical.

 

  Symmetric Cellular Automata
    V.V.Kornyak (Laboratory of Information Technologies, Joint Institute for Nuclear Research)
     
   

We consider a class of cellular automata with permutationally invariant local rules acting on symmetric lattices. We demonstrate that in the two-state case such local rules are nothing but generalization of the Game of Life rules. Taking into account the invariance with respect to renaming states allows to reduce further the number of possible local rules. We consider also algorithmic approaches to study dynamics of cellular automata with high symmetry.


  Recursive parallelization for symbolic-numerical algorithms
    G.I.Malaschonok, Y.D.Valeev (Tambov State University)
     
   

The scheme for parallelization of symbolic-numerical algorithms is proposed. It is based on sequential recursive algorithm. It would be useful for cluster computational systems. Some variants of such scheme are discussed.

 

  Fast algorithm for computation of multipole matrix elements
    V.Yu.Papshev, S.Yu.Slavynov
     
   

Recursive algorithm for computation of multipole matrix elements with Legendre polynomials based on Hilbert transform of equation for products of Legendre polynomials proposed. Special cases for computations of Clebsch-Gordon coefficients are discussed as well as other possible generalizations of the method.

 

  Symbolic algorithms for partial stability analysis of linear differential systems
    G.V.Plontikov ( Moscow State University, department of Computational Mathematics and Cybernetics )
     
   

In the report realizations of symbolic algorithms for partial stability analysis of linear differential systems with constant coefficients in Maple are considered. In partial stability problem we examine stability of system with respect to a subset of unknowns. For partial stability analysis Abramov-Bronstein algorithm realization was made. The algorithm constructs a new linear system of differential or difference equations with constant or variable coefficients, which includes only specified solution components to initial system and some of their derivatives. Realization of Linare-Shipare criterion based on Rauth-Hurwitz criterion was made for characteristic polynomial stability analysis of new linear differential system. Special attention was paid for differential systems, containing parameters: add-ins were created for considered algorithms to exclude incorrect solutions.

 

  On homogeneous Zeilberger's recurrences
    S. P. Polyakov (Computing Centre of RAS)
     
   

The existence of proper terms that have homogeneous Zeilberger's recurrences with telescoping operators of arbitrarily large order is proved. The correctness of Zeilberger's algorithm in the homogeneous case is proved. An extension of the algorithm for computing such recurrences more efficiently is proposed.

 

  Symbolic computation of the characteristic exponents for the linear system of differential equations with periodic coefficients with infinite determinant method
    A.N.Prokopenya ( Brest State Technical University )
     
   

In the present paper we show that the infinite determinant method may be effectively used for symbolic computing the characteristic exponents for the linear system of differential equations with periodic coefficients. The corresponding algorithm of calculations is developed and is implemented with the computer algebra system Mathematica. As an example we calculate the characteristic exponents in the case of the fourth order system of differential equations determining the disturbed motion in the neighborhood of the Lagrange triangular solutions in the elliptic restricted three-body problem. The corresponding characteristic exponents are found in the form of power series in a small parameter with accuracy up to the sixth order.

 

  NEW RESULTS ON INVOLUTIVE DIVISION CONSTRUCTIVITY
    A.S. Semenov (Moscow State University)
     
   

In the framework of the report possible generalizations of Janet involutive division and the problem of minimial involutive basis existence will be considered. The core of the report is new examples of constructive and non-constructive involutive divisions.

 

  Inverse Problem for Discrete Two-Dimensional Schrödinger Equation in Square
    S.I.Serdyukova ( JINR, Dubna)
     
   

Discrete potantial for discrete two-dimensional Schrödinger equation can be reconstructed from a part of spectrum and prescribed symmetry conditions for the basic eigenfunctions. Discrete potential together with the lacking eigenvalues are found by solving a polynomial system constructed and solved by using the REDUCE system. Iterations realized in the Numeric package converge with proper initial data only. Given eigenvalues are perturbed original eigenvalues corresponding to zero discrete potential. So it is natural to use original values for the lacking eigenvalues as the initial data. But in the case of square there are a lot of multiple eigenvalues among the original ones. The right implimentation of Numeric package is impossible in presence of multiple initial data. In this work a special algorithm for colculating the discrete potential for the discrete two-dimensional Schrödinger equation in square is suggested.

 

  Obstacles to Factorizations of Linear Partial Differential Operators. General Case
    E.S.Shemyakova, F. Winkler ( Research Institute for Symbolic Computations (RISC), J.Kepler University, Linz, Austria)
     
   

For a linear partial differential operator with separable symbol one could prove that every factorization of the symbol can be extended to at most one factorization of the operator [Grigoriev, Schwarz (2004), ISSAC]. Given any such operator $L$ and a specified factorization of its symbol, we define the associated ring of obstacles to the factorization of $L$ extending the specified factorization of the symbol. We derive some facts about obstacles and give an exhaustive enumeration of obstacles for operators of order two and three. The paper is a generalization of results of [E. Shemyakova, F. Winkler (2006), Proc. TC'06, Conference in Honor of Jean Della Dora. ], where we investigate the problem for factorizations into two factors. This work was supported by Austrian Science Foundation (FWF) under the project SFB F013/F1304.

 

  High-accurate method for solution of the Orr-Sommerfeld stability equation
    S.L.Skorokhodov ( Computing Centre of RAS )
     
   

An effective method for computing eigenfunctions and eigenvalues of the Orr-Sommerfeld equation for stability analysis of Poiseuille flow is developed. The method is based on the system of expansions for the eigenfunctions, on the using of Pade-approximants and on a smooth matching of the expansions. Large values of the Reynolds number are studied -- this case is correspond to singular perturbation of the equation. Effective symbolic evaluations are used for computing the coefficients of expansions, for studying of convergence and acceleration of the convergence.

 

  Convex monomial orderings, multidimensioanal Young diagrams and Groebner bases
    Vasiliev N.N. (Steklov Institute of mathematics at St.Petersburg, RAS)
     
   

We define a class of convex monomial orderings, which includes all admissible orderings. The classical Groebner base theory is generalized to the case of all convex orderings. We prove, that each monomial ideal has an uniq Groebner base relative to convex monomial ordering and each polynomial has an uniniq canonical normal form. We describe also connections between the Groebner base theory and combinatorics of multidimensional Yound diagrams.

 

  A Symbolic-numerical Algorithm for Evaluating Matrix Elements of the Parametric Eigenvalue Problem
    S.I. Vinitsky, V.P. Gerdt, A.A. Gusev, M.S. Kaschiev (IMI ), V.A.Rostovtsev, V.N. Samoylov,
T.V. Tupikova, and O. Chuluunbaatar
     
   

A symbolic-numerical algorithm for evaluating the matrix elements of the parametric eigenvalue problem. Calculating the oblate angular spheroidal functions and corresponding eigenvalues which depend on the parameter, their derivatives with respect to the parameter and matrix elements is considered in the both spherical and cylindrical coordinates. The efficiency and accuracy of the algorithm and of the numerical scheme derived are confirmed by computations of eigenenergies, eigenfunctions and matrix elements and their comparison with known data and asymptotic expansions at small and large values of parameter.

 

  Computer modelling of hydrogen-like atoms in quantum mechanics with non-negative distribution function
    A.V.Zorin, L.A.Sevastianov, N.P.Tretyakov (Peoples' Friendship University of Russia, Moscow)
     
   

A symbolic algorithm based on the quantum mechanics with non-negative probability distribution function (quantum mechanics of Kuryshkin - QMK) to generate operators and to calculate energy levels for hydrogen-like atoms is elaborated. In framework of the algorithm an original package to calculate necessary functions, such as hydrogen wave functions, Sturm functions and their Fourier-transforms, Clebsh-Gordon coefficients etc is realized also. Operators of observables are calculated according to the QMK quantization rule. Energy levels of hydrogen-like atoms are calculeted and compared with experimental data retrieved from the NIST Atomic Spectra Database Levels Data.