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

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

Slides

К.Д.Царегородцев (аспирант МГУ им. М. В. Ломоносова, старший специалист-исследователь лаборатории криптографии АО «НПК «Криптонит»)

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

Аннотация

В последнее время растет интерес к использованию в криптографических (и теоретико-кодовых) приложениях некоммутативных и неассоциативных структур (в частности, квазигрупп). Задание квазигруппы в табличном виде непрактично — размер требуемой для хранения памяти растет крайне быстро. Для функционального задания квазигрупп В. Носовым в 1999 году было введено понятие правильного семейства (булевых) функций. Исходное определение было расширено сначала на случай абелевых групп, а затем — и на более общие алгебраические структуры. В докладе мы рассмотрим результаты, полученные в последние годы: альтернативные характеризации правильных семейств (с более «геометрической» точки зрения), некоторые их свойства (оценки на количество правильных семейств, некоторые результаты о конкретных классах правильных семейств).

K.D.Tsaregorodtsev (Postgraduate student of Lomonosov Moscow State University, senior researcher at the Cryptography Laboratory of JSC «NPK «Kryptonite»)

Proper families of discrete functions: equivalent definitions and properties».

Abstract

Recently, there has been a growing interest in the use of noncommutative and non-associative structures (in particular, quasigroups) in cryptographic (and coding theory) applications. Tabular specification of a quasigroup is impractical due to the memory requirement grows extremely fast. In order to handle this problem a functional representation of a quasigroup operation by means of proper families of (boolean) functions was introduced by V. Nosov in 1999. The original definition was extended firstly to the case of Abelian groups, and then to more general algebraic structures. In the report, we will consider the results obtained in recent years: alternative characterizations of proper families (from a more «geometric» point of view) and some of their properties (e.g., estimates on the number of boolean proper families and results on specific classes of proper families).

Slides

Т.В.Яковлева (Федеральный исследовательский центр «Информатика и управление» Российской академии наук)

Двухпараметрический анализ райсовских данных: основы теории и результаты численного моделирования с помощью системы Wolfram Mathematiсa

Аннотация

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

T.V.Yakovleva (Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences)

Two-Parameter Analysis of Rician Data: basics of a theory and numerical simulation results obtained by means of Wolfram Mathematiсa system

Abstract

We consider the theoretical basics and mathematical methods of data analysis at the Rice statistical distribution. The peculiarities of this distribution cause the necessity of the development of a new approach and special mathematical apparatus for data analysis implying the joint computing of both the signal and the noise parameters, thus ensuring an efficient reconstruction of the informative signal’s component against the noise background. The two-parameter task solution is being implemented by the mathematical statistics techniques such as a maximum likelihood method, variants of the method of moments as well as the combining of the mentioned techniques. The results of numerical experiments obtained be means of Wolfram Mathematica, confirm the efficiency of the elaborated techniques of the rician data two-parameter analysis.

Slides

И.Е.Широков (МГУ, физический факультет, кафедра теоретической физики)

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

Аннотация

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

I.E.Shirokov (MSU, Faculty of physics , department of theoretical physics)

Application of computer algebra methods to quantum calculations in supersymmetric theories

Abstract

Computer algebra methods applied to quantum computing in supersymmetric theories are considered in the light of a recently created special program written in C++ language. The calculations are carried out within the framework of Feynman's superfield diagram technique. Both the generation of diagrams and further transformations up to obtaining the standard momentum integrals are considered. Specific examples demonstrate the possibilities of such an approach for theories with different parameters. The results of the performed calculations are discussed, including the timing in different situations.

Slides

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

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

Аннотация

Рассмотрены различные методы выбора модулей в модулярной арифметике. При предложенном выборе модулей ускоряется как перевод целого числа в модулярное представление, так и реконструкция результата по остаткам. Особое внимание уделено модулям вида 2^n±1 и 2^n±2^k±1. Рассмотрены различные схемы выбора этих типов модулей и алгоритмы преобразования целых чисел произвольной точности в модулярное представление и обратно. Обсуждаются результаты экспериментальной реализации описанных алгоритмов в системе GMP.

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

