9-TH WORKSHOP ON COMPUTER ALGEBRA

DUBNA 2005

May 17-18, 2005, Dubna

 

The 9-th two-day workshop on Computer Algebra will be held on May 17-18, 2005. This worshop is a traditional joint meeting of Moscow computer algebra seminar 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 Compuer 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 11.

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.

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.

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

 

  Symbolic Solutions of Inhomogeneous Linear Ordinary Differential Equations
    Anna Ryabenko (Dorodnicyn Computing Centre RAS)
     
   

For a given l.o.d.e. Ly(x)=f(x) with polynomial coefficients and a rational right hand side f(x), we determine a set of points x=a such that there can be a power series solution y(x)=\sum_{n=0}^\infty c_n (x-a)^n with hypergeometric coefficients, i.e. c_{n+1}/c_n is a rational in n for large enought n.

 

  Inverse Problem for Discrete Elliptic Equation with Prescribed Symmetry Conditions
    S.I.Serdyukova (JINR, Dubna)
     
   

We developed a numerical and analytical algorithm for reconstructing the two-dimensional discrete elliptic equation of a part of spectrum and prescribed symmetry conditions. The right problem is solved in rectangle M \times N with zero-boundary conditions. If given symmetry conditions are satisfied the eigenfunctions can be prolonged from the rectangle on the whole plain with reserving continuity of the first derivatives. The problem is reduced to reconstruction of a symmetric five-diagonal matrix. We proved that when prescribed symmetry conditions are satisfied the considered block three-diagonal matrix and all its blocks are persymmery. Such matrix has L<MN different elements and can be reconstructed of L given eigenvalues. Matrix elements and lacking MN-L eigenvalues are determined by solving a polynomial system constituted of the Vieta relations for 4 multipliers of the characteristic polynomial of the matrix. Numerical experiments were produced. The polynomial systems were derived and solved by using CAS REDUCE.

 

  On Regular and Logarithmic Solutions of Ordinary Linear Differential Systems
    Sergei A. Abramov (Dorodnicyn Computing Center RAS), Manuel Bronstein (INRIA, France), Denis E. Khmelnov (Dorodnicyn Computing Center RAS)
     
   

We present an approach to find all the regular solutions of systems of linear ordinary differential equations using the EG'-desingularization algorithm as an auxiliary tool. A similar approach to find all the solutions with entries in C(z)[log(z)] is presented as well, together with a new hybrid method for constructing the denominator of rational and logarithmic solutions.

 

  NORMAL FORMS AND INTEGRABILITY OF ODE SYSTEMS
    A.D. Bruno (Keldysh Institute of Applied Mathematics), V.F. Edneral (Moscow State University after Lomonosov)
     
   

We consider a special case of the Euler--Poisson system, describing the motion of a rigid body with a fixed point. It is the autonomous ODE system of sixth order with one parameter. For the stationary points, we compute the resonant normal form for two low level resonances of the system using a program based on the MATHEMATICA package. Our results show that in cases of the existence of an additional first integral of the system its normal form is degenerate. So we assume that the integrability of a system can be checked through its normal form.

 

  On Factorization of Some Classes of Nonlinear Differential Equations
    L.M.Berkovich (Samara State University)
     
   

The current paper considers some classes of nonlinear differential equations, that allows exact linearization and also different methods of factorization.

 

  On Euler-Imshenetsky-Darboux Transformation of Second-order Linear Differential Equations
   

L.M.Berkovich, S.A.Evlakhov (Samara State University)

     
   

On the basis of Euler-Imshenetsky-Darboux the sequence of the equations, integrable in terms of an input equation, constructs.

 

  Testing the Membership in Differential Ideals Generated by a Polynomial Composition
    M.V. Kondratieva, A.I. Zobnin (MSU, Dept. of Mechanics and Mathematics)
     
   

