C 19 октября 2011г. начал работу новый саминар Компьютерная алгебра факультета ВМК МГУ и ВЦ РАН под руководством профессора С.А.Абрамова. Более подробную информацию можно получить на сайте семинара по адресу

http://www.ccas.ru/sabramov/seminar/doku.php

— Alexander Kryukov 15/10/2011 15:47

of Faculty of Computational Mathematics and Cybernetics and Skobeltsyn Institute of Nuclear Physics of Lomonosov Moscow State University

Previous years see Archive.

Джон Маккарти (4 сентября 1927, Бостон — 24 октября 2011, Стэнфорд) — выдающийся американский информатик, автор термина «искусственный интеллект» (1955), изобретатель языка Лисп (1958), основоположник функционального программирования, лауреат Премии Тьюринга (1971) за огромный вклад в область исследований искусственного интеллекта.

http://ru.wikipedia.org/wiki/Маккарти,_Джон

The International Symposium on Symbolic and Algebraic Computation (ISSAC) is the premier conference for research in symbolic computation and computer algebra. ISSAC 2012 is the 37th meeting in the series, started in 1966 and held annually since 1981, in North America, Europe and Asia. The conference presents a range of invited speakers, tutorias, poster sessions, software demonstrations and vendor exhibits with a centerpiece of contributed research papers.

ISSAC 2012 will be held on July 22-25, 2012 in Grenoble, France.

See more details here

E.Shemyakova (Computing Centre of  the Russian Academy of Science).

Darboux (or Differential) Transformations (DT) is a well-known and one of the most efficient methods to obtain analytic solutions of Linear and Non-Linear Partial Differential Equations. In his works Darboux provides a number of intuitive and informal ideas which form the foundation of the DT theory. The methods which have been effectively used by Mathematical Physics (e.g. for soliton solutions) have been rigorously proved and formulated for only few special cases.

Thus our starting point was to provide formal statements and proofs for the completeness of the Wronskian formulas for DT of hyperbolic operators on the plane. We solved this problem for orders one and two. During this process we discover that DT have interesting algebraic structure and properties.

Алгебраическая структура преобразований Дарбу операторов $D_x_y + a(x,y) D_x + b(x,y) D_y + c(x,y)$

Е. Шемякова (Вычислительный центр Российской академии наук).

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

Нашей отправной точкой была идея сформулировать и доказать полноту формул вронскиана для ПД гиперболических операторов на плоскости. Задачу удалось решить для ПД порядка один и два. Дополнительно обнаружено, что алгебраическая структура ПД обладает рядом интересных свойств.

E. Zima (Wilfrid Laurier University, Waterloo, Canada)

A modification of an algorithm for indefinite rational summation is presented. It is based on shiftless factorization of polynomials and direct divisibility test. When the rational function is not summable it provides solution to the additive decomposition problem with minimal degree of the denominator of the rational part. The algorithm solves the problem in time which is polynomial in the size of the input and linear in the minimal possible size of the output. This removes all non-essential dependencies of the running time of the algorithm from the dispersion of the input. The result is extended to the case of quasi-rational indefinite summation. Prototype implementation of the algorithm in Maple together with succinct representation of the intermediate results is discussed.Синтетическое деление в контексте неопределенного суммирования

Е. Зима (Университет Уилфрида Лорье, Ватерлоо, Канада).

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

A.D. Bruno, A.B. Batkhin (Keldysh Institute of Applied Mathematics RAS)

We consider a polynomial in three variables near singular point, where the polynomial and its partial derivatives vanish. We propose a method of computation of asymptotic expansions for all branches of the set of zeroes of the polynomial. We distinguish three types of expansions. The method of computation is based on the spatial Power Geometry. We show an implementation of the method on a polynomial in three variables of the degree six, and we compute asymptotic expansions at infinity and at degenerate singular point of the polynomial.

Разрешение алгебраической сингулярности алгоритмами степенной геометрии

А.Д. Брюно, А.Б. Батхин (ИПМ им. Келдыша РАН)

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

Abramov S.A. , Khmelnov D.E. (Computing Centre of the Russian Academy of Science, Russia)

We consider systems of linear ordinary differential equations containing m unknown functions of a single variable x. Coefficients of the systems are polynomials over a number field. Each of the systems consists of m independent equations. The equations are of arbitrary orders. We propose an algorithm which, given a system S of this type, constructs a nonzero polynomial d(x) such that if S possesses an analytic solution having a singularity at a then d(a)=0.

Особые точки решений линейных дифференциальных систем с полиномиальными коэффициентами