On a special choice of moduli in modular arithmetic

Abstract

Several methods of selection of moduli in modular arithmetic are considered. With the proposed choice of moduli both modular reduction of an integer and reconstruction from modular images are accelerated. Special attention is paid to the moduli of the forms 2^n±1 and 2^n±2^k±1. Different schemes of choice of these types of moduli and algorithms for conversion of arbitrary precision integers into the modular representation and back are considered. Results of experimental implementation of the described algorithms in the GMP system are discussed.

Slides

В.Ф.Еднерал (НИИ ядерной физики имени Д.В. Скобельцына, МГУ им. М.В.Ломоносова)

Об интегрируемости автономных систем ОДУ с зависящей от параметров полиномиальной правой частью

Аннотация

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

На основе сформулированной гипотезы предлагается эвристический метод, позволяющий определять случаи интегрируемости автономной системы ОДУ с полиномиальной правой частью, зависящей от параметра, при наличии резонанса в линейной части этой системы.

V.F.Edneral (Skobeltsyn Institute of Nuclear Physics of Lomonosov Moscow State University)

On the integrability of autonomous ODE systems with parameter-dependent polynomial right-hand side

Abstract

The report considers a possible connection between the local integrability of autonomous two-dimensional ODE systems with a polynomial right-hand side and their global Darboux integrability. For several dynamical systems of this type, the conditions for their local integrability near stationary points are written out and restrictions on the parameters under which these conditions are satisfied are found. For the appropriate values of the parameters, we can write out the first integral, so we assume that local integrability at fixed points is necessary for the existence of the first integral. But since the system is locally integrable at other (regular) points, this statement can be reformulated as a hypothesis that for the integrability of a two-dimensional autonomous polynomial ODE system in some region of the phase space, its local integrability is necessary at each point of this region. We emphasize that this hypothesis was put forward only on an experimental basis.

Based on the formulated hypothesis, a heuristic method is proposed that allows one to determine the cases of integrability of an autonomous ODE system with a polynomial right-hand side depending on a parameter in the presence of a resonance in the linear part of this system.

Slides

А.Б.Батхин (Институт прикладной математики им. М.В.Келдыша РАН, Московский физико-технический институт, Москва), З.Х.Хайдаров (Самаркандский государственный университет им. Ш.Рашидова, Самарканд)

Структура резонансных многообразий в многочастотных системах Гамильтона

Аннотация

Исследуются резонансные многообразия многочастотной системы Гамильтона. Обсуждаются способы вычисления условие существования резонанса произвольного порядка кратности один с применением методов компьютерной алгебры (базисы Грёбнера элиминационных идеалов) и степенной геометрии (степенные преобразования). Это условие формулируется в виде нулей квазиоднородного полинома от коэффициентов характеристического многочлена линейной части системы Гамильтона. Полученные результаты могут быть использованы для изучения областей устойчивости положения равновесия многопараметрической системы Гамильтона, а также для асимптотического интегрирования её нормальной формы.

A.B.Batkhin (Keldysh Institute of Applied Mathematics of RAS, Moscow Institute of Physics and Technology, Moscow), Z.Kh.Khaydarov (Samarkand State University named after Sh. Rashidov, Samarkand)

Structure of resonant varieties in multifrequency Hamiltonian systems

Abstract

Resonant manifolds of a multifrequency Hamiltonian system are investigated. We discuss methods for computing the condition of existence of a resonance of arbitrary order and multiplicity one using computer algebra ( Gröbner bases of elimination ideals) and power geometry (power transformations) techniques. This condition is formulated in a form of zeros of a quasi-uniform polynomial from the coefficients of the characteristic polynomial of the linear part of the Hamiltonian system. The obtained results can be used to investigate the formal stability regions of the equilibrium of a Hamiltonian multiparameter system as well as for the asymptotic integration of its normal form.

