Seminar on Computer Algebra, CMC faculty of MSU & CCAS - Archive / Cеминар «Компьютерная алгебра» факультета ВМК МГУ и ВЦ РАН - Архив

Recent meetings / Недавние заседания

Slides

Заседание семинара было посвящено 85-летию В.А.Ростовцева.

А.А.Гусев (ЛИТ ОИЯИ, Дубна)

Метод конечных элементов с интерполяционными полиномами Эрмита для решения эллиптических краевых задач

Аннотация

Предложены новые вычислительные схемы метода конечных элементов высокого порядка точности решения краевых задач для эллиптического уравнения в частных производных, сохраняющие непрерывность приближенного решения и его производных в ограниченной области многомерного евклидова пространства, заданной в виде многогранника. Сформулирован и реализован в системе MAPLE алгоритм для вычисления в аналитическом виде кусочно-непрерывного базиса из интерполяционных полиномов Эрмита нескольких переменных, обеспечивающий на границах треугольных конечных элементов непрерывность не только приближенного решения, но и его производных до заданного порядка. Эффективность и порядок точности вычислительных схем, алгоритмов и программ, реализованных в среде MAPLE-FORTRAN, демонстрируется эталонными расчетами краевых задач на собственные значения для треугольной мембраны, гиперкуба, моделей связанных состояний тримера атомов бериллия в коллинеарной конфигурации и атома гелия.

The session of the seminar was dedicated to the 85-th birthday of V.A.Rostovtsev.

A.A.Gusev (LIT JINR, Dubna)

Finite Element Method with Hermite Interpolation Polynomials for Solving Elliptic Boundary Value Problems

Abstract

A new computational schemes of the finite element method of a high order of accuracy for solving boundary value problems for an elliptic partial differential equation that preserve the continuity of the approximate solution and the its derivatives in a bounded domain like a polygon of a multidimensional Euclidean space is proposed. Algorithm implemented in MAPLE for calculating a piecewise continuous basis of interpolation Hermite polynomials of several variables in analytical form, preserving the continuity of not only the approximate solution but also its derivatives up to a given order on the boundaries of the triangle finite elements, is formulated. The efficiency and accuracy order of the computational schemes, algorithms and programs implemented in MAPLE-FORTRAN environment are demonstrated by benchmark calculations of the boundary-value problems for the triangular membrane, the hypercube, models of the bound states of a trimer of Beryllium atoms in the linear configuration and a Helium atom.

Slides (Eferina), Slides (Velieva)

1. Е.Г.Еферина (Российский университет дружбы народов)

Реализация диаграммной техники для статистических систем в SymPy

Аннотация

При разработке методики стохастизации одношаговых процессов основное внимание было уделено получению стохастических уравнений в форме Ланжевена, поскольку данный вид наиболее привычен при построении и исследовании данного круга моделей. Однако формы уравнений в частных производных (основное кинетическое уравнение и уравнение Фоккера–Планка) могут предоставить исследователю более богатое описание модели. Для исследования данных уравнений предлагается использовать теорию возмущений в форме, реализованной в рамках квантовой теории поля. Для этого описана методика и создан аналитический программный комплекс приведения основного кинетического уравнения к операторной форме в фоковском представлении. Также программный комплекс позволяет создавать фейнмановские диаграммы и получать модельные уравнения из них. В качестве системы символьных вычислений была использована библиотека SymPy.

2. Т.Р.Велиева (Российский университет дружбы народов)

Линеаризация системы с управлением при помощи библиотеки SymPy

Аннотация

Автоколебательные режимы, возникающие в сетях передачи данных имеют негативное влияние на характеристику этих сетей. Для устранения данного явления необходимо определить зоны возникновения автоколебаний, а также определить и проанализировать их параметры. В качестве метода исследования был применён метод гармонической линеаризации. Данный метод известен из теории управления. Однако он мало известен за пределами теории управления и не применялся ранее к задачам такого типа. Метод гармонической линеаризации требует приведение модели к определенному виду. Подготовительным этапом является линеаризация модели системы с управлением. Из-за трудоёмкости задачи была использована система компьютерной алгебры SymPy. С помощью этой системы исследованы разные критерии устойчивости модели (Михайлова, Найквиста–Михайлова, Рауса–Гурвица).

1. E.G.Eferina (Peoples’ Friendship University of Russia (RUDN University))

Implementation of diagram technique for statistical systems in SymPy

Abstract

During development of various methods for randomization of one-step processes the attention was focused on obtaining the stochastic equations in the Langevin's form, since this form is most usual in the construction and study of models of one-step processes. However, the partial differential equations (master equation and the Fokker–Planck equation) can provide richer description of the model to researchers. It is proposed to use a help of perturbation theory in the framework of quantum field theory to study these equations. For this purpose a methodology is introduced and an analytical software framework is constructed to represent the main kinetic equation in the operator form in the terms of Fock representation. Additionally the developed framework allows to generate feynman diagrams and to obtain model equations using them. SymPy library is employed as a symbolic calculations engine.

2. T.R.Velieva (Peoples’ Friendship University of Russia (RUDN University))

Linearization of system with control with help of SymPy

Abstract

The self-oscillation modes arising in data transmission networks have a negative effect on the characteristics of these networks. To eliminate this phenomenon, it is necessary to determine the zones of occurrence of self-oscillations, and also to determine and analyze their parameters. As a method of investigation, the harmonic linearization method was applied. This method is known from control theory. However, it is little known outside the theory of control and has not been applied to problems of this type previously. The method of harmonic linearization requires the reduction of the model to a specific form. The preparatory stage is the linearization of the model of the system with control. Due to the complexity of the task, the computer algebra system SymPy was used. With the help of this system, various criteria for the stability of the model (Mikhailov, Nyquist-Mikhailov, Raus-Hurwitz) have been investigated.

Slides (Panferov), Extended Abstract (Abramov)

Очередное заседание семинара «Компьютерная алгебра» состоится в среду 1 марта 2017 года в 16:20, в ауд. 713 ВМК:

1. А.А.Панфёров (Факультет вычислительной математики и кибернетики МГУ; Вычислительный центр им. А.А.Дородницына ФИЦ ИУ РАН)

Сателлитные компоненты решений линейных дифференциальных систем с выделенными неизвестными

Аннотация