Абрамов С.А.,     Хмельнов Д.Е. (Вычислительный центр РАН, Россия)

Рассматриваются системы линейных обыкновенных дифференциальных уравнений относительно m неизвестных функций одной переменной  x. Коэффициенты систем являются полиномами над некоторым числовым полем. Каждая система состоит из m независимых уравнений. Уравнения имеют произвольные порядки.Предлагается алгоритм, который для заданной системы S описанного типа строит ненулевой полиином d(x) такой, что если S обладает аналитическим решением с особенностью в точке a, то d(a)=0.

Romanovski V.G. (CAMTP - Center for Applied Mathematics and Theoretical Physics, University of Maribor, Slovenia)

Consider a dynamical system described by ODE's of the form

dz/dt = F(z)

where F is a vector field on a manifold. A time-reversible symmetry of the system is an invertible map R, such that

d(R(z))/dt  =-F(R(z)).

We investigate the case of two-dimensional polynomial systems, that is, z =(x,y) and F is a polynomial vector-function. We also assume that R is a linear transformation. If the coefficients of F are parameters, then the action of the group SL(2,C) on z induces a transformation of the coefficients of the system. These transformations also form a group, which we denote by U. We call polynomial invariants of U the Sibirsky invariants of our system. In the talk we describe an efficient algorithm to compute a generating set of these invariants.

Using methods of computational algebra we show an interconnection of the physically important phenomena of time-reversibility, involution and the Sibirsky invariants. Furthermore, we characterize the set of all time-reversible systems within a particular family of complex two-dimensional polynomial differential systems and give an efficient computational algorithm for finding this set.

We then discuss application of the invariants to studying periodic oscillations and limit cycles bifurcations in polynomial systems of ODE.

Обратимость и инварианты полиномиальных систем ОДУ

Романовский В.Г. (CAMTP - Центр прикладной математики и теоретической физики, Университет Марибора, Словения)

Рассмотрим динамическую систему, описываемую ОДУ вида

 dz/ dt = F (z),

где  F - векторное  поле на некотором многообразии.   Симетрией  системы называется обратимое отображение R, такое, что

d(R(z))/dt  =-F(R(z)).

Мы исследуем случай  двумерных полиномиальных систем, то есть, z = (х, у) и F является полиномиальной  вектор-функцией. Предполагаем также, что R-линейное преобразование.  Если коэффициенты F являются параметрами, то действие группы SL (2, С) на z  индуцирует преобразование коэффициентов системы. Эти преобразования также образуют группу, которую мы обозначим через U. Мы называем полиномиальные инварианты группы U инвариантами Сибирского  нашей системы. В докладе описывается эффективный алгоритм вычисления порождающего множества этих инвариантов.

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

Мы также обсуждаем  применение инвариантов к изучению периодических колебаний и бифуркации предельных циклов в полиномиальных систем ОДУ.

Gutnik  S.A. (Moscow Institute of Physics and Technology (University)), Sarychev V.A. (Keldysh Institute of Applied Mathematics (RAS))

The equilibrium orientations of a satellite in a circular orbit under the influence of gravitational and constant torques are investigated. Differential equations of the satellite's attitude motion take the Lagrange form. The stationary motions of a satellite are governed by a set of nonlinear algebraic equations.

A computer algebra method based on algorithm for the construction Groebner basis is proposed for determining the equilibrium orientations of a satellite with a given constant torque vector and given principal central moments of inertia. It is shown that 24 isolated equilibrium orientations exist when the module of constant vector is sufficiently small.

The equilibrium orientations are determined by algebraic equation of the sixth degree.The investigation of number of equilibria developing both the Computer Algebra method and the numerical analysis of these algebraic equations was completed.

The domains evolution with fixed number of equilibria is investigated numerically in dependence of three dimensionless system parameters and bifurcation values of the system parameters corresponding to the qualitative change of these domains are considered.

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

Гутник Сергей Александрович (МФТИ(У)), Сарычев Васлий Андреевич (ИПМ им. М.В.Келдыша)

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

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

С использованием методов компьютерной алгебры было проведено построение базиса Грёбнера для данной алгебраической системы. Получено алгебраическое уравнение шестой степени, которое позволяет определить численно все равновесные решения и построить области с одинаковым количеством равновесных решений в зависимости от безразмерного параметра системы. Показано, что при небольшом модуле вектора постоянного момента существуют 24 положения равновесия спутника.

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

A.Aranson (Scientific Research Institute of Long-Range Radiocommunication)