Slides

Г.Погудин (Политехническая школа, Париж)

Решение разностных уравнений в последовательностях: что можно и чего нельзя

Аннотация

Рассмотрим рекуррентное соотношение для чисел Фибоначчи f_{n + 2} = f_{n + 1} + f_n. Его можно рассматривать как уравнение связывающее последовательность и ее сдвиг. В общем случае, можно рассматривать уравнения, в которые наравне с арифметическими операциями входит оператор сдвига. Многие вопросы, связанные с нелинейными рекуррентами и динамическими системами в дискретном времени, можно сформулировать как утверждения о решениях таких уравнений, называемых разностными, в кольце последовательностей. В 2007 году Хрущовский и Пуан доказали, что теория первого порядка, соответствующая кольцу последовательностей в таком языке, не разрешима, то есть не существует алгоритма для определения истинности формулы первого порядка в таком языке. В докладе речь пойдет о двух недавних результатах, развивающих эту тематику в двух разных направлениях:

• алгоритм для проверки разрешимости системы разностных уравнений в кольце последовательностей (совместно с А. Овчинниковым и Т. Скенлоном)
• несколько утверждений о неразрешимости для естественных усложнений задачи о разрешимости, например, разрешимости в последовательностях действительных чисел и проверки принадлежности радикальному разностному идеалу (совместно с Т. Скенлоном и М. Вибмером)

G.Pogudin (Ecole polytechnique, Paris)

Solving equations in sequences: cans and cannots

Abstract

Consider any recurrence relation, for example, the one for Fibonacci numbers: f_{n + 2} = f_{n + 1} + f_n. One can think of this equation as a relation between the sequence itself and its shifts. A natural general framework that would incorporate equations of this sort would be a language including not only arithmetic operations, but also a shift operator S. In this language, the above recurrence will recast to $S^2(f) = S(f) + f$. Many questions about nonlinear recurrences and discrete-time dynamical systems can be stated as questions about solutions of equations in this extended language (so-called difference equations) in the ring of sequences. In 2007, Hrushovski and Point showed that the first order theory of sequences in this language is undecidable, that is, there is no algorithm for verifying correctness of first-order formulas. In this talk, I will describe two more recent results in this area in two different directions:

• an algorithm for deciding whether a system of difference equations has solutions in sequences (joint with A. Ovchinnikov and T. Scanlon)
• several undecidability results showing that many natural extensions of the consistency problem above are undecidable including determining the existence of a solution in real-valued sequences and membership problem for radical difference ideals (joint with T. Scanlon and M. Wibmer).

Slides

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

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

Аннотация

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

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

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

Investigation of the Equilibrium Orientations of Two Connected Bodies in a Circular Orbit Using Computer Algebra Methods

Abstract

In the report, we investigate the equilibrium orientations of a system of two bodies connected by a spherical hinge that moves along a circular orbit under the action of gravitational torque. A computer algebra method based on the resultant approach is applied to reduce the satellite's stationary motion system of algebraic equations to a single algebraic equation in one variable, which determines the equilibrium configurations of the two-body system. Classification of domains with equal numbers of equilibrium solutions is carried out using algebraic methods for constructing discriminant hypersurfaces. Bifurcation curves in the space of system parameters that determine boundaries of domains with a fixed number of equilibria for the two-body system are obtained symbolically. Depending on the parameters of the problem, the number of equilibria is found by analyzing the real roots of the algebraic equations. Using the proposed approach, it is shown the possible number of equilibrium orientations of the satellite–stabilizer system in a circular orbit.

Slides

А.Н.Прокопеня (Варшавский университет естественных наук – SGGW, Польша)

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

Аннотация