Пусть K - дифференциальное поле характеристики 0. Рассматривается линейная дифференциальная система S вида y'=Ay, в которой A - квадратная матрица над K порядка n и y - вектор-столбец неизвестных размера n, некоторые компоненты которого являются выделенными. Ранее была представлена концепция сателлитных неизвестных: для непустого множества выделенных неизвестных s невыделенная неизвестная y_j называется сателлитной, если j-я компонента любого решения системы S принадлежит дифференциальному расширению, порожденному K и всеми выделенными компонентами всех решений S. Также для случая, когда K представляет собой поле рациональных функций переменной x над алгебраически замкнутым полем констант, был предложен алгоритм распознавания сателлитных неизвестных. В докладе вводится понятие сателлитных неизвестных по отношению к решениям. В отличии от сателлитных неизвестных, сателлитные по отношению к решениям неизвестные не определяются выделенными компонентами сразу всех решений системы. Невыделенная неизвестная y_j называется сателлитной по отношению к решениям, если j-я компонента любого решения S принадлежит линейному пространству над K, порождённому выделенными компонентами этого решения. Также предлагается алгоритм распознавания сателлитных по отношению к решениям неизвестных и его реализация в Maple.

2. С.А.Абрамов (Вычислительный центр им. А.А.Дородницына ФИЦ ИУ РАН)

Бесконечные ряды как входные данные некоторых алгебраических процедур

Аннотация

Бесконечные ряды играют важную роль в математических исследованиях. Такие ряды могут служить исходными данными в некоторых математических задачах. Чтобы обсуждать соответствующие алгоритмы, надо условиться о представлении бесконечных рядов: входные данные алгоритма всегда являются словами специального вида в некотором алфавите. В докладе обсуждаются два возможных решения проблемы представления степенных рядов. Во-первых, рассматривается алгоритмическое представление. Для ряда пытаемся указать алгоритм, который для данного i вычисляет коэффициент при x^i (допускаются любые детерминированные алгоритмы); каждый такой алгоритм определяет некоторый конструктивный ряд. Во-вторых, рассматривается представление в усеченном, т.е. в приближенном, виде.

1. А.А.Panferov (Department of Computational Mathematics and Cybernetics, Moscow State University; Dorodnicyn Computing Centre, Federal Research Center «Computer Science and Control» of Russian Academy of Science)

Satellite components of solutions to linear differential systems with the selected unknowns

Abstract

Let K be a differential field of characteristic 0. Consider a linear differential system S of the form y'=Ay, where A is a square matrix over K of order n and y is a column vector of unknowns some components of which are selected. Earlier the concept of satellite unknowns was presented: for the nonempty set of selected unknowns s an unselected unknown y_j is called satellite unknown if the j-th component of any solution to S belongs to differential extension generated by K and all selected components of all solutions to S. Also for the case when K is the field of rational functions in x with coefficients from the algebraically closed field of constants the Satellite testing algorithm was presented. In the present work we introduce the concept of sol-satellite unknowns (satellite unknowns w.r.t. solutions). Contrary to satellite unknowns, the definition of sol-satellite unknowns does not concern selected components of all solutions at once. Some unselected unknown y_j is called sol-satellite unknown for the nonempty set of selected unknowns if the j-th component of any solution to S belongs to a linear space over K, that is generated by the selected components of this solution. We present Sol-satellite testing algorithm and its implementation in Maple.

2. S.A.Abramov (Dorodnicyn Computing Centre, Federal Research Center «Computer Science and Control» of Russian Academy of Science)

Infinite series as the input of certain algebraic procedures

Abstract

Infinite power series play an important role in mathematical studies. Those series may appear as inputs for certain mathematical problems. In order to be able to discuss the corresponding algorithms, we must agree on representation of the infinite series (algorithm inputs are always objects, represented by specific finite words in some alphabet). This talk examines two possible solutions to the problem of representation of power series. First, we consider the algorithmic representation. For each series, an algorithm is specified that, given an integer i, finds the coefficient of x^i. Any deterministic algorithms are allowed (any such algorithm defines a so called constructive series). Second, we consider a representation in an approximate form, namely, in a truncated form.

Slides (Kulyabov), Slides (Ilchenko)

1. Д.С.Кулябов (Кафедра прикладной информатики и теории вероятностей, Российский университет дружбы народов, Лаборатория информационных технологий, Объединённый институт ядерных исследований)

От Cadabra к Cadabra II – новые возможности аналитических тензорных вычислений

Аннотация

Среди свободных систем компьютерной алгебры для работы с тензорами выделяется система Cadabra. По удобству интерактивной работы она не имеет равных среди свободных систем тензорной компьютерной алгебры. Но и она не свободна от многих проблем, а именно: манипуляция только с абстрактными индексами, низкая интероперабельность с другими системами компьютерной алгебры, слабая расширяемость самой системы, устаревший пользовательский интерфейс. Однако с выходом новой версии системы – Cadabra II – эти недостатки были устранены. В докладе демонстрируются новые возможности системы Cadabra II на примере задач геометризации Максвелловской оптики.

2. Е.А.Ильченко (Тамбовский государственный университет им. Г.Р.Державина)

Динамическое децентрализованное управление распределенными вычислениями для блочно-рекурсивных алгоритмов в компьютерной алгебре

Аннотация

В докладе рассматривается одна из центральных задач параллельной компьютерной алгебры: организация параллельных вычислений для рекурсивных древовидных алгебраических алгоритмов на вычислительном кластере с распределенной памятью. Примерами таких алгоритмов являются блочный алгоритм умножения матриц, умножение матриц методом Штрассена, обращение матриц алгоритмом Шура-Штрассена, дихотомическое умножение полиномов и алгоритм Карацубы умножения полиномов. Для этих алгоритмов рассматривается несколько схем управления параллельными вычислениями, реализующих концепцию динамического децентрализованного распараллеливания алгоритмов с использованием Message Passing Interface (MPI). Сравнивается эффективность таких схем. На основе разработанной схемы динамического децентрализованного управления создана программная платформа, которая обеспечивает организацию параллельных вычислительний для этого класса алгортмов. Приводятся результаты экспериментов для случая целочисленных матриц, в которых вычисляется ядро матричного оператора и обратная матрица на кластере МВС-10П. Дается сравнительный анализ экспериментов, которые проводились для матриц с целыми коэффициентами и для матриц над конечными полями. Эксперименты демонстрируют хорошую масштабируемость параллельных программ, полученных на данной программной платформе.

