Contact Persons: Sergei Abramov (sergeyabramov [AT] mail [DOT] ru), Alla Bogolubskaya (abogol [AT] jinr [DOT] ru), Anna Ryabenko (anna [DOT] ryabenko [AT] gmail [DOT] com) / Контактные лица: Сергей Александрович Абрамов (sergeyabramov [AT] mail [DOT] ru), Алла Анатольевна Боголюбская (abogol [AT] jinr [DOT] ru), Анна Андреевна Рябенко (anna [DOT] ryabenko [AT] gmail [DOT] com).
Russian Computer Algebra Community page
Computer algebra seminar of Limoges University, France
From the history of computer algebra / Из истории компьютерной алгебры:
Очередное заседание семинара «Компьютерная алгебра» состоится в среду 16 октября 2024 года в 16:30 по московскому времени в дистанционном режиме через Zoom. Cоответствующая ссылка для подключения будет сообщена письмом приглашенным участникам.
А.В. Селиверстов (ИППИ РАН, Москва). Совместная работа с О.А. Зверковым.
Алгоритм полиномиального времени для распознавания существования (0, 1)-решения системы немногих линейных уравнений по модулю три.
Аннотация
Распознавание существования (0, 1)-решения для системы линейных уравнений по модулю три служит примером NP-полной задачи. Однако в случае, когда количество уравнений ограничено сверху достаточно медленно растущей функцией от числа переменных, предложен новый алгоритм полиномиального времени для распознавания существования (0, 1)-решения у такой системы. Алгоритм основан на замечании: если в матрице коэффициентов присутствуют ненулевые пропорциональные друг другу столбцы, то элиминация соответствующих переменных сохраняет свойство отсутствия (0, 1)-решения системы. В частности, каждая система из двух уравнений от пяти переменных допускает элиминацию некоторых переменных, при которой сохраняется свойство отсутствия (0, 1)-решения системы. Кроме того, мы предлагаем безошибочный эвристический алгоритм, который реализован на языке программирования Python. Для представления матриц и выполнения базовых операций используется библиотека NumPy. Входом служит расширенная матрица системы. С использованием этой реализации была рассчитана эмпирическая оценка времени работы. Экспериментально показано, что алгоритм эффективнее для разреженных систем уравнений.
—————————————————————————————————
The next meeting of the seminar on Computer Algebra of Faculty of Computational Mathematics and Cybernetics of MSU, and Computing Centre of RAS will be on Wednesday, Oktober 16, 2024 at 16:30 Moscow time online via Zoom. The corresponding connection link will be e-mailed to the invited participants.
A.V. Seliverstov (IITP RAS, Moscow). This is joint work with O.A. Zverkov.
A polynomial-time algorithm for recognizing the existence of a (0, 1)-solutions to a system of several linear equations modulo three.
Abstract
Recognizing the existence of a (0, 1)-solution to a system of linear equations modulo three is an example of an NP-complete problem. In case the number of equations is less than a sufficiently slowly growing function of the number of variables, a new polynomial-time algorithm is proposed to recognize the existence of a (0, 1)-solution to such a system. The algorithm is based on the note that if the coefficient matrix contains non-zero columns proportional to each other, then the elimination of the corresponding variables preserves the property of having no (0, 1)-solution to the system. In particular, every system of two equations in five variables allows the elimination of some variables that preserves the property of having no (0, 1)-solution to the system. Moreover, we propose an errorless heuristic algorithm, which is implemented using the Python programming language. The NumPy library is used to represent matrices and perform basic operations. The input is the augmented matrix. An empirical running time estimate has been calculated using the implementation. It has been experimentally shown that the algorithm is more efficient for sparse systems of equations.
Жак-Артюр Вейль (Лиможский университет). Совместная работа с Ги Казалем и Примитиво Акоста-Уманезом.
Вычисление (нелинейного) группоида Мальгранжа-Галуа для уравнений Пенлеве посредством линеаризации
Аннотация
Для некоторых классов дифференциальных уравнений Пенлеве описывается подход к вычислению нелинейного аналога дифференциальной группы Галуа — группоида Мальгранжа. Мы концентрируемся на классах уравнений Пенлеве, которые допускают одно рациональное или алгебраическое решение. Линеаризация вдоль этого конкретного решения, позволяет выяснить
(1) как на практике могут вычисляться дифференциальные группы Галуа последовательных вариационных уравнений,
(2) что группоид Мальгранжа содержит, в некотором смысле, все эти дифференциальные группы Галуа,
(3) что, если размерность одной из этих дифференциальных групп Галуа больше 8, то уравнение Пенлеве имеет «очень большой» группоид Мальгранжа, и, следовательно, обладает свойствами сильной неприводимости.
Изложение будет фокусироваться на примерах, чтобы сделать в формате семинара теорию понятной.
—————————————————————————————————
Jacques-Arthur Weil (Limoges University). This is joint work with Guy Casale and Primitivo Acosta-Humanez.
Computing the Malgrange-Galois (non-linear) grouppoïd for Painlevé equations via linearizations
Abstract
In this work, we show an approach to compute the non-linear analog of the differential Galois group, the Malgrange groupoïd, for some classes of Painlevé differential equations. We focus on classes of Painlevé equations which admit one rational or algebraic solution. Linearizing along this particular solution, we will explain how :
(1) the differential Galois groups of the successive variational equations can be computed in practice
(2) the Malgrange groupoïd contains, in a sense, all these differential Galois groups
(3) if the dimension of one of these differential Galois groups is bigger than 8, the Painlevé equation has a Malgrange groupoïd which is “very big” and hence has strong irreducibility properties.
The talk will focus on examples to make the theory understandable in a seminar format.
А.Н. Прокопеня (Warsaw University of Life Sciences), М.Д. Минглибаев (A l-Farabi Kazakh National University), А.Б. Кошербаева (A l-Farabi Kazakh National University)
Символьно-численные вычисления при моделировании динамики систем многих тел с переменными массами
Аннотация
Исследуется классическая задача многих тел с переменными массами, которые притягиваются в соответствии с законом всемирного тяготения. Массы всех тел могут изменяться изотропно с разными скоростями. Применяя второй закон Ньютона, можно легко записать уравнения движения тел, аналогично случаю постоянных масс. Законы изменения масс определяются произвольными дважды дифференцируемыми функциями времени. Уравнения движения неинтегрируемы, и для их исследования применяется теория возмущений на основе апериодического движения по квазиконическим сечениям. Основное внимание уделяется обсуждению вычислительных задач, возникающих при получении разложения возмущающих сил в степенные ряды по малым параметрам, а также при выводе эволюционных уравнений, которые в дальнейшем решаются численно. Все соответствующие вычисления выполняются с использованием системы компьютерной алгебры Wolfram Mathematica.
—————————————————————————————————
A. Prokopenya (Warsaw University of Life Sciences), M. Minglibayev (A l-Farabi Kazakh National University), A. Kosherbayeva (A l-Farabi Kazakh National University)
Symbolic-numeric computation in modeling the dynamics of the many-body systems of variable masses
Abstract
We investigate the classical problem of many bodies with variable masses attracting each other according to Newton's law of universal gravitation. The masses of all bodies may change isotropically at different rates. Applying Newton’s second law, one can easily write the equations of motion of the bodies which look similar to the case of constant masses. The laws of the masses change are arbitrary twice differentiable given functions of time. The equations of motion are not integrable and we apply the canonical perturbation theory to their investigation using an aperiodic motion along quasi-conical section as the unperturbed one. The main attention is paid to the discussion of computational problems arising in deriving the expansion of the perturbing forces in a power series in small parameters and in deriving the evolutionary equations which are solved later numerically. All the relevant computations are carried out using Wolfram Mathematica.
А.А. Михалев (Механико-математический факультет МГУ имени М.В.Ломоносова)
Алгебры, нётеровые по уравнениям
Аннотация
Доказано, что алгебры Витта W_n, лево-симметричные алгебры Витта L_n, симплектические алгебры Пуассона P_n и свободные алгебры многообразий, порожденные этими алгебрами, являются нётеровыми по уравнениям. Доклад основан на совместной работе А.А.Михалев, М.Мустафа, У.Умирбаев, Journal of Algebra 633 (2023), 814–830.
—————————————————————————————————
A.A. Mikhalev (Faculty of Mechanics and Mathematics, M.V.Lomonosov Moscow State University)
Equationally Noetherian algebras
Abstract
We show that Witt algebras W_n, left-symmetric Witt algebras L_n, symplectic Poisson algebras P_n, and free algebras of the varieties generated by these algebras are equationally Noetherian. The talk is based on the joint article with M.Mustafa and U.Umirbaev.
А.Д. Брюно (Институт прикладной математики им. М.В.Келдыша РАН)
Аналитическое решение любого уравнения вида многочлен от переменных и производных
Аннотация
Разработано исчисление [1], позволяющее аналитически вычислять асимптотические разложения решений для уравнений, являющихся многочленами от переменных и производных, а также для систем таких уравнений. Это исчисление применимо к уравнениям любого типа: алгебраическим [2, 3], обыкновенным дифференциальным [4] и в частных производных [5], а также – к их системам. Исчисление основано на алгоритмах степенной геометрии: (а) выделение укороченных уравнений, состоящих из всех ведущих слагаемых, а также из (б) степенных, (в) логарифмических и (г) нормализующих преобразований координат. Требуемое при этом программное обеспечение уже разработано.
—————————————————————————————————
A.D. Bruno (Keldysh Institute of Applied Mathematics of RAS)
Analytic solution to any equation of polynomial type on variables and derivatives
Abstract
A calculus [1] has been developed which allows one to calculate analytically asymptotic expansions of solutions to equations which are polynomials on variables and their derivatives, as well as to systems of such equations. This calculus is applied to equations of any type: algebraic [2, 3], ordinary differential [4] and partial differential [5], as well as to their systems. The calculus is based on algorithms of power geometry: (a) selection of truncated equations consisting of all leading terms, as well as (b) power transformations, ( c ) logarithmic and (d) normalizing coordinate transformations. The required software for this calculus has already been developed.
М.МакКаллум (Лондонский университет королевы Марии)
Использование компьютерной алгебры для характеристики пространства-времени с изотропией
Аннотация
Много лет назад я заметил, что в определенных случаях симметрия пространства-времени в общей теории относительности обязательно приводит к идентичности наблюдений и другим свойствам в разных направлениях, то есть к изотропии. Я постараюсь адекватно обрисовать необходимую основу. Работа, которую я представлю, является частью программы решения обратной задачи: когда пространство-время с изотропией в каждой точке обязательно имеет непрерывную группу симметрий? Я решил это для случая, когда изотропии образуют одну и ту же непрерывную группу в каждой точке.
Существует общая теорема о том, что пространство-время (и более общие римановы многообразия) локально характеризуются компонентами тензора кривизны и его производных. Компьютерная алгебра была мною использована для изучения влияния наложения изотропии на эти величины и, таким образом, для выводов об общей структуре симметрии.
—————————————————————————————————
M.McCallum (Queen Mary University of London)
Using computer algebra to characterize spacetimes with isotropy
Abstract
Many years ago I noted that certain spacetimes in general relativity with symmetries would necessarily give rise to identical observations, and other properties, i in different directions, i.e. an isotropy. I shall try to adequately sketch the necessary background. The work I shall describe is part of a program to solve an inverse problem: when is it that a spacetime with the same isotropies at every point necessarily has a continuous group of symmetries? I solved this for the case where the isotropies form the same continuous group at every point.
There is a general theorem that spacetimes (and more general Riemannian manifolds) are locally characterized by components of the curvature tensor and its derivatives. Computer algebra was used to study the effect of imposing the isotropies on these quantities and so infer the overall symmetry structure.
А.И.Овчинников (Городской университет Нью-Йорка)
Оценка значений параметров в системах ОДУ, применяя интерполяцию данных, дифференциальную алгебру и решение систем полиномиальных уравнений.
Аннотация
Системы ОДУ часто зависят от неизвестных параметров, знание значений которых может быть важным само по себе. В докладе будет представлен подход к оценке значений параметров, не использующий оптимизацию. Предложенный подход основывается на дифференциальной алгебре, интерполяции результатов измерений для оценки значений производных и на решении систем полиномиальных уравнений. Такой подход позволит получить реализацию с гарантированными результатами.
—————————————————————————————————
A.I.Ovchinninkov (City University of New York)
Parameter estimation in ODE systems via data interpolation, differential algebra, and polynomial system solving
Abstract
Frequently, ODE systems depend on unknown parameters, which could be important quantities on their own. We will discuss an approach to estimate these parameter values that does not rely on optimization. It uses differential algebra, output data interpolation for derivative estimation, and on polynomial system solving. This approach provides a framework for a robust implementation.
Кытманов А.А. (Институт перспективных технологий и индустриального программирования МИРЭА - Российский технологический университет), Царев С.П. (Красноярский Математический Центр, Сибирский Федеральный Университет)
Дискретные ортогональные полиномы, асимптотика решения специальных линейных рекуррентных уравнений второго порядка с полиномиальным коэффициентом и граничные эффекты полиномиальных фильтров (памяти профессора М.Петковшека)
Аннотация
Описан новый результат в классической теории одномерных дискретных ортогональных полиномов: чрезвычайно быстрое убывание их значений вблизи границы интервала для полиномов достаточно высокой степени. Этот эффект кардинально отличается от поведения гораздо более популярных в математических учебных программах непрерывных ортогональных полиномов.
Данный эффект имеет как теоретическую связь с некоторыми классическими направлениями компьютерной алгебры (изучением решений линейных обыкновенных рекуррентных уравнений), так и важную практическую сторону: обоснование ранее наблюдавшегося в численном анализе эффекта подавления сигнала вблизи границы интервала обработки при удалении полиномиальных трендов высоких степеней.
—————————————————————————————————
Kytmanov A.A. (Institute for Advanced Technologies and Industrial Programming, MIREA - Russian Technological University), Tsarev S.P. (Krasnoyarsk Mathematical Center, Siberian Federal University)
Discrete orthogonal polynomials, asymptotics of solution of special second-order linear recurrencies with polynomial coefficient, and boundary effects of polynomial filters (in memory of Professor M. Petkovšek)
Abstract
We describe a new result in the classical theory of univariate discrete orthogonal polynomials: extremely fast decay of their values near the interval boundary for polynomials of sufficiently high degree. This effect dramatically differs from the behavior of much more popular in mathematical curricula continuous orthogonal polynomials.
This effect has both a theoretical connection with some classical areas of computer algebra (the study of solutions of linear ordinary recurrent equations) and an important practical side: the proof of the effect of signal suppression near the boundary of the processing interval previously observed in numerical analysis after removing polynomial trends of high degree.
А.Б. Арансон (НИИ Дальней Радиосвязи)
Степенная алгебра для степенной геометрии
Аннотация
В степенной геометрии А.Д. Брюно предлается в том числе применение многогранников Ньютона для вычисления решений алгебраических и дифференциальных уравнений. В докладе рассматриваются эффективные алгоритмы для вычисления решений ОДУ и систем ОДУ в виде рядов Пюизо с ненулевой конечной главной частью с помощью многогранников Ньютона. Показаны результаты применеия этих алгоритмов к системам ОДУ Эйлера-Пуассона, Лотки-Вольтерры и к уравнению Шази. Для системы Эйлера-Пуассона получены в том числе условия на параметры системы для всех известных решений. Вычисления выполнены с применением CAS Maxima и программ на языке C++.
—————————————————————————————————
A.B. Aranson (SRI of Long-Range Radio Communications)
Power Algebra for Power Geometry
Abstract
Applying Newton polyhedrons to calculate solutions for algebraic and differential equations is suggested by Power Geometry of A.D. Bruno. We consider effective algorithms to calculate solutions of ODEs and systems of ODEs in the Puiseux series form with a nonzero finite principal part by means of a Newton polyhedron. The results of applying the considered algorithms to Euler-Poisson and Lotka-Volterra systems of ODEs and to Chazy ODE are presented. The conditions of the Euler-Poisson system parameters for some solutions, including all known solutions, were calculated. CAS Maxima and author C++ programs were used for calculations.
А.С.Кулешов (Механико-математический факультет МГУ им. М.В. Ломоносова), Н.М.Видов (аспирант Механико-математического факультета МГУ им. М.В. Ломоносова)
Нелинейные эффекты вблизи многообразия равновесий неголономных систем
Аннотация
В конце 80-х годов прошлого века в работах Я.В.Татаринова был описан эффект, названный им эффектом трансгрессии. Изучаются нелинейные колебания консервативной неголономной системы около состояния равновесия. Хорошо известно, что такие состояния у неголономных систем не изолированы, а образуют, вообще говоря, многообразия в фазовом пространстве (причина этого явления -– не неинтегрируемость связей, а их дифференциальное представление). Если размерность многообразия равновесий равна числу связей, то в динамике с независимыми частотами уравнения связей «интегрируемы в среднем», то есть в подходящих определяющих координатах движение происходит вблизи координатных плоскостей, причем отклонение от них имеет второй порядок малости и носит колебательный характер. Если размерность многообразия равновесий больше числа связей, то во втором приближении возникает тривиальное смещение вдоль многообразия со скоростью первого порядка малости, а в четвертом приближении может возникнуть эффект дополнительной эволюции вдоль многообразия равновесий со скоростью третьего порядка малости, так что об «интегрируемости в среднем» говорить уже не приходится. Именно этот эффект дополнительной эволюции вдоль многообразия равновесий и был назван в работах Я.В. Татаринова эффектом трансгрессии. Изучение подобных эффектов предполагалось проводить путем привлечения метода нормальных форм.
В докладе представлено детальное описание эффекта трансгрессии в двух задачах динамики неголономных систем: в задаче о движении тяжелого тонкого твердого стержня по поверхности прямого кругового цилиндра и в задаче о качении тяжелого однородного шара по неподвижной поверхности в окрестности наинизшей точки данной поверхности, являющейся точкой эллиптического типа.
—————————————————————————————————
A.S.Kuleshov (Department of Mechanics and Mathematics, M.~V.~Lomonosov Moscow State University), N.M.Vidov (postgraduate student of Department of Mechanics and Mathematics, M.~V.~Lomonosov Moscow State University),
Nonlinear Effects Near the Equilibrium Manifold of Nonholonomic Systems
Abstract
In the late 80th of the last century, Ya.V.Tatarinov described the effect, that he called the transgression effect. Nonlinear oscillations of a conservative nonholonomic system near an equilibrium state are studied. It is well known, that such states in nonholonomic systems are not isolated, but form, generally speaking, manifolds in the phase space (the reason for this phenomenon is not the nonintegrability of the constraints, but their differential representation). If the dimension of the equilibrium manifold is equal to the number of constraints, then in dynamics with independent frequencies the constraint equations are «integrable on average», i.e. in suitably defined coordinates the motion is nearly confined to coordinate planes, and the deviation from the latter is of the second order of smallness and has an oscillatory nature. If the dimension of the equilibrium manifold is greater than the number of constraints, in the second approximation a trivial displacement along the equilibrium manifold occurs with velocity of the first order of smallness, while in the fourth approximation one can catch an effect of additional evolution along the equilibrium manifold with a velocity of the third order of smallness, so that it is no longer appropriate to talk of the «average integrability». It is this effect of additional evolution along the equilibrium manifold that was named in the papers by Ya.~V.~Tatarinov by the transgression effect. The study of such effects was supposed to be carried out by the normal form method.
In this talk we present a detailed description of the transgression effect in two problems of the dynamics of nonholonomic systems: in the problem of motion of a heavy thin rigid rod on the surface of an inclined right circular cylinder and in the problem of the rolling of a heavy homogeneous ball on a fixed surface in the vicinity of the lowest point of this surface, which is an elliptical point.
П.В.Тришин (выпускник Института математики и фундаментальной информатики СФУ, инженер-исследователь Красноярского математического центра)
Необходимое условие и достаточное условие существования рациональных решений однородных разностных уравнений с постоянными коэффициентами
Аннотация
Вопрос о разрешимости разностных уравнений в классе рациональных функций поставлен уже более 50 лет назад. В одномерном случае задача решена С.А. Абрамовым в 1974 (постоянные коэффициенты) и 1989 (полиномиальные коэффициенты) годах.
При переходе к многомерному случаю возникли трудности, так оказалось, что некоторые классы разностных уравнений не могут быть разрешимы в рациональных функциях, или, по крайней мере, в этих классах не существует алгоритмов поиска рациональных решений. Возникает необходимость выделять некоторыми условиями классы разностных уравнений, в которых задача может быть разрешима.
В докладе будут представлены необходимое условие и достаточное условие разрешимости однородных разностных уравнений с постоянными коэффициентами в классе рациональных функций. Приведены примеры на применение результатов работы для поиска рациональных решений разностных уравнений или доказательства их неразрешимости в классе рациональных функций.
—————————————————————————————————
P.V.Trishin (graduate of the Institute of Mathematics and Fundamental Informatics of Siberian Federal University, research engineer of the Krasnoyarsk Mathematical Center)
Necessity and sufficiency of existence rational solutions to homogeneous difference equations with constant coefficients
Abstract
The question of solvability of difference equations in the class of rational functions was posed more than 50 years ago. In the one-dimensional case the problem was solved by S.A. Abramov in 1974 (constant coefficients) and in 1989 (polynomial coefficients).
In the multidimensional case some difficulties arose, as it turned out that some classes of difference equations cannot be solved in rational functions, or, at least, there are no algorithms for finding rational solutions in these classes. There is a need to identify, using certain conditions, classes of difference equations in which the problem can be solvable.
We will present a necessary condition and a sufficient condition of solvability of homogeneous difference equations with constant coefficients in the class of rational functions. Examples on application of the results to find rational solutions of difference equations or to prove their unsolvability will be given.