Обсуждается проблема построения периодических решений уравнений движения машины Атвуда, в которой два груза одинаковой массы могут колебаться в вертикальной плоскости. Получены дифференциальные уравнения движения системы и описан алгоритм вычисления их периодических решений в виде степенных рядов по малому параметру при условии резонанса частот вида n ω1=m ω2, где n и m - натуральные числа, а ω1, ω2 – частоты колебаний грузов. Сравнение полученных результатов с соответствующими численными решениями уравнений движения подтверждает их корректность. Все необходимые вычисления выполняются с помощью системы компьютерной алгебры Wolfram Mathematica.

A.N.Prokopenya (Warsaw University of Life Sciences – SGGW, Poland)

Construction of periodic solutions of the equations of motion of an Atwood machine with two oscillating bodies

Abstract

The problem of constructing periodic solutions of the equations of motion of the Atwood machine, in which two bodies of the same mass can oscillate in a vertical plane, is discussed. Differential equations of motion of the system are obtained and an algorithm for computing their periodic solutions in the form of power series with respect to a small parameter is described under the condition of frequency resonance of the form n ω1=m ω2, where n and m are natural numbers, and ω1, ω2 are the frequencies of the bodies oscillations. Comparison of the obtained results with the corresponding numerical solutions of the equations of motion confirms their correctness. All necessary calculations are performed using the Wolfram Mathematica computer algebra system.

Slides

Video Video Video

Шаоши Чен (Академия математики и системных наук, Китайская академия наук)

Задачи устойчивости в символьном интегрировании

Аннотация

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

Доклад посвящается Зимингу Ли в честь его шестидесятилетия.

Shaoshi Chen (Academy of Mathematics and Systems Science, Chinese Academy of Sciences)

Stability Problems in Symbolic Integration

Abstract

This talk aims at initializing a dynamical aspect of symbolic integration by studying stability problems in differential fields. We present some basic properties of stable elementary functions and D-finite power series that enable us to characterize three special families of stable elementary functions including rational functions, logarithmic functions, and exponential functions. Some problems for future studies are proposed towards deeper dynamical studies in differential and difference algebra.

This talk is dedicated to Ziming Li on the occasion of his 60th birthday.

Slides

Очередное заседание семинара «Компьютерная алгебра» состоится во вторник 17 мая 2022 года в 16:30 по московскому времени в дистанционном режиме через Zoom. Cоответствующая ссылка для подключения будет сообщена письмом приглашенным участникам.

Зиминг Ли (Главная лаборатория математики и механизации, AMSS Китайская академия наук, Пекин)

Вычисление элементарных интегралов с помощью аддитивных разложений и гомоморфного оценивания

Аннотация

Аддитивное разложение - это представление данной функции f в виде суммы производной g' и остатка r. При этом g и r принадлежат тому же дифференциальному полю F, что и f. Дополнительные требования: (i) r в определенном смысле минимально; (ii) f является производной некоторого элемента из F тогда и только тогда, когда r = 0. Таким образом, вычисление интеграла от f сводится к вычислению интеграла от r.

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

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

Результаты получены в сотрудничестве с Шаоши Ченом, Хао Ду, Цзин Го, Иманом Гао и Элейн Вонг.

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 Tuesday, May 17, 2022 at 16:30 Moscow time online via Zoom. The corresponding connection link will be e-mailed to the invited participants.

Ziming Li (Key Lab of Mathematics and Mechanization, AMSS Chinese Academy of Sciences, Beijing)

Computing Elementary Integrals by Additive Decompositions and Homomorphic Valuation

Abstract

An additive decomposition writes a function f as the sum of a derivative g' and a remainder r. Both g and r lie in the same differential field F as f does. The requirements on the remainder are:

(i) r is minimal in some sense; (ii) f is a derivative of some element in F if and only if r = 0.

Thus, computing an integral of f amounts to computing an integral of r.

In this talk, we present an additive decomposition in S-primitive extensions, which include logarithmic extensions as an instance, and show that computing elementary integrals of remainders in such an extension does not need to solve any differential equation. This feature enables us to use homomorphic valuations to compute elementary integrals over S-primitive extensions.