1. D.S.Kulyabov (Department of Applied Probability and Informatics, RUDN University (Peoples' Friendship University of Russia), Laboratory of Information Technologies, Joint Institute for Nuclear Research)

From Cadabra to Cadabra II: towards new opportunities of analytical tensor calculus

Abstract

Among the open source computer algebra systems for tensors calculus the Cadabra is a distinguished system. By the convenience of interactive work it has no equal among the open source computer algebra systems tensor. But it is not free from many problems, namely the manipulation only with abstract indices, low interoperability with other computer algebra systems, poor scalability of the system, the outdated user interface. However, with the release of a new version of the system–Cadabra II–these drawbacks have been eliminated. The presentation demonstrates the opportunities Cadabra II system on the example of the problem of geometrization of Maxwellian optics.

2. E.A.Ilchenko (Tambov State University named after G.R.Derzhavin)

Dynamic decentralized control of distributed computing for the block-recursive algorithms in computer algebra

Abstract

We consider one of the central problem of parallel computer algebra. It's a problem of organization of parallel computations for tree-like recursive algebraic algorithms for compute cluster with distributed memory. The block algorithm of matrix multiplication, Strassen method of matrix multiplication, Schur-Strassen algorithm of matrix inversion, polynomial dichotomous multiplication and Karatsuba algorithm of polynomial multiplication are examples of such tree-like recursive algorithms. For such algorithms we suggest several schemes for management of parallel computing processes, which implement the concept of decentralized dynamic parallelization and using the Message Passing Interface (MPI). We compare the effectiveness of such schemes. A software platform was created on the basis of developed algorithms for the dynamic decentralized control scheme. This software platform provides the organization of parallel computing for such class of computer algebra algorithms. We demonstrate the results of experiments at the cluster computer MVS-10P with parallel programs for matrix inversion and for the computation of kernel of the matrix operator over the integer numbers. We give a comparative analysis of the experiments for matrices with integer coefficients and matrices over finite fields. Parallel programs, that was made using the developed program platform, demonstrate a good scalability.

Extended Abstract

И.В.Горючкина (ИПМ им. М.В. Келдыша РАН)

О свойствах формальных решений алгебраического ОДУ

Аннотация

Рассматриваются алгебраическое обыкновенное дифференциальное уравнение (ОДУ) и его формальное решение в виде хорошо упорядоченного функционального ряда довольно общего вида. Члены этого формального ряда являются решениями приближенных ОДУ (вообще говоря, алгебраических), которые выделяются из исходного уравнения с помощью многоугольника Ньютона–Брюно. Как правило, начиная с некоторого, все члены этого ряда удовлетворяют линейным неоднородным ОДУ, и к изучению этих линейных уравнений применим классический анализ. Более того, в некоторых случаях приближенные уравнения решаются явно. А в общем случае всегда можно найти их решения в виде формального ряда. В докладе будет описан алгоритм вычислений таких рядов и метод изучения их аналитических свойств. А также в качестве примера будут приведены формальные решения шестого уравнения Пенлеве и сформулированы утверждения об асимптотических и аналитических свойствах этих решений.

I.V.Goryuchkina (Keldysh Institute of Applied Mathematics of RAS)

On properties of formal solutions to an algebraic ODE

Abstract

We consider an algebraic ordinary differential equation (ODE) and its formal solution in the form of a well-ordered functional series of rather general form. The terms of this formal series are solutions of the approximate ODEs (algebraic, in general) which are selected from the initial equation by means of the Newton–Bryuno polygon. Generically, starting with some term, all the terms of this series satisfy linear inhomogeneous ODEs and therefore one can apply classical analysis for studying these linear equations. Moreover, in some particular cases the approximate equations have explicit solutions. In general case, one can always find their formal series solutions. In the talk we will describe an algorithm for calculating such series and a method of studying their analytical properties. Also there will be given examples of the sixth Painleve equation formal solutions and there will be formulated statements on asymptotical and analytical properties of these solutions.

Slides

Заседание семинара посвящено памяти Виктора Петровича Иванникова (27.02.1940-27.11.2016).

В.В.Корняк (ЛИТ ОИЯИ, Дубна)

Конструктивный взгляд на квантовую механику: модели, основанные на конечных группах

Аннотация

Траектория квантовой системы – это последовательность унитарных эволюций векторов в гильбертовом пространстве, перемежаемых наблюдениями (измерениями). Наблюдения представляют собой проекции векторов в некоторые подпространства, фиксируемые измерительными приборами. Квантовомеханическое описание можно сделать конструктивным, если заменить общую унитарную группу преобразований гильбертова пространства унитарными представлениями конечных групп. Известно, что любое линейное (= унитарное) представление конечной группы может быть реализовано как подпредставление некоторого перестановочного представления. Таким образом, квантовомеханические проблемы можно сформулировать в терминах групп перестановок. Изучение свойств моделей квантовой механики, основанных на группах перестановок, позволяет прояснить смысл ряда физических концепций. Например: можно естественным образом объяснить появление комплексных чисел в формализме квантовой механики; «принцип наименьшего действия» возникает как континуальная аппроксимация «принципа отбора наиболее вероятных траекторий». Для изучения конкретных физических задач с помощью конечных моделей мы используем системы компьютерной алгебры SymPy и Maple, системы вычислительной теории групп GAP и Magma; а также методы моделирования Монте-Карло.

The session of the seminar was dedicated to the memory of Victor Ivannikov (27.02.1940-27.11.2016).

V.V.Kornyak (LIT JINR, Dubna)

Constructive view of quantum mechanics: models based on finite groups

Abstract

The trajectory of a quantum system is a sequence of unitary evolutions of vectors in a Hilbert space, interspersed with observations (measurements). Observations are projections of vectors in some subspaces, that are specified by measuring devices. Quantum-mechanical description can be made constructive, if you replace the general group of unitary transformations of the Hilbert space by unitary representations of finite groups. It is known that any linear (= unitary) representation of a finite group can be realized as a subrepresentation of some permutation representation. Thus, quantum mechanical problems can be formulated in terms of groups of permutations. The study of the properties of quantum mechanics models based on permutation groups allows us to clarify the meaning of some physical concepts. For example: one can naturally explain the emergence of complex numbers in the formalism of quantum mechanics; «the principle of least action» arises as a continuum approximation of «the principle of selection of the most probable trajectories». To study specific physical problems with the help of the finite models, we use the computer algebra systems SymPy and Maple, the computational group theory software GAP and Magma; as well as the methods of Monte Carlo simulation.

Slides

А.Б.Батхин (ИПМ им. М.В.Келдыша РАН, МФТИ)

Глобальные параметризации одного вещественного многообразия

Аннотация

Рассматривается одно вещественное алгебраическое многообразие в вещественном трёхмерном пространстве, играющее важную роль в изучении нормализованного потока Риччи на обобщённых пространствах Уоллаха, связанных с инвариантными метриками Эйнштейна. Описывается методика получения глобального параметрического представления этого многообразия, состоящая в том, что пересечение этого многообразия с дискриминатным множеством вспомогательного кубического многочлена используется в качестве оси параметризации. Для этого используются методы теории исключений и методы компьютерной алгебры. Получено три различных параметризации многообразия, каждая из которых справедлива вне некоторых критических значений одного из параметров (А.Б.Батхин Глобальные параметризации одной вещественной алгебраической поверхности. Препринты ИПМ им. М.В.Келдыша. 2016. №76. DOI:10.20948/prepr-2016-76).

A.B.Batkhin (Keldysh Institute of Applied Mathematics, Moscow Institute of Physics and Technology)

Global parametrizations of a certain real algebraic variety

Abstract

A certain real algebraic variety in three dimensional real space is considered. This variety plays an important role in the investigation of the normalized Ricci flow on the generalized Wallach spaces. A method for constructing of the global parametric representation of this variety which consists in the fact that the intersection of this variety with discriminant set of an auxiliary cubic polynomial is used as the axis of parameterization. For this purpose the methods of elimination theory and computer algebra methods are used. A parametrization of the discriminant set of a real cubic polynomial is used. Three different parametrizations of the variety are obtained, each valid beyond some critical values of parameters.

Slides

A.A. Гусев (ЛИТ ОИЯИ, Дубна)

Алгоритмы расчета асимптотик фундаментальных решений самосопряженных систем ОДУ второго порядка

Аннотация

Рассматривается самосопряженная система ОДУ второго порядка на полуоси (или на оси) с матрицами коэффициентов, элементы которых даны в виде разложений по прямым и обратным степеням независимой переменной в окрестностях малых и больших значений независимой переменной, соответственно. Построены системы рекуррентных соотношений для расчета набора фундаментальных решений в виде асимптотических разложений по обратным степеням независимой переменной при больших значениях переменной, используя фундаментальные решения эталонного уравнения (S.I. Vinitsky et al, LNCS 5743, 334 (2009); A.A. Gusev et al, LNCS 6885, 175 (2011)). Построены системы рекуррентных соотношений для расчета набора регулярных линейно независимых решений в виде асимптотических степенных рядов при малых значений переменной (O. Chuluunbaatar et al, Comput. Phys. Commun. 179, 685 (2008)). Системы рекуррентных отношений были получены и реализованы в виде алгоритмов в системе компьютерной алгебры Maple. Вычисленные разложения применяются для формулировки граничных условий третьего рода при редукции на конечный интервал исходных краевых задач (КЗ) для систем ОДУ на полуоси (или оси). Редуцированные КЗ решаются методом конечных элементов (МКЭ) реализованного в виде программы KANTBP на языках Maple и Fortran (A.A. Gusev et al, Comput. Phys. Commun. 185, 33413 (2014)). Граница конечного интервала при больших значениях независимой переменной и число членов асимптотических разложений необходимые для достижения заданной точности решения МКЭ вычисляются используя вронскиан фундаментальных решений.

A.A. Gusev (LIT JINR, Dubna)

Algorithms for Calculations of Asymptotic Expansions of the Fundamental Solutions of the Selfadjoint Systems of ODEs of Second Order

Abstract

We consider selfadjoint system of ODEs of second order on a half axis (or an axis) with elements of the matrix coefficients given in the form of expansions over power and inverse powers of the independent variable in vicinities of small and large values of the variable, respectively. We construct systems of recurrent relations for calculating a set of the fundamental solutions in the form of asymptotic inverse power series in vicinity of large values the variable, using fundamental solutions of an appropriate etalon equation (S.I. Vinitsky et al, LNCS 5743, 334 (2009); A.A. Gusev et al, LNCS 6885, 175 (2011)). We construct systems of recurrent relations for calculating a set of the regular linear independent solutions in the form of asymptotic power series in vicinity of small values of the variable (O. Chuluunbaatar et al, Comput. Phys. Commun. 179, 685 (2008)). The systems of recurrent relations have been derived and implemented as the algorithms in CAS Maple. The calculated expansions are applied in setting of third-type boundary conditions for reduction of boundary values problems (BVPs) for the systems of the ODEs on a half axis (or an axis) in a finite interval to solve the reduced BVPs using of the finite element method (FEM) implemented as the KANTBP programs in both Maple and Fortran (A.A. Gusev et al, Comput. Phys. Commun. 185, 33413 (2014)). Boundary of the finite interval at large values of the variable and number of terms of asymptotic expansion needed to have a prescribed accuracy of the FEM solution are checked in advance by calculation of the Wronskian of the fundamental solutions.

Slides

С.В.Парамонов (МГУ, факультет вычислительной математики и кибернетики, Москва)

Алгоритмически неразрешимые задачи компьютерной алгебры, связанные с уравнениями в частных производных и разностях

Аннотация

Рассматривается ряд задач, связанных с проверкой существования решений некоторых видов для уравнений в частных производных и разностях с полиномиальными коэффициентами, и доказывается их алгоритмическая неразрешимость. Рассматриваются задачи проверки существования решений в виде рациональных функций и формальных лорановых рядов, задача проверки существования универсального знаменателя. Также доказывается неразрешимость задачи проверки единственности аналитического решения и задачи распознавания существования бесконечно дифференцируемого решения для уравнений в частных производных с граничными условиями.

S.V.Paramonov (MSU, The faculty of Computational Mathematics and Cybernetics, Moscow)

Algorithmically undecidable problems of computer algebra connected with partial differential and difference equations

Abstract

We concider the problems connected with testing the existence of solutions of certain forms for partial linear differential equations with polynomial coefficients and prove algorithmic undecidability of them. We consider the problems of testing the existence of rational function solutions and formal Laurent series solutions, the problem of testing the existence of universal denominator. Also we prove undecidability of problems of testing the uniquenes of analytic solution and of testing the existence of indefinitely differentiable solution for partial differential equation with boundary conditions.

29 июня - 2 июля 2016 года состоялся Международная конференция "Компьютерная алгебра". Конференция организована совместно Вычислительным центром им. А.А. Дородницына Федерального исследовательского центра «Информатика и управление» Российской академии наук и Российским университетом дружбы народов.

International Conference "Computer Algebra" was held in Moscow, June 29 - July 2, 2016. The conference was co-organized by Dorodnicyn Computing Center, Federal Research Center “Computer Science and Control” of Russian Academy of Sciences and Peoples’ Friendship University of Russia.

24-25 мая 2016 года состоялся традиционный совместный семинар - фактически, двухдневная конференция - с Лабораторией информационных технологий ОИЯИ (Дубна).

The traditional joint meeting with the seminar of Laboratory of Information Technologies of JINR (Dubna) was held on May 24th-25th, 2016. Essentially, this was a two-days conference.

Slides (Sadykov)

1. Г.Погудин (МГУ, механико-математический факультет)

Дифференциальный аналог теоремы о примитивном элементе.

Аннотация

В 1942 году Э. Колчин доказал следующую дифференциальную версию классической теоремы о примитивном элементе.

Пусть дифференциальное поле E конечно порождено над дифференциальным полем F, всякий элемент из E удовлетворяет алгебраическому дифференциальному уравнения с коэффицентами из F, и F содержит неконстанту. Тогда E над F можно породить одним элементом.

Вопрос о том, верна ли эта теорема, если F состоит из констант, а E содержит неконстанту, был долгое время открыт и только недавно решен положительно. В докладе будет рассказано, почему этот случай интересен, в чем его отличие от теоремы Колчина.

Кроме того, планируется изложить план доказательства с акцентом на способ найти примитивный элемент алгоритмически.

2. Т.М.Садыков (РЭУ им. Г.В.Плеханова, Москва)

Алгоритмы вычисления полиномиальных решений гипергеометрических систем уравнений в частных производных.

Аннотация

Конструктивное решение вопроса о существовании нетривиального полиномиального решения линейной системы дифференциальных уравнений в частных производных представляет собой задачу высокой вычислительной сложности. В докладе будет представлен пакет процедур в среде Wolfram Mathematica для вычисления решений гипергеометрических систем уравнений в классе многочленов Пюизо и анализа их свойств. Особое внимание будет уделено описанию тропико-геометрических свойств нулей полиномиальных решений резонансных систем уравнений.

1. G.Pogudin (MSU, faculty of mechanics and mathematics)

Differential analogue of the Primitive Element theorem.

Abstract

In 1942 E. Kolchin obtained the following differential analogue of the Primitive Element theorem.

Let E be a finitely generated differential field extension of a differential field F. Assume that every element of E satisfies an algebraic differential equation over F and F contains a nonconstant element. Then, there exists a in E such that E is generated by a and F.

It was unknown for several decades if the theorem holds in the case when F consists of constants and E contains a nonconstant element. Recently, this question was answered affirmatively. In my talk I am going to explain why this question is important and what is the difference between this problem and Kolchin’s theorem. Also I an going to sketch the proof in order to give an idea how to compute a primitive element.

2. T.M.Sadykov (Plekhanov Russian Uiversity, Moscow)

Algorithmic computation of polynomial solutions to hypergeometric systems of partial differential equations.

Abstract

To find out whether a linear system of partial differential equations admits a nontrivial polynomial solution is a task of formidable computational complexity. In the talk, a Wolfram Mathematica based package for the computation of Puiseux polynomial solutions to hypergeometric systems will be presented and used to analyze properties of such polynomials. Particular attention will be paid to the description of the tropical-geometric properties of the zero loci of solutions to resonant systems of equations.

Extended abstract

Р.Р.Гонцов (ИППИ РАН)

Теорема Майе для обобщенных степенных рядов.

Аннотация

Классическая теорема Майе (1903) описывает рост коэффициентов степенного ряда, формально удовлетворяющего ОДУ. Впоследствии она уточнялась Рамисом, Мальгранжем, Сибуйей. В докладе предлагается обобщение этой теоремы для степенного ряда с комплексными показателями степени (обобщенного степенного ряда), формально удовлетворяющего алгебраическому ОДУ. Планируется изложить некоторые примеры, а также предложить вопросы для дальнейших исследований.

R.R.Gontsov (IITP RAS)

A Maillet type theorem for generalized power series.

Abstract

The classical Maillet theorem (1903) describes the growth of the coefficients of a formal power series solution to an ODE. Subsequently, this theorem was refined by Ramis, Malgrange, Sibuya. In the talk there is proposed a generalization of this theorem for a power series with complex power exponents (a generalized power series) formally satisfying an algebraic ODE. We plan to present some examples as well as problems for further research.

Slides (Panferov), Slides (Paramonov)

1. А.А.Панфёров (МГУ, факультет вычислительной математики и кибернетики, Москва)

Линейные дифференциально-алгебраические системы с выделенными неизвестными.

Аннотация

Рассматриваются линейные дифференциально-алгебраические системы, некоторые компоненты вектора неизвестных которых являются выделенными. Предлагаемый алгоритм ExtrAB для имеющей полный ранг линейной дифференциальной системы S вида A_1y'+A_0y=0 (где A_1,A_0 - матрицы над дифференциальным полем K характеристики 0) позволяет получить нормальную дифференциальную систему S_d (т.е. систему, имеющую вид ŷ'=Aŷ), неизвестными которой является часть выделенных неизвестных исходной системы и~некоторые их производные, а также алгебраическую систему S_a, из которой остальные выделенные неизвестные линейно выражаются над K только через выделенные неизвестные, входящие в S_d. Получаемые системы S_d и S_a таковы, что при рассмотрении решений с компонентами, принадлежащими произвольному расширению исходного дифференциального поля K, проекция пространства решений исходной системы на выделенные неизвестные совпадает с проекцией на выделенные неизвестные пространства решений систем S_d, S_a. При этом если система S_d имеет решение, выделенные компоненты которого принадлежат некоторому дифференциальному расширению K, то и остальные компоненты этого решения также принадлежат этому расширению. Размеры получаемых алгоритмом ExtrAB систем S_d и S_a являются минимально возможными.

Алгоритм реализован в среде Maple.

2. С.В.Парамонов (МГУ, факультет вычислительной математики и кибернетики, Москва)

О некоторых алгоритмически неразрешимых задачах, связанных с дифференциальными уравнениями в частных производных .

Аннотация

Рассматриваются задачи распознавания существования решений некоторых видов для дифференциальных уравнений в частных производных с полиномиальными коэффициентами. Доказывается неразрешимость таких задач для решений в виде рациональных функций (этот результат справедлив и для разностых уравнений) и формальных лорановых рядов. Также доказывается неразрешимость задачи проверки единственности аналитического решения и задачи распознавания существования бесконечно дифференцируемого решения для уравнений в частных производных с граничными условиями.

1. A.A.Panferov (MSU, The faculty of Computational Mathematics and Cybernetics, Moscow)

Linear differential-algebraic systems with selected unknowns.

Abstract

We consider the linear differential-algebraic systems some components of the unknowns vector of witch are selected. We present the ExtrAB algorithm that for the full rank linear differential system S of the form A_1y'+A_0y=0 (where A_1,A_0 are matrices above the differential field K of characteristic 0) make it possible to get the normal differential system S_d (i.e. the system of the form ŷ'=Aŷ), witch unknowns are the part of the selected unknowns of the original system and some of their derivatives, and also the algebraic system S_a, by means of witch the other selected unknowns can be linearly expressed above K only through the selected unknowns from S_d. The obtained systems S_d and S_a are such that if we will regard the solutions with components from arbitrary extension of the original differential field K the projection of the initial system solution space onto the selected unknowns is the same as the projection onto the selected unknowns of the solution space of S_d, S_a. Furthermore if the system S_d has a solution, witch selected components belong to some differential extension of K, then all other components of this solution also belong to the same extension. The sizes of the systems S_d and S_a obtained by ExtrAB are as minimal as possible.