We consider software to calculate power expansions of solutions of nonlinear ODE systems by power geometry algorithms. These programs are made by CAS Maxima and C++ languages. We demonstrate calculations of leader terms of power expansions of solutions near zero and infinity for Euler-Poisson ODE system. One describes motion of a rigid body around a fixed point and consist of six autonomous ODE with six parameters and three first integrals that exists for any admissible vales of parameters. When parameters of Euler-Poisson ODE system correspond to N.Kowalewski reduction, by means of considered software we calculate supports of equations and first integrals of the system and pairs of normal cones - truncated systems. Number of pairs is 53637 when time limit to zero and 53456 when time limit to infinity. All these pairs were analysed and we calculate 58 real power expansions of solutions near zero.

Программы для вычисления степенных разложений решений нелинейных систем ОДУ алгоритмами степенной геометриии

А.Арансон (НИИ Дальней радиосвязи)

Разработаны программы для вычисления степенных разложений решений нелинейных систем ОДУ алгоритмами степенной геометриии. Эти программы написаны на языке C++ и на языке системы символьных вычислений Maxima. Показывается вычисление первых членов степенных разложений действительных решений в нуле и бесконечности по времени для системы ОДУ Эйлера-Пуассона, описывающей движение твёрдого тела около неподвижной точки. Система Эйлера-Пуассона состоит из шести автономных ОДУ первого порядка с шестью параметрами и имеет три первых интеграла при любых допустимых значениях параметров. При условиях на параметры системы Эйлера-Пуассона, допускающих редукцию Н.Ковалевского, с помощью разработанных программ были вычислены носители уравнений и трёх первых интегралов системы, а также пары нормальный конус - укороченная система. Число пар составило 53637 для случая, когда время стремится к нулю и 53456 для случая, когда время стремится к бесконечности. Для всех этих пар были выполнены вычисления и получено 58 вещественных степенных разложений решений в нуле.

D.J.Jeffrey (University of Western Ontario, Canada)

The evaluation of definite integrals is the source of the largest number of reported errors in computer algebra systems. One reason for this is the use of the Risch algorithm for indefinite integration. The expressions produced by this algorithm contain branch cuts. Thus the standard Newton-Leibnitz method fails without corrective action. In this talk, the notion of a “rectifying transformation” is introduced. Several transformations are described and their use in the evaluation of integrals is illustrated. Finally, an algorithm is described for the rectification of a class of integrals of rational trigonometric polynomials.

Интегрирование: распрямление преобразований

Д. Дж. Джеффри (Университет Западного Онтарио, Канада)

Вычисление определенных интегралов является причиной большинства регистрируемых пользователями ошибок в системах компьютерной алгебры. Одна из причин - алгоритм Рича для неопределенного интегрирования. Функции, получаемые с помощью этого алгоритма, содержат точки ветвления. Поэтому стандартный метод Ньютона-Лейбница не работает без дополнительных корректирующих действий. В докладе вводится понятие “распрямляющего преобразования”. Описываются несколько такого рода преобразований, приводятся примеры вычисления интегралов. Описывается алгоритм  распрямления для классе рациональных тригонометрических полиномов.

D. Trushin (Faculty of Mechanics and Mathematics of MSU).

Our purpose is to solve the following three problems: finding a criterion for a differential ideal to have a finite differential standard basis, describing the quasi-spectrum of a ring of divided powers, and constructing an algebraic theory of constructible differential fields.

Дифференциальные идеалы

Д.Трушин (Mеханико-математический факультет МГУ)

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

I.G.Klyuchnikov (Keldysh Institute of Applied Mathematics, RAS).

A new algorithm of supercompilation for higher-order functional language has been developed, which, unlike other algorithms, is intended to be used for program analysis, rather than optimization, the main idea being that the transformed program may be easier to analyze, than the original one.

This algorithm has been implemented in an experimental supercompiler HOSC, the first supercompiler for Haskell whose correctness and termination properties have been carefully investigated and formally proved.

HOSC is able to automatically prove the equivalence of a large class of higher-order expressions by just comparing the corresponding residual expressions for syntactical identity. Moreover, a slight modification of HOSC is often capable to check if a pair of equivalent expressions forms an improvement lemma.

A new method of multi-level supercompilation, based on the use of improvement lemmas, is suggested. We show that a multi-level supercompiler, in comparison to single-level ones, is able to perform deeper program transformations, improving asymptotic complexity of programs.

The results obtained are applicable also to other areas where lambda terms are transformed, generalized or there is a need to ensure the termination of rewriting – such as program transformation systems, theorem provers, computer algebra, etc.

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

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

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

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

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

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

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