We will also discuss about recent work on additive decompositions in hyperexponential extensions of some types.

The results in this talk are obtained in collaboration with Shaoshi Chen, Hao Du, Jing Guo, Yima n Gao and Elaine Wong.

Slides

М.Петковшек (Люблянский Университет, факультет математики и физики. Любляна, Словения)

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

Аннотация

Для линейного рекуррентного уравнения Ly = 0 с полиномиальными коэффициентами задача нахождения его ненулевого решения, имеющего вид определенной гипергеометрической суммы, связана с обратной задачей креативного телескопинга. Эта последняя задача остается открытой уже более трех десятилетий. Предлагается алгоритм, позволяющий для рассматриваемого уравнения и квазитреугольного, совместимого со сдвигом, факториального базиса B = <P_k(n)>, k = 0, 1, 2, …, в полиномиальном пространстве K[n ] над полем K нулевой характеристики, находить такое рекуррентное соотношение, которому удовлетворяет последовательность коэффициентов c = <c_k>, k = 0, 1, 2, …, решения y_n в форме суммы слагаемых вида c_k P_k( n), k = 0, 1, 2, … (сумма конечна для каждого натурального n в силу квазитреугольности базиса B). В более общем случае, если B является m-просеянным для некоторого положительного целое число m, алгоритм вычисляет систему из m рекуррентных уравнений, которым удовлетворяют m-секции последовательности коэффициентов c. Если мы можем найти явное ненулевое решение этой системы, мы получаем явное ненулевое решение исходного уравнения Ly = 0.

Работа выполнена совместно с Антонио Хименесом-Пастором (Эколь Политекник, Париж, Франция).

M.Petkovsek (University of Ljubljana, Faculty of Mathematics and Physics, Ljubljana, Slovenia)

The Factorial-Basis Method for Finding Definite-Sum Solutions of Linear Recurrences With Polynomial Coefficients

Abstract

The problem of finding a nonzero solution of a linear recurrence Ly = 0 with polynomial coeffi cients where y has the form of a defi nite hypergeometric sum, related to the Inverse Creative Telescoping Problem, has now been open for more than three decades. We present an algorithm which, given such a recurrence and a quasi-triangular, shift-compatible factorial basis B = <P_k(n)> (for k = 0, 1, 2, …) of the polynomial space K[n] over a field K of characteristic zero, computes a recurrence satisfi ed by the coe fficient sequence c = <c_k> (for k = 0, 1, 2, …) of the solution y_n = sum of c_k P_k(n) for k = 0, 1, 2, … (where, due to the quasi-triangularity of B, the sum terminates for each natural n). More generally, if B is m-sieved for some positive integer m, the algorithm computes a system of m recurrences satisfi ed by the m-sections of the coeffi cient sequence c. If we can find an explicit nonzero solution of this system, we obtain an explicit nonzero solution of the original recurrence Ly = 0.

This will be a joint talk with Antonio Jimenez-Pastor (currently a postdoc at École Polytechnique, Paris).

Slides

М.Н.Геворкян (Российский университет дружбы народов)

Описание аппарата геометрической алгебры и его реализации в системе компьютерной алгебры SymPy

Аннотация