The algorithm is implemented in Maple.

2. S.V.Paramonov (MSU, The faculty of Computational Mathematics and Cybernetics, Moscow)

On some algorithmically undecidable problems connected with partial differential equations.

Abstract

We concider the problems of testing the existence of solutions of certin forms for partial linear differential equations with polynomial coefficients. We prove undecidability of such problems for rational function solutions (this result holds also for difference equations) and for formal Laurent series solutions. Also we prove undecidability of problems of testing the uniquenes of analytic solution and of testing the existence of indefinitely differentiable solution for partial differential equation with boundary conditions.

Slides (Gusev et al.), Slides (Ovchinnikov)

1. А.А.Гусев, В.П Гердт, О.Чулуунбаатар, С.И.Виницкий (ОИЯИ, Дубна)

Комплекс символьно-численных алгоритмов и программ для решения краевых задач.

Аннотация

В докладе будет дан обзор цикла работ по созданию символьно-численных алгоритмов и комплекса программ в среде Maple-Fortran для решения краевых многомерных задач шредингеровского типа в конечной области многомерного конфигурационного пространства. В качестве базового метода нами использовался метод, предложенный советским математиком, нобелевским лауреатом (1975 г.) Л.В. Канторовичем в 1934 году для численного решения краевых двумерных задач эллиптического типа сведением к системе обыкновенных дифференциальных уравнений. Представленные в докладе программы включают шесть программ, входящих в библиотеку программ журнала Computer Physics Communications и одну программу из библиотеки JINRLIB.