The membership problem posed for finitely generated differential ideals in ordinary differential polynomial rings is still open. It is solved just in several important cases, including the case of radical ideals, the case of isobaric ideals and the case of known finite or parametric differential standard basis. The authors suggested the process that builds such a basis with respect to certain orderings and always terminates if the latter is finite. The method that reduces testing the membership in saturated ideals generated by a polynomial composition to simpler solvable problems is described.

 

  THE ALGORITHMS OF SYMBOLIC CALCULATIONS IN STUDYING SOME PROBLEMS OF COSMIC DYNAMICS
  ` A.Prokopenya (Brest Technical University, Belarus)
     
   

Studying some models of cosmic dynamics, for example, elliptic restricted many-body problem or satellite motion along the elliptic orbit in the central field, we have to solve a number of problems where bulky symbolic calculations are involved. Obtaining the equations of motion, a search of their stationary solutions and studying their stability are just some examples of such problems. In the present paper we discuss the algorithms of symbolic calculations we use for solving the problems. The examples of their implementation in codes of the system Mathematica are shown.

 

  The Proof of Non-existence of Elliptic Solutions of the Cubic Complex Ginzburg--Landau Equation
    S.Yu. Vernov (Skobeltsyn Institute of Nuclear Physics of MSU)
     
   

The cubic complex one-dimensional Ginzburg-Landau equation is considered. Using the Hone's method, based on the use of the Laurent-series solutions and the residue theorem, we have proved that this equation has neither elliptic standing wave nor elliptic travelling wave solutions. This result amplifies Hone's result, that the Ginzburg-Landau equation has no elliptic travelling wave solutions. The proof has been reduced to solve a system of algebraic equations, that allows to automatize calculations.


  Parallel Integration
   

M. Bronstein (INRIA, http://www-sop.inria.fr/cafe/Manuel.Bronstein/pmint/ )

   


   

Parallel integration, is an attempt to avoid the recursive nature of the Risch integration algorithm by considering the function to integrate as a multivariate rational function in the various terms appearing in it. We present new theorems that refine the classical Liouville theorem on elementary integration in the case of purely transcendental integrands. By predicting precisely the new functions that can appear in the integral, they yield a very simple parallel integration method that is applicable also to nonelementary and non-monomial functions, such as the Lambert W and the Bessel functions. The method is so simple that an experimental Maple program takes less than 100 lines of code.

 

  Solution Spaces of H-Systems and the Ore-Sato Theorem
    S.A. Abramov (Dorodnicyn Computing Centre RAS), M. Petkovsek (University of Ljubljana, Slovenia)
     
   

An $H$-system is a system of first-order linear homogeneous difference equations for a single unknown function (sequence) $T(n_1,\dots,n_d)$. The coefficients of an $H$-system are in $\cs [n_1,\dots ,n_d]$. We consider two spaces of solutions of $H$-systems: the space $V_1$ of solutions defined everywhere on $\zs ^d$, and the space $V_2$ of solutions that are defined at all nonsingular points of $\zs ^d$. We investigate the dimensions of the spaces $V_1$, $V_2$, and prove for the case $d=1$ that if the equation has singularities then $1 \le \dim V_1 < \dim V_2 < \infty$, and for any integers $s, t$ such that $1 \le s < t$ there exists an equation with $\dim V_1 = s$ and $\dim V_2 = t$ (the case where there is no singularity is trivial: $\dim V_1=\dim V_2 =1$). Then we show that in the case $d>1$ the possibilities are even richer: for any $s,t\in \zs_+ \cup \{\infty\}$ there exists an $H$-system with $\dim V_1 =s$ and $\dim V_2=t$.

Additionally we revisit the Sato-Ore theorem and show that, contrary to some interpretations in the literature, this theorem does not imply that any solution of an $H$-system is of the form
$$
R(n_1,\dots ,n_d) \frac{\prod_{i=1}^p \Gamma(a_{i1}
n_1 +\dots + a_{id}n_d+ \alpha_i)} {\prod_{j=1}^q \Gamma(b_{j1}
n_1 +\dots + b_{jd}n_d+ \beta_j)} \,u_1^{n_1}\cdots u_d^{n_d},
$$
where $R\in \cs(x_1,\dots ,x_d)$, $a_{ik},b_{jk} \in \zs$, and $\alpha_i,\beta _j \in \cs$. We give an appropriate formulation of the Ore-Sato theorem on possible form of solutions of $H$-systems.


  Gosper's Algorithm, Accurate Summation, and Discrete Newton-Leibniz Formula
    S.A. Abramov (Dorodnicyn Computing Centre RAS), M. Petkovsek (University of Ljubljana, Slovenia)
     
   

Sufficient conditions are given for validity of the discrete Newton-Leibniz formula when the indefinite sum is obtained either by Gosper's algorithm or by Accurate Summation algorithm. It is shown that sometimes a polynomial can be factored from the summand in such a way that the safe summation range is increased.

 

  Applications of BK Method of LPDOs Factorization
    Shemyakova Katya (1.RISC, Austria; 2. MSU, Dept. of Mechanics and Mathematics)
     
   

The problem of factorization of LPDOs is well-known and a lot of deep results are already obtained (Tsarev and its bib). However, mostly the results were not constructive and play the role of pure existence theorems.
The last year the first algorithm for factorization of LPDO of arbitrary order is presented (Grigoriev, Schwarz). Immediately BK-algorithm appeared which is based on the ideas of the first one but in another approach.
In resent paper we study problems related with the factorization of LPDO such that the number of factorizations and the commutativity of factors, capabilities of the method itself.
There is also the first version of MAPLE-based implementation of BK-algorithm. The code is not presented but all the results starting with Sect.3 up to the end are obtained partially with its help.

 

  Optimal Algorithm to Compute Essential Values of Hypergeometric Type Functions
    Alexey Bogolubsky (MSU, Dept. of Mechanics and Mathematics), Sergey Skorokhodov (Dorodnicyn Computing Centre RAS)
     
   

The new method is proposed to compute the values of big set of functions at their singular points. Method is based on using of complete asymptotical expansions by Hurwitz functions \zeta(s, \alpha) for efficient summation of Dirichlet-type series. Application of the method for computation of practically important function p_F_p-1 ([a]; [b]; 1) is being considered in detail; the comparison with existing methods and their program realizations has been carried out. One of the real challenges is to make efficient choice of \alpha parameter (which is influencing convergence speed greatly); to do it, one must solve strongly nonlinear optimization problem. Computer analytical calculations play key role on both stages of developing and usage of the method. Besides, stochastic approach is also applied efficiently: genetic alghorithm is used to solve one of the subproblems. The whole of the methods developed allows to achieve significant perfomance increase in comparison with traditional techniques.

 

  Analysis of the Solution Component Stability of Linear Differential or Recurrent Equations System with Maple
    G.V. Plotnikov (Dept. of Computational Mathematics and Cybernetics, MSU)
     
   

The complex of the MAPLE-procedures based on Abramov-Bronstein's algorithm is described. This complex allows to consider components of the solution of the linear differential or recurrent equations system (to examine only a part of unknowns). Application of this algorithm in stability of solution components is also analyzed. Cases of constant and variable coefficients are examined.

 

  Experimental Study of Efficiency of Involutive Criteria
    V.P. Gerdt, D.A. Yanovich (JINR, Dubna)
     
   

In this paper we present results of computer experiments to study effectiveness of involutive criteria for avoiding some useless prolongations in construction of polynomial Janet bases. These bases are typical representative of involutive bases. Our experimental study shows that the role of criteria in the involutive approach is definitely weaker than that in Buchberger's algorithm.


  Symbolic Algorithm for Decomposition of Evolution Operator for Time-Dependent Schroedinger Equation
    V.P. Gerdt, A.A. Gusev, V.A. Rostovtsev, T.V. Tupikova, S.I. Vinitsky (JINR, Dubna), Y. Uwano (Hakodate University, Japan)
     
   

An symbolic algorithm based on unitary evolution operator decomposition to generate a multi-layer implicit schemes for solving the time dependent Schroedinger equation is elaborated. In framework of the algorithm a gauge transformation for extraction of symmetric operators for construction chonomical evolution schemes is realised also. The efficiency of the generated schemes is demonstrated on some integrable models.

 

  CONSTRUCTIVITY OF INVOLUTIVE DIVISIONS
    Alexander Semenov (MSU, Dept. of Mechanics and Mathematics)
     
   

Constructivity of involutive divisions plays a significant role in the theory of involutive bases, as this property is sufficient for existence of the minimal involutive basis of an arbitrary polynomial ideal
The contribution contains new examples of constructive and non-constructive pairwise involutive divisions.

 

  Analysis Methods of Multiple Eigenvalues of Spheroidal Wave Functions
    Skorokhodov S.L. (Dorodnicyn Computing Centre RAS), Khristoforov D.V. (MSU, Dept. of Mechanics and Mathematics)
     
   

Spheroidal wave functions are eigenfunctions of special differential operator of second order. They play an important role in many applied problems of diffraction, astrophysics, etc.
When the spheroid slenderness parameter $c$ is real or pure imaginary, the numerable set of different real eigenvalues $\lambda_n(c)$ corresponds to different spheroidal functions. Otherwise, when the differential operator is not self-adjoint, the values of $\lambda_n(c)$ can coincide. This case originates in the complex plane $c$ the singular points $c_b$ --- square-root branch points of eigenvalues.
Several modern methods are proposed for the structure of these singularities analysis. By means of effective symbolic evaluations the explicit power series expansions $\lambda_n=\lambda_n(c)$ were obtained and the character of singularities on the boundary of convergence disk was studied. The strong cancellation of digits appearing during $c_b$ evalution was overcome. Application of Pad\`e approximants and its generalization --- Hermite-Pade approximants -- allowed to compute branch points $c_b$ and eigenvalues $\lambda_n(c_b)$ with high precision and computation speed.

 

  Discrete Relations On Abstract Simplicial Complexes
    V. V. Kornyak (JINR, Dubna)
     
   

A system of discrete relations is, on the one hand, generalization of a cellular automaton, or, on the other hand, a set-theoretic analog of a system of polynomial equations. Methods of investigation of systems of discrete relations based on set-theoretic and topological constructions are considered. The proposed approach is implemented as a C program. The results of application of the approach to
some binary cellular automata are presented. In the binary case a cellular automaton can be represented as a system of polynomial relations. The standard tool for investigation of polynomial relations is the Groebner basis method. We compare our approach with this method.

 

  Symbolic-numeric program for solving two-dimensional Schroedinger equation
    I.N.Belyaeva, N.A. Chekanov (Belgorod State University, Belgorod), A.A. Gusev, V.A. Rostovtsev (JINR, Dubna), Yu.A.Ukolov (Belgorod State University, Belgorod), Y. Uwano (Hakodate University, Hakodate, Japan) and S.I. Vinitsky (JINR, Dubna)
   

 

   

The symbolic-numeric program for solving of the two-dimensional Schroedinger equation. The rresponding algorithm of this program using a conventional pseudocode is described too. As example, the energy spectrum and wave functions for generalized Henon-Heiles Hamiltonian were obtained.

 

  Weak-admissible Monomial Orderings and the Universal Groebner Base
    N.N.Vasiliev (PDMI RAS, St.Petersburg )
     
   

We consider non admissible monomial orderings which are only adjusted to usual division of monomials. We suggest some ways to define Groebner bases for such kind of orderings. We prove also the finiteness of universal base of an ideal defined for all weak admissible orderings.

 

rw