Геометрическая алгебра является реализацией алгебры Клиффорда. Основные понятия геометрической алгебры восходят к 19 веку, к трудам Грассмана и Клиффорда, однако основная волна исследований на эту тему началась уже в 21 веке. В целом следует отметить прикладной характер исследований по геометрической алгебре, относящихся к в основном к физике и математическим основам компьютерной графики. В физике с помощью геометрической алгебры можно описать спиновое пространство, повороты и бусты в СТО. В области компьютерной графики методы описания вращений с помощью бивекторов могут потенциально вытеснить кватернионы и бикватернионы. При описании в пространство-временной алгебре с помощью этого формализма можно описать эффекты связанные со скоростью и другие релятивистские эффекты: движение с релятивистской скоростью, прецессия Томаса, фаза Берри, эффект Ааронова-Бома. Аппарат геометрической алгебры можно рассматривать как частный случай тензорного формализма, так как p-векторы являются антисимметричными контравариантными тензорами. Однако при универсальном тензорном описании мы получаем усложнение теории, так как допускаем лишнюю общность описания, а также теряем ряд эффектов, которые возникают в алгебре Клиффорда (например, релятивистское движение) для многих задач. Мы считаем, что применение специализированного пространства и математического аппарата было бы очень полезно для физики, так как обобщает спиноры, кватернионы, комплексные числа, но не использует поле комплексных чисел. В докладе рассматриваются основные понятия геометрической алгебры. В связи с прикладным характером рассматриваемого В связи с прикладным характером рассматриваемого предмета, в докладе при изложении теории сделан акцент на реализацию основных операций геометрической алгебры в системе символьных вычислений SymPy. Показаны примеры использования геометрической алгебры в области физики и компьютерной геометрии.

M.N.Gevorkyan (Peoples’ Friendship University of Russia (RUDN University))

Description of the geometric algebra apparatus and its implementation in the SymPy computer algebra system

Abstract

Geometric algebra is an implementation of the Clifford algebra. The basic concepts of geometric algebra date back to the 19th century, to the works of Grassman and Clifford, but the main wave of research on this topic began in the 21st century. In general, it should be noted the applied nature of research on geometric algebra, related mainly to physics and the mathematical foundations of computer graphics. In physics, with the help of geometric algebra, it is possible to describe spin space, rotations and boosts in SRT. In the field of computer graphics, methods for describing rotations using bivectors can potentially displace quaternions and biquaternions. When described in space-time algebra, this formalism can be used to describe velocity-related effects and other relativistic effects: motion with relativistic velocity, Thomas precession, Berry phase, the Aharonov-Bohm effect. The apparatus of geometric algebra can be considered as a special case of tensor formalism, since p-vectors are antisymmetric contravariant tensors. However, with a universal tensor description, we get a complication of the theory, since we allow an extra generality of the description, and also lose a number of effects that arise in the Clifford algebra (for example, relativistic motion) for many tasks. We believe that the use of a specialized space and mathematical apparatus would be very useful for physics, since it generalizes spinors, quaternions, complex numbers, but does not use the field of complex numbers. The report discusses the basic concepts of geometric algebra. Due to the applied nature of the considered Due to the applied nature of the subject under consideration, in the presentation of the theory, the report focuses on the implementation of the basic operations of geometric algebra in the SymPy symbolic computing system. Examples of the use of geometric algebra in the field of physics and computer geometry are shown.

Slides

С.Д.Мешвелиани (Институт программных систем им. А.К. Айламазяна РАН, Переславль-Залесский, Россия)

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

Аннотация

Обсуждаются конструктивное доказательство завершаемости алгоритма NF нормальной формы для многочленов нескольких переменных и связанное с ним понятие допустимого упорядочения <e на показателях мономов. В классической математике свойство обрыва убывающей цепочки (descending-halt) для отношения <e выводится из леммы Диксона, и этого достаточно для обоснования завершаемости алгоритма NF. В доказательном программировании требуется конструктивное доказательство и более сильное свойство отношения порядка: свойство хорошей заданности (well-founded). Обсуждаются некоторые известные конструктивные подходы к проблеме, а также приводится прямое и простое конструктивное доказательство хорошей заданности для случая двух переменных.

S.D.Meshveliani (Ailamazyan Program systems institute of RAS, Pereslavl-Zalessky, Russia)

On constructive proofs for termination of the normal form algorithm for a multivariate polynomial with respect to a polynomial list

Abstract