2. А.И.Овчинников (Университет города Нью-Йорк)

Символьные вычисление и уравнения с частными производными.

Аннотация

Мы обсудим оценки снизу и сверху для эффективной теоремы Гильберта о нулях для систем полиномиальных уравнений с частными производными. Оценивается число применений операций дифференцирования к системе таких уравнений, достаточное для проведения проверки совместности системы чисто алгебраическим способом. Оценка является функцией от степени и порядка уравнений системы и от числа зависимых и независимых переменных. Эту задачу поставил Зайденберг в 1956 году. Первая общаяШ оценка в явном виде появилась в 2009 году и выражалась через функцию Аккермана. Первую явную оценку для обыкновенных уравнений получил Григорьев в 1989 году. Эта оценка для обыкновенных уравнений, но с постоянными коэффициентами, была улучшена в 2014 году. Наш результат не имеет таких ограничений.

1. A.A.Gusev, V.P. Gerdt, O.Chuluunbaatar, S.I.Vinitsky (JINR, Dubna)

Complex of algorithms and programs to solve boundary-value problems.

Abstract

A series of research works on design of symbolic-numerical algorithms and their implementation in a Maple-Fortran environment for solving boundary-value problems of the Schrödinger type in a finite domain of multidimensional configuration space will be presented. The main ingredient of the algorithm is the method proposed by the Soviet mathematician (Nobel prize, 1975) L.V. Kantorovich in 1934 for the numerical solution of boundary-value two-dimensional problems of elliptic type by reducing them to a system of the ordinary differential equations. From the programs to be presented, six programs have been included in the Program Library of the journal Computer Physics Communications and one program in the JINRLIB library.