The International Symposium on Symbolic and Algebraic Computation (ISSAC) is the premier conference for research in symbolic computation and computer algebra. ISSAC 2011 is the 36th meeting in the series, started in 1966 and held annually since 1981, in North America, Europe and Asia. The conference presents a range of invited speakers, tutorials, poster sessions, software demonstrations and vendor exhibits with a centerpiece of contributed research papers.

ISSAC 2011 is affiliated with the 2011 International Workshop on Symbolic Numeric Computation (SNC 2011) which will be held on June 7–9, 2011 as another member of the ACM FCRC.

More details in the conference here

D.E.Khmelnov. (Computer Center of RAS)

A few induced recurrences based computer-algebra (symbolic) algorithms for solving systems of linear ordinary (differential, difference and q-difference) equations with polynomial coefficients are proposed. The experimental efficiency comparison of the implemented software package with known existing alternatives is given .

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

Д.Е.Хмельнов. (ВЦ РАН)

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

Valery G. Romanovski (CAMTP - Center for Applied Mathematics and Theoretical Physics, University of Maribor, Slovenia)

Consider systems of the form dx/dt=P(x,y), dy/dt=Q(x,y), where P, Q are polynomials of degree n, and suppose that the coefficients of the polynomials are parameters. In the case, when the origin of the system is a non-degenerate center or focus, a limit cycle bifurcates from the origin when the linearized system changes its stability. This is the well-known Andronov-Hopf bifurcation. Limit cycle bifurcations which depend on nonlinear terms of system (sometimes such bifurcations are called the degenerate Andronov-Hopf bifurcations) are much less investigated, but there is an approach to their study suggested by N.N. Bautin. Bautin also introduced the notion of cyclicity, which nowadays plays an important role in the theory of bifurcations. By the definition, the cyclicity of an elementary focus or center of a polynomial system of ODEs is the maximum number of limit cycles that can be made to bifurcate from the singularity under small perturbation of parameters of the system.

We present an algorithmic approach to investigate the cyclicity problem for polynomial systems. The main steps of the approach are as follows. We complexify the system and let B denote the Bautin ideal of the system, the ideal generated by the focus quantities, that is, polynomials whose vanishing characterizes a center at the origin. Suppose B_K is the ideal generated by the first K focus quantities and generates the same variety as B. If the ideal B_K is radical then the cyclicity is bounded above by K. If it is not radical we show that sometimes it is possible to map the polynomials to a polynomial subalgebra in which a non-radical B_K can become radical. Most of calculations are performing using algorithms of computational commutative algebra based on the Groebner basis theory.

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

В.Г.Романовский (CAMTP - Центр прикладной математики и теоретической физики, Университет Марибора, Словения)

Рассмотрим системы вида  dx/dt = P (х, у),  dy/dt = Q (х, у), где  P (х,у), Q(х, у) - многочлены степени n, и предположим, что коэффициенты многочленов являются параметрами. В случае, если начало координат системы –  невырожденный центр или фокус, предельный  цикл  бифурцирует из начала координат,  когда линеаризованная  систем  меняет устойчивость.  Это хорошо известная бифуркация Андронова-Хопфа. Бифуркации предельных циклов, которые зависят от нелинейных членов  системы (иногда такие бифуркации называют вырожденными бифуркациями Андронова-Хопфа) гораздо менее исследованы, но имеется  подход к их изучению предложенный  Н. Н.  Баутиным. Баутин также ввел понятие цикличности, которое в настоящее время играет важную роль в теории бифуркаций. По определению,  цикличность элементарного фокуса или центра полиномиальной системе ОДУ  это максимальное число предельных циклов, которые появляются из особой точки при малых возмущениях параметров системы.

В докладе представлен алгоритмический подход к иссследованию  проблемы цикличности некоторых классов полиномиальных систем. Основные этапы подхода заключаются в следующем. Комплексифицируем  систему  и обозначим через B идеал Баутина, порожденный фокусными   величинами, т. е. многочленами обращение  в нуль которых влечет  наличие центра в начале координат. Предположим, что  B_K,  идеал, порожденный первыми К фокусными  величинами, определят тоже алгебраическое многообразие, что и идеал  B.  Если идеал B_K радикален, то цикличность ограничена сверху числом К.  Если же идеал  не радикальный, то иногда оказывается возможным отобразить его в полиномиальную подалгебру, где образ идеала является  радикальным идеалом. Большинство вычислений  выполняется  с использованием алгоритмов вычислительной коммутативной алгебры основанных на теории  базисов Гребнера.