There are discussed a constructive proof for termination of the normal form algorithm NF for multivariate polynomials and its related notion of admissible ordering <e on the monomial exponents. In classical logic, the descending-halt property for <e is derived from the Dickson's lemma, and this is sufficient to prove termination of NF. In provable programming, it is required a constructive proof, and a stronger property for the order relation: well-foundedness. There are discussed certain known constructive approaches to the subject, and also it is presented a simple and direct constructive proof for the case of two variables.

Slides

В.Г.Захаров (Институт механики сплошных сред УрО РАН, Пермь)

Матричный метод нахождения полиномиальных решений системы линейных дифференциальных уравнений в частных производных

Аннотация

Предложен матричный метод конструктивного нахождения базиса полиномиального пространства решений системы линейных, с постоянными коэффициентами, уравнений в частных производных (УЧП'х) с полиномиальными правыми частями (в общем случае, как полиномы, так и правые части УЧП'х, должны быть умножены на экспоненты). При этом матрица, строящаяся в нашем методе, — есть просто матрица линейной системы алгебраических уравнений. И наш подход не требует использования сложных методов общей алгебры (таких как примарные разложения идеалов и т.п.). При этом открывается возможность исследовать пространства решений элементарными методами линейной алгебры. Так, в частности, доказывается фундаментальный факт, что линейное УЧП (не система) с постоянными коэффициентами всегда имеет полиномиальное (умноженное на экспоненту, в общем случае) решение произвольно большой степени. Рассмотрен ряд примеров построения множества полиномов (умноженных на экспоненты, в общем случае), являющихся базисными функциями пространств решений уравнений Лапласа, Гельмгольца, Пуассона.

V.G.Zakharov (Institute of Continuum Mechanics RAS, Perm, Russia)

Matrix method of polynomial solutions to constant coefficient PDE's

Abstract

We introduce a matrix method to determine constructively the basis of a polynomial space that the space is a solution to the system of linear constant coefficient PDE's with polynomial right-hand sides (in general, polynomials and right-hand sides of PDE's must be multiplied by exponentials). The matrix, obtained in our method, is the matrix of the system of linear algebraic equations and the method is not based on complicated general algebra approaches (like primary decompositions). But our approach allows to use linear algebra to investigate solution spaces. In particular, we proved that a linear constant coefficient PDE always has a polynomial solution (multiplied by an exponential, generally) up to arbitrary large degree. Some polynomial sets that the polynomials (multiplied by exponentials, in general) are basis functions of solution spaces to the Laplace, Helmholtz or Poisson equations are constructed.

Slides and Maple worksheets

Очередное заседание семинара «Компьютерная алгебра» состоится в среду 15 декабря 2021 года в 16:30 по московскому времени в дистанционном режиме через Zoom. Cоответствующая ссылка для подключения будет сообщена письмом приглашенным участникам.

Бертран Тегия Табугия ( Университет Касселя, Германия )

Ряды и последовательности, определяемые квадратными дифференциальными уравнениями

Аннотация

Предлагается алгоритм построения формальных степенных рядов для функций, которые не удовлетворяют линейным дифференциальным уравнениям с полиномиальными коэффициентами. К таким функциям, например, относятся тангенс, секанс, косеканс, экспоненциальные производящие функции для чисел Бернулли, Эйлера, Белла, и многие другие. Лежащий в основе метод определяет новый класс функций, являющихся, в основном, решениями квадратных дифференциальных уравнений. Их изучение открывает дополнительные исследовательские вопросы. Мы представляем один уже окончательный результат о «нелинейном» угадывании «нехороших» коэффициентов разложений в степенные ряды, делающим возможным нахождение производящих функций.

Часть этого выступления была представлена на Maple Conference 2021 в соавторстве с Вольфрамом Кёпфом.

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, December 15, 2021 at 16:30 Moscow time online via Zoom. The corresponding connection link will be e-mailed to the invited participants.

Bertrand Teguia Tabuguia ( University of Kassel, Germany )

Series and Sequences Defined by Quadratic Differential Equations

Abstract