2. A.I.Ovchinnikov (City University of New York)

Symbolic Compuation and Partial Differential Equations.

Abstract

We will discuss upper and lower bounds for the effective Nullstellensatz for systems of polynomial PDEs. These are uniform bounds for the number of differentiations to be applied to all equations of a system o.f PDEs in order to discover algebraically whether it is consistent. The bounds are functions of the degrees and orders of the equations of the system and the numbers of dependent and independent variables in them. Seidenberg was the first to address this problem in 1956. The first explicit bounds appeared in 2009, with the upper bound expressed in terms of the Ackermann function. In the case of one derivation, the first explicit bound is due to Grigoriev (1989). In 2014, another bound was obtained if restricted to the case of one derivation and constant coefficients. Our new result does not have these restrictions.

Slides

А.Д.Брюно (Институт прикладной математики им. М.В. Келдыша)

Вычисление наилучших диофантовых приближений и основных единиц алгебраических полей.

Аннотация

Пусть в вещественном $n$-мерном пространстве $\mathbb{R}^{n}=\{X\}$ задано $m$ однородных вещественных форм $f_{i}(X)$, $i=1,\ldots,m$, $2\leqslant m\leqslant n$. Выпуклая оболочка множества точек $G(X)=\left(|f_{1}(X)|,\ldots,|f_{m}(X)|\right)$ для целочисленных $X\in\mathbb{Z}^{n}$ во многих случаях является выпуклым многогранным множеством, граница которого для $||X||<\mathrm{const}$ вычисляется с помощью стандартной программы. Граничные точки $G(X)$, т. е. лежащие на этой границе, соответствуют наилучшим диофантовым приближениям $X$ для указанных форм. Это дает глобальное обобщение цепной дроби. Для $n=3$ обобщить цепную дробь безуспешно пытались Эйлер, Якоби, Дирихле, Эрмит, Пуанкаре, Гурвиц, Клейн, Минковский, Брун, Арнольд и многие другие.

Пусть $p(\xi)$ — целый неприводимый в $\mathbb{Q}$ многочлен степени $n$ и $\lambda$ — его корень. Набор основных единиц кольца $\mathbb{Z}[\lambda]$ можно вычислить по граничным точкам некоторой совокупности линейных и квадратичных форм, построенных по корням многочлена $p(\xi)$. Аналогично вычисляется набор фундаментальных единиц поля $\mathbb{Q}(\lambda)$. До сих пор эти единицы вычислялись только для $n=2$ (с помощью обычных цепных дробей) и $n=3$ (с помощью алгоритма Вороного).

Наш подход обобщает цепную дробь, дает наилучшие совместные приближения и основные единицы алгебраических полей для любого $n$.

A.D.Bruno (Keldysh Institute of Applied Mathematics)

Computation of the best Diophantine approximations and of the fundamental units of the algebraic fields

Abstract

Let in the real $n$-dimensional space $\mathbb{R}^{n}=\{X\}$ be given $m$ real homogeneous forms $f_{i}(X)$, $i=1,\ldots,m$, $2\leqslant m\leqslant n$. The convex hull of the set of points $G(X)=(|f_{1}(X)|,\ldots,|f_{m}(X)|)$ for integer $X\in\mathbb{Z}^{n}$ in many cases is a convex polyhedral set. Its boundary for $||X||<\mathrm{const}$ can be computed by means of the standard program. Boundary points $G(X)$, i. e. lying on the boundary, corrrespond to the best Diophantine approximations $X$ for the given forms. That gives the global generalization of the continued fraction. For $n=3$ Euler, Jacobi, Dirichlet, Hermite, Poincaré, Hurwitz, Klein, Minkowski, Brun, Arnold and a lot of others tried to generalize the continued fraction, but without a succes.

Let $p(\xi)$ be an integer real irreducible in $\mathbb{Q}$ polynomial of the order $n$ and $\lambda$ be its root. The set of fundamental units of the ring $\mathbb{Z}[\lambda]$ can be computed using boundary points of some set of linear and quadratic forms, constructed by means of the roots of the polynomial $p(\xi)$. Similary one can compute a set of fundamental units of the field $\mathbb{Q}(\lambda)$. Up today such sets of units were computed only for $n=2$ (using usual continued fractions) and $n=3$ (using the Voronoi algorithm).

Our approach generalizes the continued fraction, gives the best Diophantine approximations and fundamental units of algebraic fields for any $n$.

Slides (Malaschonok - 1.), Slides (Lyakhov - 2.), Slides (Lyakhov - 3.)

1. Г.И.Малашонок (Тамбовский государственный университет)

Облачный математический сервис «Math Partner».

Аннотация