We describe a general-purpose algorithm to represent formal power series of functions that do not satisfy linear differential equations with polynomial coefficients. These are functions like tangent, secant, cosecant, the exponential generating functions of the Bernoulli numbers, Euler numbers, Bell numbers, and many others. The underlying method defines a new class of functions, mainly characterized by quadratic differential equations, and their study opens further research questions. We present one already conclusive result about the «nonlinear» guessing, which makes it possible to find generating functions from finitely many «not nice» coefficients of their power series expansions.

I presented a part of this talk at the Maple Conference 2021 in collaboration with Wolfram Koepf.

Slides GitHub Link

Ю.А.Блинков (Научный центр вычислительных методов в прикладной математике института прикладной математики и телекоммуникаций РУДН)

Объектно-ориентированное динамическое перераспределение памяти в C++

Аннотация

Организация динамического перераспределения памяти в пакете GInv (Groebner Involutive) по вычислению базисов Грёбнера. Использование для динамических структур данных, таких как списки, красно-черные и бинарные деревья, библиотеки GMP для вычислений с целыми числами с произвольной точностью.

Yu.A.Blinkov (Research Center of Computational Methods in Applied Mathematics at the RUDN Institute of Applied Mathematics and Telecommunications)

Object-oriented dynamic memory reallocation in C++

Abstract

Organizing Dynamic Memory Reallocation in GInv (Groebner Involutive Package) for the calculation of Gröbner bases is presented. Dynamic data structures such as lists, red-black and binary trees, GMP libraries are used for computing with integers with arbitrary accuracy.

Slides

Мулей Баркату, Тома Клюзо, Али Эль Хадж (Лиможский университет; CNRS; XLIM UMR 7252; MATHIS)

Символьные алгоритмы исследования и решения псевдолинейных систем

Аннотация

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

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 Thursday, October 21, 2021 at 16:30 Moscow time online via Zoom. The corresponding connection link will be e-mailed to the invited participants.

Moulay Barkatou, Thomas Cluzeau, and Ali El Hajj (University of Limoges ; CNRS ; XLIM UMR 7252 ; MATHIS)

Symbolic Algorithms for Studying and Solving Pseudo-Linear Systems

Abstract

This talk concerns the study of pseudo-linear systems: a large class of linear functional systems including differential, difference and q-difference systems. Firstly, we develop a direct algorithm for computing simple forms of pseudo-linear systems by extending the ideas of existing algorithms for differential and difference system. Then we present a generic and efficient algorithm for computing rational solutions (including a universal denominator) of first order pseudo-linear systems. Finally we develop two new recursive algorithms for computing rational and hypergeometric solutions of partial pseudo-linear systems with arbitrary number of variables. All algorithms are implemented in our Maple package PseudoLinearSystems.

Slides

А.Н.Прокопеня (Варшавский университет естественных наук - SGGW), М.Дж.Минглибаев, А.Б.Кошербаева (Казахский национальный университет им. аль-Фараби)

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

Аннотация

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

A.N.Prokopenya (Warsaw University of Life Sciences – SGGW, Warsaw, Poland), M.Zh.Minglibayev, A.B.Kosherbayeva (al-Farabi Kazakh National University, Almaty, Kazakhstan)

Symbolic computation in studying the evolutionary equations in the problem of many bodies of variable masses

Abstract

We consider the classical problem of many bodies when their masses vary isotropically according to some given laws and reactive forces do not arise. As a result the differential equations of motion may be written out similarly to the case of constant masses. It is known that the problem is not integrable in case of three and more bodies even for constant masses and so the perturbation theory is usually applied to its investigation. In the system under consideration an unperturbed motion is described by an exact solution of the problem of two bodies of variable masses determining the bodies motion along quasi-conic sections. Main attention is paid to discussion of computational problems connecting with obtaining an expansion of the perturbing function into power series in terms of small parameters and determining the evolutionary equations. The corresponding calculations are demonstrated with Wolfram Mathematica.