Мы приводим общие характеристики облачного математического сервиса MathPartner, который теперь свободно доступен на технологической платформе программы «Университетский Кластер» (http://unihub.ru). Он позволяет использовать масштабные математические объекты, которые хранятся на жестком диске, обеспечивает ввод и вывод результатов в файлы пользователя. Он предоставляет возможность проводить вычисления не только на сервере, но и на вычислительном кластере. Мы выделяем его основные отличия от других систем символьно-численных вычислений, описываем элементы синтаксиса и сервис пользователя.

2. Д.Мичелс (Стэнфорд, США), Д.Ляхов (НАНБ, Минск), В.Гердт (ОИЯИ, Дубна), Г.Соботтка и А.Вебер (Бонн, Германия)

Частные аналитические решения системы Кирхгофа.

Аннотация

Представлен символьно-численный алгоритм для решения системы Кирхгофа, которая описывает динамику упругого стержня и учитывает сдвиг, изгиб и кручение. Метод основан на получении точного решения подсистемы системы Кирхгофа. Представлены примеры моделирования в 2-мерном и 3-мерном случаях.

3. Д.Ляхов (НАНБ, Минск), В.Гердт (ОИЯИ, Дубна)

Линеаризация скалярного дифференциального уравнения.

Аннотация

Представлен алгоритм, реализованный в системе компьютерной алгебры Maple в виде скрипта для линеаризации обыкновенного скалярного дифференциального уравнения. Тест-линеаризация полностью алгоритмична. Алгоритм основан на двух разных концепциях: прямая процедура Ли и анализ симметрий ОДУ. В сравнении с другими результатами мы не делаем никаких ограничений на порядок ОДУ.

1. G.I.Malasсhonok (Tambov State University)

Cloud mathematical service «Math Partner»

Abstract

We present the general characteristics of the cloud mathematical service MathPartner, which is now freely available on the technology platform of the program «University Cluster» (http://unihub.ru). This service allows you to use of large-scale mathematical objects that are stored on your hard disk, provides input and output results in the user's files. It provides the ability to perform calculations not only on the server but also on a computing cluster. We highlight its main difference from other systems of symbolic-numerical computations, describe the syntax elements and the services for users.

2. D.Michels (Stanford, USA), D.Lyakhov (NASB, Minsk), V.Gerdt (JINR, Dubna), G.Sobottka and A.Weber (Bonn, Germany)

Partial analytical solution of the Kirchhoff equation.

Abstract

We present symbolic-numerical method for solution of the Kirchhoff system, that describes spatiotemporal evolution of elastic rod and takes into account its bending, twisting and longitudinal dilation deformation. The method is based on general analytical solution of subsystem of the Kirchhoff system. Some examples of simulation in 2D and 3D cases are presented.

3. D.Lyakhov (NASB, Minsk), V.Gerdt (JINR, Dubna)

Linearization of scalar ordinary differential equation.

Abstract

We present the algorithm and script on Maple for linearization of scalar ordinary differential equation. Test-linearization is purely algorithmic. Algorithm is based on two different concepts: direct Lie procedure and analysis of symmetry algebra of ODE. In comparison with other results we do not make any restrictions on the order of differential equations.

Sides

А.А.Гусев, Л.Ле Хай, О.Чулуунбаатар, С.И.Виницкий (ОИЯИ, Дубна)

Алгоритм решения краевых задач для системы обыкновенных дифференциальных уравнений второго порядка.

Аннотация

Представлен алгоритм, реализованный в системе компьютерной алгебры MAPLE в виде программы KANTBP 4M, для решения краевых задач, таких как задача на собственные значения или рассеяния для системы обыкновенных дифференциальных уравнений второго порядка с непрерывными или кусочно-непрерывными вещественными или комплексными коэффициентами. Дискретизация краевой задачи реализована методом конечных элементов с интерполяционными полиномами Эрмита, сохраняющими непрерывность производных искомого решения [A.A. Gusev et al, Lecture Notes in Computer Science 8660, 138-154 (2014)]. Для вычисления метастабильных состояний с комплексными собственными значениями энергии, или для решения задачи на связанные состояния с граничными условиями, зависящими от спектрального параметра, реализована ньютоновская итерационная схема [A.A. Gusev et al, Lecture Notes in Computer Science 9301, 182–197 (2015)].

A.A.Gusev, L.Le Hai, O.Chuluunbaatar, S.I.Vinitsky (JINR, Dubna)

Algorithm for solving boundary problems of the system of ordinary second order differential equations.

Abstract

We present the algorithm and program KANTBP 4M implemented in the computer algebra system MAPLE for solutions of boundary-value problems, such as eigenvalue or scattering problems for the system of ordinary differential equations of the second order with continuous or piecewise continuous real- or complex-valued coefficients. Discretization of the boundary problems is implemented by the finite element method with the interpolation Hermite polynomials preserves the property of continuity of derivatives of the desired solutions [A.A. Gusev et al, Lecture Notes in Computer Science 8660, 138-154 (2014)]. For the calculation of metastable states with complex eigenvalues of energy, or to solve the problem for bound states with boundary conditions, depending on the spectral parameter, the Newtonian iteration scheme is implemented [A.A. Gusev et al, Lecture Notes in Computer Science 9301, 182-197 (2015)].

Slides (Malykh), Slides (Eferina et al.)

1. М.Д.Малых (МГУ)

О разностных схемах, задающих (n,n)-соответствия между слоями.

Аннотация

В Стокгольмских лекциях на примере уравнений 1-го и 2-го порядков Пенлеве указал на свойство, общее всем дифференциальным уравнениям, разрешимых в элементарных, алгебраических и абелевых функциях: общее решение таких уравнений зависит от константы интегрирования алгебраически. Таким образом, наложив алгебраическое условие на общее решение, мы можем выделить класс общеупотрибимых трансцендентных функций. В нашем прошлом докладе это утверждение было вписано в круг идей теории Галуа, при этом получилась версия этой теории, в которой изначально список допустимых операций не фиксирован.

Сопоставление этой идеи с методом конченых разностей выделяет на класс дифференциальных уравнений y'=f(x,y), для которых возможно составить разностную схему, задающую алгебраическое (n,n)-соответствие между слоями. Такие схемы примечательны тем, что они верно описывают подвижные особые точки решений. В докладе будут даны примеры.

Обобщение этой идеи на случай уравнения вида F(x,y,y')=0 подразумевает вычислений группы автоморфизмов кривой рода p>1. В докладе будет предложен алгоритм вычисления автоморфизмов заданной алгебраической кривой рода p>1 и приведены примеры его применения. Прием основан на одной конструкции, использованной в редко цитируемой работе Гурвица 1887 г.

2. Е.Г.Еферина, А.В.Королькова, Д.С.Кулябов, Л.А.Севастьянов (Российский университет дружбы народов)

Применение предметно-ориентированных систем компьютерной алгебры при моделировании марковских процессов.

Аннотация

В процессе математического моделирования можно выделить стадии разработки модели и стадии её реализации. Эти стадии достаточно сильно отличаются друг от друга. Разнится и используемый инструментарий. Авторы на протяжении долгого времени занимались моделированием марковских процессов с использованием систем компьютерной алгебры. В процессе разработки использовалось несколько универсальных пакетов компьютерной алгебры. Но на стадии реализации комплекса программ была выявлена неудовлетворительность универсальных пакетов. В докладе приводятся требования к системе компьютерной алгебры, возникшие в процессе разработки комплекса программ, и обосновывается выбор предметно-ориентированной системы FORM.

1. M.D.Malykh (MSU)

On the difference schemes setting (n,n)-correspondence between layers.

Abstract

In the Stockholm lectures (1897) Painleve gave on the example of the equations of the 1st and 2nd order property which is common for all differential equations, solvable in elementary, special and abelian functions: the general solutions of these equations depend on integration constants algebraically. Thus, if we record algebraic properties of the general solution, we can allocate a class of all-usable transcendental functions. In our last report this statement was inscribed in a circle of ideas of the theory of Galois: the version of this theory was offered, in which the list of all-usable transcendental operations isn't fixed.

Association of this idea with the finite difference method point out a class of the differential equations y'=f(x,y) for which it is possible to write the difference schemes setting algebraic (n,n)-correspondence between layers. These schemes are remarkable that they correctly describe singularity. In the report examples will be given.

Generalization of this idea on a case of the equation F(x,y,y')=0 means calculation of automorphism group for a given curve of genus p>1. In the report an algorithm for computing the automorphisms for a given algebraic curve of genus p>1 is offered, same examples of its application are given. Method is based on a construction used in seldom quoted articles by Hurwitz, 1887.

2. E.G.Eferina, A.V.Korolkova, D.S.Kulyabov, L.A.Sevastyanov (Peoples’ Friendship University of Russia)

Use of Domain-specific Computer Algebra Systems in the Simulation of Markov Processes.

Abstract

The process of mathematical modeling can be divided into the stage of the model development stage and its implementation. These stages are quite different from each other. And different tools used at each stage. Authors are for a long time to carry out simulation of Markov processes with the help of computer algebra systems. During the development process, we used some universal computer algebra systems. At the stage of implementation of software, we found unsatisfactory of universal computer algebra packages. The report describes the requirements for the computer algebra system that have arisen during the programming. We substantiate the choice of domain-specific computer algebra system FORM.