Это старая версия документа.


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

Contact Person: Sergei Abramov (sergeyabramov [AT] mail [DOT] ru) / Контактное лицо: Сергей Александрович Абрамов (sergeyabramov [AT] mail [DOT] ru).

:!: Russian Computer Algebra Community page

Computer algebra seminar of Limoges University, France

Next meeting/Следующее заседание

Очередное заседание семинара «Компьютерная алгебра» состоится в среду 27 мая 2020 года в дистанционном режиме через ZOOM. Начало трансляции в 16:20. Идентификатор комнаты для видеоконференции: 947 7456 3799. Для подключения к конференции надо пройти по ссылке: https://cern.zoom.us/j/94774563799. Комната будет открыта с 15:50 для тестирования.

:!: Как подключиться к видеоконференции ZOOM можно посмотреть по ссылке Начало работы на ПК и Mac. Скачать приложение ZOOM можно по ссылке download.

А.Крюков, Г.Шпиз (НИИЯФ МГУ)

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

Аннотация

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


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, May 27, 2020 at 16:20 via ZOOM. Meeting ID: 947 7456 3799. To connect to the conference, follow the link: https://cern.zoom.us/j/94774563799.The videoconferencing room will be opened from 15.50 (MSK) for testing.

:!: How to connect to ZOOM video conferencing can be found at the https://support.zoom.us/hc/en-us/categories/200101697 page. You can download the ZOOM application from the download link.

A.Kryukov, G.SHpiz (SINP MSU)

The problem of simplification of algebraic expressions with indices in computer algebra

Abstract

The report develops the authors' approach to the case when indexes in expressions can be divided into several sets acting in different namespaces. The simplest example of such a separation can be the superscripts and subscripts of tensor expressions. The main idea of ​​the proposed approach is the use of a (colored) structural graph to obtain a set of canonical names (numbers) of summation indices, which is defined up to an automorphism of the structural graph. After that, the construction of the canonical form of the expression with indices is reduced to the canonical form of the symbols included in it and the application of averaging operators associated with the group of atomorphisms of the structural graph.

Previous meetings/Предыдущие заседания

March 11, 2020/11 марта 2020 г.

А.Е.Панкратьев (МГУ им. М.В.Ломоносова, механико-математический факультет)

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

Аннотация

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

—————————————————————————————————

A.E.Pankratiev (Lomonosov Moscow State University)

The complexity of decision of the polynomial completeness of finite quasigroups

Abstract

Of particular interest in cryptographic applications are polynomially (functionally) complete algebraic structures, since the problem of deciding whether a system of equations over a functionally complete algebra is NP-complete. For this reason, cryptographic systems based on such structures are rather strong. In our talk we discuss the complexity of deciding the polynomial completeness of a finite quasigroup.

February 12, 2020/12 февраля 2020 г.

Paper

А.И.Зобнин (факультет компьютерных наук НИУ ВШЭ)

Линейная алгебра в задачах векторного представления слов

Аннотация

В прикладных задачах, связанных с автоматической обработкой текстов, слова заменяются действительными векторами сравнительно небольшой размерности, такими, что семантическая и синтаксическая близость слов соответствует геометрической близости векторов. Обычно такие векторы получаются из слоёв нейронной сети, или из низкоранговых разложений матриц. Мы рассмотрим две базовых модели построения таких векторов - SVD-разложение PPMI-матрицы и word2vec SGNS. Проанализировав первую модель, мы предложим модификацию второй модели, исключив из нее векторы контекстов. Для этого нам понадобятся теоремы из классической линейной алгебры.

—————————————————————————————————

A.I.Zobnin (Faculty of Computer Science, Higher School of Economics)

Linear algebra and word embeddings

Abstract

In natural text processing applications words are usually embedded into space of real vectors of relatively small dimension, such that the semantic and syntactic similarity of words corresponds to the geometric similarity of vectors. Usually such vectors are obtained from layers of the neural network, or from low-rank matrix decompositions.

We consider two basic models for constructing such embeddings: SVD of the PPMI matrix and word2vec SGNS. After analyzing the first model, we propose a modification of the second model, excluding context vectors from it. To do this, we use theorems from classical linear algebra.

January 10, 2020/10 января 2020 г.

А.А.Михалев (Механико-математический факультет МГУ имени М.В.Ломоносова)

Комбинаторика слов и стандартные базисы идеалов свободных алгебр

Аннотация

Мы обсудим приложения комбинаторики слов к проблеме построения стандартных базисов идеалов свободных (некоммутативных) алгебр многообразий линейных алгебр над полем. В качестве примеров будут рассмотрены свободная неассоциативная алгебра, свободные алгебры и супералгебры Ли.

—————————————————————————————————

A.A.Mikhalev (Faculty of Mechanics and Mathematics, M.V.Lomonosov Moscow State University)

Combinatorics of words and standard bases of ideals of free algebras

Abstract

We discuss applications of combinatorics of words to the problem to constract standard bases of ideals of free (noncommutative) algebras in varieties of linear algebras over a field. As examples we consider the free nonassociative algebra, free Lie algebras and superalgebras.

December 23, 2019/23 декабря 2019 г.

Slides

А.И.Овчинников

Определимость параметров в ОДУ при помощи дифференциальной алгебры

Аннотация

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


A.I.Ovchinnikov

Identifiability of parameters in ODEs with differential algebra

Abstract

ODEs with parameters appear widely in modeling. Parameter identifiability is a structural property of a model for recovering the values of parameters from the data. This property is a prerequisite for meaningful parameter identification in practice. We will discuss the basics of this using techniques from differential algebra. We will also address recently discovered subtleties in using parameter identifiability in practice and how we can overcome them with differential algebra.

November 27, 2019/27 ноября 2019 г.

Slides

C.Ф.Aдлай

Механическая интерпретация и эффективное вычисление эллиптических интегралов третьего рода

Аннотация

В недавней работе «замечание о круговых сечениях» (http://iitp.ru/upload/publications/8014/PlaneSection11.pdf) А.В. Селиверстовым было предложено расширенное толкование оси Галуа, которая (как отмечается в работе) была введена с целью иллюстрации критического движения трёхосного твёрдого тела. В работе также упоминается, что название (Галуа) было дано в связи с эллиптическими интегралами (третьего рода), которые могут быть наделены новой (механической) интерпретацией. Нашей целью станет дальнейшее прояснение этой связи и выявление «алгебраических свойств» эллиптического интеграла третьего рода, как «общего случая» эллиптического интеграла. Следует подчеркнуть, что арифметико-геометрическое среднее (АГМ), модифицированное арифметико-геометрическим среднее (МАГМ) и обобщённое арифметико-геометрическое среднее (ОАГМ) являются многозначными функциями, как и эллиптические интегралы, которые мы стремимся быстро вычислить, пользуясь точными «замкнутыми» формулами.


S.F.Adlaj

Mechanical interpretation and efficient computation of elliptic integrals of the third kind

Abstract

In a recent work «Note on circular sections» (http://iitp.ru/upload/publications/8014/PlaneSection11.pdf) A.V. Seliverstov proposed an extended interpretation of the Galois axis, which (as noted in this work) was introduced for illustrating the critical motion of a triaxial rigid body. He also indicates that the naming (Galois) was given in connection with elliptic integrals (of the third kind) which might be endowed with a new (mechanical) interpretation. Our goal is to further clarify this connection and to identify the «algebraic properties» of the elliptic integral of the third kind, being a «general case» of elliptic integrals. We emphasize that the arithmetic-geometric mean (AGM), the modified arithmetic-geometric mean (MAGM), as well as, the generalized arithmetic-geometric mean (GAGM) are multivalued functions, as are the elliptic integrals, which we aim to evaluate swiftly via exact «closed» formulas.

October 23, 2019/23 октября 2019 г.

Slides (Stefanescu), Slides (Gutnik)

1. Д.Штефанеску (Бухарестский университет, Румыния)

Вычислительные аспекты теории полиномов

Аннотация

Обсуждаются вычислительные проблемы получения границ для корней полиномов одной переменной с комплексными коэффициентами и получения оценок размера полиномиальных делителей. Здесь оказывается существенным вопрос о границах положительных корней полиномов с вещественными коэффициентами. В связи с этим обсуждаются границы, предложенные Лагранжем и Бретом. Излагаются полученные Серджеску обобщения оценок Брета и обобщение R+r-границ Лагранжа, данное Батра, Миньоттом и Штефанеску. Приводится краткое обоснование R+r-границ, устанавливаются вычислительные возможности результатов Лагранжа, обсуждаются подходы к их расширению.

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

2. С.А.Гутник (Московский физико-технический институт (национальный исследовательский университет))

Динамика движения спутника относительно центра масс с пассивными системами ориентации

Аннотация

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


1. D.Stefanescu (University of Bucharest, Romania)

Some computational aspects of polynomials

Abstract

We discuss some computational aspects concerning the bounding of roots of univariate polynomials with complex coefficients and on the estimation of the size of polynomial divisors.

We look to some bounds for positive roots of univariate polynomials with real coefficients. We shall discuss the bounds of Lagrange and Bret. Then we shall present the generalizations on Bret's bounds obtained by ive Sergescu and those of the bound R+r of Lagrange given by Batra-Mignotte-Stefanescu. We give a short proof of the bound R+r and we establish the computational quality of Lagrange's results and its improvements.

On the other hand we propose new bounds for the size of polynomial divisors of a univariate polynimial over the integers. These bounds are useful in polynomial factorization.

2. S.A.Gutnik (Moscow Institute of Physics and Technology)

The dynamics of satellite motion relative to the center of mass with passive orientation systems

Abstract

The report presents symbolic-numerical methods for studying the dynamics of a gyrostat satellite, a satellite subject to aerodynamic moment, constant moment, active control moment, and a satellite-stabilizer movement along a circuit orbit.

September 18, 2019/18 сентября 2019 г.

Slides

Заседание семинара было посвящено памяти С.Н.Перепечко.

А.В.Селиверстов (Институт проблем передачи информации им. А.А. Харкевича Российской академии наук)

Матрицы Гессе приводимых многочленов третьей степени

Аннотация

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


A.V.Seliverstov (Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute))

Hessian matrices of reducible third degree polynomials

Abstract

The report is aimed at describing some properties of Hessian matrices of polynomials over the field of real numbers. Let us consider a square-free third degree polynomial over the field of real numbers. If its Hessian matrix is definite at some real point, then the projective closure of the vanishing locus of this polynomial does not contain any real singular point at infinity. Moreover, for almost every reducible multivariate third degree polynomial over the field of real numbers, its Hessian matrix is definite at some real point if and only if the projective closure of the vanishing locus of the polynomial does not contain any real singular point at infinity.

April 24, 2019/24 апрель 2019 г.

Slides (Batkhin), Slides (Zima)

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

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

Аннотация

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

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

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

Аннотация

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


1. A.B.Batkhin (Keldysh Institute of Applied Mathematics of RAS)

Bifurcations of symmetric periodic solutions of a Hamiltonian system

Abstract

We consider an autonomous Hamiltonian system with two degrees of freedom, which canonical system is t-invariant under Klein four-group of linear canonical automorphisms of the extended phase space of the system. The sequence of symplectic transformations of monodromy matrix of a symmetric periodic solution is proposed. Three types of bifurcations of a family of symmetric periodic solutions - saddle-node bifurcation, pitch-fork bifurcation and period multiplying bifurcation - are investigated by means of these transformations. For last two types of bifurcations different scenarios are shown for the case of doubly symmetric periodic solutions of the Hill problem.

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

Factorial polynomials in computer algebra problems related to symbolic summation

Abstract

We introduce natural succinct representation for factorial polynomials along with the set of low complexity lazy manipulation and evaluation rules. This leads to immediate improvements of running-time complexity of many basic steps of standard algorithms of indefinite and definite summation.

February 20, 2019/20 февраля 2019 г.

Slides

Р.Р.Гонцов (Институт проблем передачи информации РАН)

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

Аннотация

Изучается вопрос разрешимости систем линейных дифференциальных уравнений в лиувиллевом смысле (или, в обобщенных квадратурах). Для произвольной системы этот вопрос эквивалентен вопросу разрешимости алгебры Ли дифференциальной группы Галуа системы. Однако, зависимость этой алгебры Ли от коэффициентов системы остается неизвестной. Мы показываем, что для класса систем с нерезонансными иррегулярными особыми точками, имеющих достаточно малые коэффициенты, проблема сводится к вопросу разрешимости явно заданной алгебры Ли, порожденной матрицами коэффициентов системы. Это утверждение дополняет соответствующий критерий Ильяшенко–Хованского разрешимости в квадратурах фуксовых систем с малыми коэффициентами. Также обсуждается возможность практической проверки полученных критериев разрешимости с использованием общих процедур, реализованных в Maple. Несмотря на достаточно алгебраическое описание, сам доклад будет носить скорее аналитический характер. Основан на совместных работах с И. Вьюгиным (ИППИ РАН, ВШЭ) и М. Баркату (Лиможский университет).


R.R.Gontsov (Institute for Information Transmission Problems of Russian Academy of Sciences)

Linear differential systems with small coefficients: various types of solvability and their verification

Abstract

We study the problem of solvability of linear differential systems in the Liouvillian sense (or, by generalized quadratures). For a general system, this problem is equivalent to that of solvability of the Lie algebra of the differential Galois group of the system. However, dependence of this Lie algebra on the system coefficients remains unknown. We show that for the particular class of systems with non-resonant irregular singular points that have sufficiently small coefficient matrices, the problem is reduced to that of solvability of the explicit Lie algebra generated by the coefficient matrices. This complements the corresponding Ilyashenko–Khovanskii theorem obtained for linear differential systems with Fuchsian singular points. We also give some examples illustrating the practical verification of the presented criteria of solvability by using general procedures implemented in Maple. The talk is based on the joint works with Ilya Vyugin (IITP RAS, HSE) and Moulay Barkatou (University of Limoges).

January 16, 2019/16 января 2019 г.

Slides

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

Приведённая нормальная форма периодической системы Гамильтона

Аннотация

Сначала рассматриваются линейные периодические системы Гамильтона. Для них находятся нормальные формы функций Гамильтона в комплексном и вещественном случаях. Обнаружена специфика вещественного случая. Затем находятся нормальные формы функций Гамильтона нелинейных периодических систем также в комплексном и вещественном случаях. Посредством дополнительного канонического преобразования координат такая нормальная форма всегда сводится к автономной системе Гамильтона, которая сохраняет все малые параметры и симметрии исходной системы. Её локальным семейством неподвижных точек соответствуют семейства периодических решений исходной системы. Всё это завершает исследование титульной проблемы, частично изложенное в гл. II книги А.Д.Брюно «Ограниченная задача трёх тел», М.: Наука, 1990. Рассматривается нетривиальный пример с двумя степенями свободы. Будет указана связь с компьютерной алгеброй.


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

Reduced normal form of the periodic Hamiltonian system

Abstract

First we consider the linear periodic Hamiltonian systems. For them we find normal forms of Hamiltonian functions in both complex and real cases. The real case has a specificy. Then we find normal forms of the Hamiltonian functions for nonlinear periodic systems also in complex and real cases. By means of additional canonical transformation of coordinates, such system always is reduced to an autonomous Hamiltonian system, which preserves all small parameters and symmetries of the initial system. Its local families of stationary points correspond to families of periodic solutions of the initial system. All that concludes the study of the problem mentioned in the title and partially given in Ch. II of the book A.D.Bruno «The Restricted 3-Body Problem». Berlin. Walter de Grouter, 1994. We consider a nontrivial example with two degrees of freedom. A connection with Computer Algebra will be given.

December 26, 2018/26 декабря 2018 г.

Slides

Н.Н.Осипов (Сибирский федеральный университет, г. Красноярск)

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

Аннотация

В 1887 г. немецкий математик Карл Рунге предложил эффективный метод решения диофантовых уравнений f(x,y)=0 с двумя неизвестными в целых числах. Этот метод опирается на разложения в ряды Пюизо ветвей алгебраической функции, определяемой данным уравнением. Несмотря на эффективность метода, явные оценки для решений (x,y) содержат слишком большие константы, что делает практически бесполезными переборные алгоритмы решения даже в случае уравнений малой степени. Отчасти поэтому в современных системах компьтерной алгебры (Maple, Mathematica и т.п.) отсутствуют модули для решения таких диофантовых уравнений. В докладе будет рассказано об алгоритмизации элементарной версии метода Рунге для кубических диофантовых уравнений, которая не использует разложения в ряды и допускает эффективную компьютерную реализацию.


N.N.Osipov (Siberian Federal University, Krasnoyarsk)

An algorithmic implementation of an elementary version of Runge's method for cubic diophantine equations

Abstract

In 1887 the german mathematician Carl Runge proposed an effective method for solving diophantine equations f(x,y)=0 with two unknowns in integers. This method relies on the Puiseux expansions of the branches of the algebraic function defined by the given equation. Despite the effectiveness of the method, the explicit estimates for the solutions (x,y) contain too large constants, making the full search solving algorithms practically useless even in the case of equations of small degree. Partly therefore in modern systems of computer algebra (Maple, Mathematica, etc.) there are no modules for solving such diophantine equations. In the talk we will describe the algorithmization of an elementary version of Runge's method for cubic diophantine equations, which does not use any series expansions and allows for efficient computer implementation.

November 28, 2018/28 ноября 2018 г.

Slides (Panferov), Slides (Tyutyunnik)

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

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

Аннотация

Особенностью символьных алгоритмов построения решений дифференциальных систем является то, что они позволяют получать только такие решения, все компоненты которых имеют заранее определённый вид: вид многочленов, рациональных функций, рядов и пр. При построении частичных решений дифференциальных систем, когда интерес представляют не все, а только выделенная часть неизвестных, использование общих процедур не всегда приводит к нужному результату. Известный алгоритм Абрамова-Бронштейна, применимый к нормальным дифференциальным системам вида y'=Ay, позволяет обходить возникающие трудности. Для обобщения этого алгоритма на случай линейных дифференциальных систем произвольного порядка предлагается алгоритм Extract. Дополнительно для систем с выделенными неизвестными вводится понятие сателлитных неизвестных, т.е. неизвестных, вид компонент решений для которых схож с видом выделенных компонент решений. Предлагаются алгоритмы распознавания сателлитных неизвестных. Применение этих алгоритмов позволяет при частичном построении решений дифференциальных систем без больших дополнительных затрат также находить и решения для сателлитных неизвестных. Предложенные алгоритмы реализованы в среде компьютерной алгебры Maple.

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

Символьно-численное исследование векторной модели волноводного распространения электромагнитного излучения (по материалам кандидатской диссертации)

Аннотация

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


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

Algorithms for symbolic computation in computer algebra systems for linear differential systems with selected unknowns

Abstract

A feature of symbolic algorithms for constructing solutions to differential systems is that they only allow to get such solutions, all components of which have a specified form: polynomials, rational functions, power series, etc. During construction of partial solutions to differential systems, when not all unknowns are of interest, but only a selected part of them, the use of general procedures does not always lead to the desired result. The well-known Abramov-Bronstein algorithm, applicable only to normal differential systems of the form y '= Ay, makes it possible to overcome these difficulties. To generalize this algorithm to the case of linear differential systems of arbitrary order, the Extract algorithm is proposed. Additionally, for systems with selected unknowns the concept of satellite unknowns is introduced. An unselected unknown is called satellite for the set of selected unknowns if the form of corresponding solution component is similar to the form of the selected solution components. Satellite unknowns recognition algorithms are proposed. The use of these algorithms allows to obtain solutions for satellite unknowns without large additional costs. The proposed algorithms are implemented in the Maple.

2. A.A.Tyutyunnik (Peoples’ Friendship University of Russia (RUDN University))

Symbolic-numerical investigation of the vector model of waveguide propagation of electromagnetic radiation (Materials of PhD thesis) tyutyunnik181128.pdf

Abstract

The report presents and analyzes the method of four potentials for solving waveguide problems in a full vectorial formulation. Based on the method of four potentials, a symbolic-numerical algorithm for solving the spectral problem of finding normal modes for regular waveguides is developed and realized in the computer algebra system Maple. The problems of wave diffraction at the junction of two waveguides and long irregularities in integrated optical waveguides are formulated and solved numerically using the developed algorithm. Calculations for the problem of diffraction on a Luneberg waveguide lens are given. The obtained results are verified by comparison with exact solutions in model structures and with results obtained by other authors.

October 24, 2018/24 октября 2018 г.

Slides (Gerdt), Slides (Sukhovyh)

1. В.П.Гердт (Лаборатория информационных технологий Объединенного Института Ядерных Исследований, Дубна)

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

Аннотация

(Совместная работа с М.Ланге–Хегерманом и Д.Робертцом)

Мы представим в докладе основные алгоритмические аспекты и реализацию в системе Maple декомпозиции Томаса для полиномиально – нелинейных дифференциальных уравнений и систем таких уравнений, которые могут также включать неравенства вида p≠0, на конечное множество дифференциально треугольных и алгебраически простых инволютивных подсистем. Обычно, такая декомпозиция облегчает исследование и построение решений как аналитически, так и численно. Отличительной особенностью декомпозиции Томаса является то, что решения ее подсистем не пересекаются, т.е. образуют разбиение пространства решений исходной системы. В частности, решение корректно поставленной начальной задачи принадлежит одной и только одной из подсистем, получающихся в результате декомпозиции. Декомпозиция Томаса является полностью алгоритмической. Она позволяет получить следующие важные результаты алгебраического анализа дифференциальных систем: проверить совместность, т.е. существование общих решений уравнений системы; определить (локальный) произвол в общем аналитическом решении; для заданного уравнения установить удовлетворяется ли оно на всех общих решениях исходной системы; исключить часть зависимых переменных, если такое исключение возможно; выявить скрытые связи для зависимых переменных и др. Материал доклада будет проиллюстрирован примерами использования декомпозиции Томаса.

2. В.И.Суковых (DataArt, Факультет компьютерных наук ВГУ, Воронеж)

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

Аннотация

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

Такие задачи, несмотря на естественный прикладной характер, по-видимому, не исследованы в литературе. Билинейная система, полученная из задачи об однородности, освобождается от параметров и сводится к большой системе полиномиальных уравнений. Основным результатом является оценка «количества» решений таких (билинейных и полиномиальных) систем. Показано, что множество решений задачи об однородности (т.е. семейство голоморфно-однородных строго псевдо-выпуклых вещественных гиперповерх-ностей) определяется не более чем 13 вещественными тейлоровскими коэффициентами из нормальных уравнений рассматриваемых поверхностей.


1. V.P.Gerdt (Laboratory of Information Technologies, Joint Institute for Nuclear Research, Dubna)

Thomas decomposition of differential systems and its implementation in Maple

Abstract

(Joint work with Markus Lange-Hegermann and Daniel Robertz)

We present the basic algorithmic features and implementation in Maple of the Thomas decomposition of polynomial nonlinear differential systems, which in addition to equations may contain inequations, into a finite set of differentially triangular and algebraically simple subsystems whose subsets of equations are involutive. Usually the decomposed system is substantially easier to investigate and solve both analytically and numerically. The distinctive property of a Thomas decomposition is disjointness of the solution sets of the output subsystems. Thereby, a solution of a well-posed initial problem belongs to one and only one output subsystem. The Thomas decomposition is fully algorithmic. It allows to perform important elements of algebraic analysis of an input differential system such as: verifying consistency, i.e., the existence of solutions; detecting the arbitrariness in the general analytic solution; given an additional equation, checking whether this equation is satisfied by all common solutions of the input system; eliminating a part of dependent variables from the system if such elimination is possible; revealing hidden constraints on dependent variables, etc. Examples illustrating the use of the differential Thomas decomposition are given.

2. V.I.Sukhovyh (DataArt, Depatrment of Computer Science VSU, Voronezh)

Computer algorithms and symbolic calculations in the problem of coefficients classification for homogeneous surfaces

Abstract

The problem of classification is studied in report (with the use of a Maple package of symbolic mathematics) for homogeneous real hypersurfaces of a 3-dimensional complex space.The information model of this problem is a system of bilinear equations with respect to two large groups of variables; one of the groups contains the so-called free parameters.

Such problems, despite their natural applied character, apparently do not have been investigated in the literature. The bilinear system,obtained from the homogeneity problem, is exempted from the parameters and reduces to a large system of polynomial equations. The main result is the estimationof the «number» of solutions of such (bilinear and polynomial) systems. It is shown that the set of solutions of the homogeneity problem (that is, the family of holomorphically homogeneous strictly pseudo-convex real hypersurfaces) is determined by no more than 13 real Taylor coefficients from the normal equations of the surfaces under consideration.

September 26, 2018/26 сентября 2018 г.

Slides

С.В.Пославский (НИЦ «Курчатовский Институт» - ИФВЭ, Протвино)

Rings: эффективная JVM библиотека для коммутативной алгебры

Аннотация

Rings это эффективная библиотека для коммутативной алгебры, написанная на языках программирования Java и Scala. Арифметика в кольцах полиномов, вычисление наибольших общих делителей, факторизация полиномов, а также построение базисов Гребнера, имплементированы с использованием современных асимптотически быстрых алгоритмов. Rings можно легко использовать или встраивать в приложения с использованием простого API с полностью типизированной иерархией алгебраических структур и алгоритмов для коммутативной алгебры. Язык Scala позволяет использовать оригинальную и мощную концепцию функционального программирования с полной статической типизацией, что дает возможность писать краткий выразительный и быстрый код для приложений. В то же время Rings показывает одну из лучших производительностей среди программ для алгебраических вычислений. Специальное внимание в докладе будет уделено вопросам импелементации, бенчмаркам и приложениям библиотеки в вычисления в физике высоких энергий.


S.V.Poslavsky (NRC «Kurchatov Institute» - IHEP Protvino)

Rings: efficient JVM library for commutative algebra

Abstract

Rings is an efficient lightweight library for commutative algebra written in Java and Scala languages. Polynomial arithmetic, GCDs, polynomial factorization and Groebner bases are implemented with the use of modern asymptotically fast algorithms. Rings can be easily interacted or embedded in applications via a simple API with fully typed hierarchy of algebraic structures and algorithms for commutative algebra. The use of the Scala language brings a quite novel powerful, strongly typed functional programming model allowing to write short, expressive, and fast code for applications. At the same time Rings shows one of the best performances among existing software for algebraic calculations. Specific attention in the talk will be paid to the implementational aspects, benchmarks and applications of the library in typical computations in high-energy physics.

April 18, 2018/18 апреля 2018 г.

Slides (Panferov), Slides (Varin)

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

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

Аннотация

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

Алгоритм Абрамова-Бронштейна (AB-алгоритм) для нормальных дифференциальных систем первого порядка (y'=Ay) с выделенными неизвестными позволяет построить новую нормальную дифференциальную систему первого порядка, неизвестными которой являются только выделенные неизвестные исходной системы и их производные.Полученная система помогает отвечать на многие вопросы, формулируемые для первоначальной системы с выделенными неизвестными.Но к линейным дифференциальным системам высоких порядков AB-алгоритм напрямую не применим. Предлагается алгоритм Extract, обобщающий AB-алгоритм на линейные дифференциальные системы произвольных порядков полного ранга.

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

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

2. В.П.Ваpин (ИПМ им. М.В. Келдыша)

Факториальное преобразование некоторых классических комбинаторных последовательностей

Аннотация

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


1. A.A.Panferov (Dorodnicyn Computing Centre, Federal Research Center «Computer Science and Control» of RAS, Department of Computational Mathematics and Cybernetics, MSU)

Algorithms of computer algebra for linear differential systemswith selected unknowns

Abstract

We consider linear differential systems some unknowns in which are selected. Such systems appears in problems where not all system unknowns are of interest, but only a part of them, e.g., in the problem of searhing partial solutions to the system, in the problem of partial stability, and in other applied and theoretical problems.

The Abramov-Bronshtein algorithm (AB-algorithm) for first-order normal differential systems (y'= Ay) with selected unknowns makes it possible to construct a new normal differential system whose unknowns are only the selected unknowns of the original system and their derivatives. The resulting system helps to answer many questions formulated for the original system with selected unknowns. However, the AB-algorithm is not directly applicable to the linear differential systems of high orders. We propose the Extract algorithm that generalizes the AB-algorithm to full rank linear differential systems of arbitrary orders.

Also, we introduce the concept of satellite unknowns for systems with selected unknowns. Unselected unknowns are called satellite if theirs values are functions (or elements of some differential field) that are similar in their properties to the values of the selected unknowns. Algorithms for recognizing satellite unknowns among all unselected unknown systems and some possible applications of these algorithms are discussed.

The presented algorithms are implemented in Maple.

2. V.P.Varin (Keldysh Institute of Applied Mathematics, Moscow)

Factorial transformation for some classical combinatorial sequences

Abstract

Factorial transformation known from Euler's time is a very powerful tool for summation of divergent power series. We use factorial series for summation of ordinary power generating functions for some classical combinatorial sequences. These sequences increase very rapidly, so OGFs for them diverge and mostly unknown in a closed form. We demonstrate that factorial series for them are summable and expressed in known functions. We consider among others Stirling, Bernoulli, Bell, Euler and Tangent numbers. We compare factorial transformation with other summation techniques such as Pade approximations, transformation to continued fractions, and Borel integral summation. This allowed us to derive some new identities for GFs and express integral representations of them in a closed form.

February 28, 2018/28 февраля 2018 г.

Slides

С.А.Гутник (Московский физико-технический институт)

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

Аннотация

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


S.A.Gutnik (Moscow Institute of Physics and Technology)

Application of Computer Algebra Methods to Investigation of Influence of Aerodynamic Torque on Satellite Dynamics

Abstract

Methods of computer algebra are used to study the properties of nonlinear algebraic system that determines the equilibrium orientations of a system of two bodies connected by a spherical hinge moving along a circular orbit under the action of gravitational torque. To determine the equilibrium orientations of a bunch of two bodies, the system consisting of twelve stationary algebraic equations was decomposed, using linear algebra methods and an algorithm for the construction of a Groebner basis. The number of equilibria depending on the parameters of the problem is found by the analysis of the real roots of algebraic equations from the constructed Groebner bases. Evolution of conditions of equilibria existence in the space of parameters is carried out using symbolic – numerical approach. Computer algebra system Maple was used.

January 31, 2018/31 января 2018 г.

Slides

А.В.Климаков, А.А.Михалев (Механико-математический факультет Московского государственного университета имени М.В.Ломоносова)

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

Аннотация

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


A.V.Klimakov, A.A. Mikhalev (Faculty of Mechanics and Mathematics, M.V.Lomonosov Moscow State University)

Homogenious almost primitive elements of free algebras of Schreier varieties

Abstract

A variety of linear algebras is Schreier if any subalgebra of a free algebra of this variety is free. An element of a free algebra is primitive if it has a complement with respect to a free generating set. An element of a free algebra of a Schreier variety is almost primitive if it is not primitive in the whole free algebra, but it is primitive in any proper subalgebra which contains it. We construct algorithms to recognize homogenious almost primitive elements.

December 27, 2017/27 декабря 2017 г.

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

1. Д.В.Диваков, М.Д.Малых, Л.А.Севастьянов, А.А.Тютюнник (Российский университет дружбы народов)

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

Аннотация

В докладе представлен способ вычисления нормальных мод волновода в полной векторной постановке и его реализация в CAS Maple. В работах авторов доклада система уравнений Максвелла для волноводного распространения электромагнитного излучения была редуцирована к эквивалентной системе дифференциальных уравнений для четырех скалярных «потенциалов». Граничные уравнения Максвелла редуцированы к граничным условиям для потенциалов. Система уравнений для собственных мод волновода приведена к виду обобщенной задачи на собственные значения и собственные векторы.

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

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

2. А.Овчинников (Городской университет Нью-Йорка)

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

Аннотация

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


1. D.Divakov, M.Malykh, L.Sevastianov, A.Tiutiunnik (Peoples’ Friendship University of Russia (RUDN University))

Method for calculating the normal modes of an optical waveguide in the vector case in the computer algebra system Maple

Abstract

The report presents a method for calculating the normal modes of a waveguide in a full vectorial formulation and its implementation in CAS Maple. In the authors' approach Maxwell's equations for the waveguide propagation of electromagnetic radiation was reduced to equivalent system of differential equations for four scalar «potentials». The Maxwell boundary conditions are reduced to the boundary conditions for the potentials. The system of equations for the eigenmodes of a waveguide is reduced to the form of a generalized eigenvalue and eigenvector problem.

This report presents a solution to this problem, based on the incomplete Galerkin method (truncation of the basis), and investigation of the dependence of the solutions obtained on the parameters of the waveguide. The matrices of the truncated finite-dimensional eigenvalue and eigenvector problem are computed in a symbolic form in the computer algebra system Maple. The structure of resulting sparse matrices (including depending on the dimension) and the dependence of the matrix elements on the parameters of the waveguide are analyzed.

The search for the eigenvalues of the truncated problem is performed by numerical methods in the computer algebra system Maple. The dependence of the obtained eigenvalues on the parameters of the waveguide is analyzed, the error analysis and stability of the calculated values are analyzed depending on the size of the truncation. Verification of the results obtained by symbolic-numerical methods is carried out using examples of waveguides that admit exact solutions to the eigenmode problem.

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

Elimination of unknowns for systems of difference and differential equations and its applications

Abstract

We will discuss effective elimination theorems for systems difference equations. We will compare these with recent effective elimination theorems for systems of differential equations. We will also discuss applications of elimination to parameter identification problems that arise in models given by differential and difference equations.

October 18, 2017/18 октября 2017 г.

Slides

Заседание семинара было посвящено памяти Виталия Александровича Ростовцева (23.05.1932-19.09.2017).

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

О доказательной программе арифметики дробей для общего случая

Аннотация

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

Описываются главные черты программы, которая воплощает все три подхода к арифметике дробей в общем случае, и при этом содержит удостоверение – полные формальное доказательства 1) правильности каждого из трёх способов сложения, умножения и деления дробей, 2) того, что эти алгоритмы задают структуру поля на Q. Эти определения и доказательства «понимаются» компилятором и автоматически им проверяются до начала исполнения программы.

Эта программа является частью большой библиотеки DoCon-A доказательных программ для алгебры (http://www.botik.ru/pub/local/Mechveliani/docon-A/), написанной докладчиком на языке Agda. Приблизительно можно считать, что Agda есть (чисто функциональный) язык Haskell, расширенный средством зависимых типов.


The session of the seminar was dedicated to the memory of Vitaly Rostovtsev (23.05.1932-19.09.2017).

S.D.Meshveliani (Ailamazyan's Program Systems Institute of RAS, Pereslavl-Zalessky, Russia)

Provable generic programming for arithmetic of fractions

Abstract

It is described a provable program for a generic arithmetic of fractions. This is a small part of the project DoCon-A of certified programs for a computer algebra library (http://www.botik.ru/pub/local/Mechveliani/docon-A/).

In this system, functional programs for known algebraic methods are written together with proofs, and proofs are automatically checked by the compiler (see the Coq and Agda systems).

The used language (Agda) is purely functional and includes the feature of dependent types. There are described the design principles for certified programs for arithmetic of fractions over a) any domain with gcd, b) any unique factorization domain.

September 13, 2017/13 сентября 2017 г.

Extended Abstract

А.В.Парусникова (НИУ ВШЭ, Департамент прикладной математики)

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

Аннотация

В данной работе изучаются асимптотики третьих трансцендентов Пенлеве при параметрах γ=0, α,β,δ∈C, α,δ≠0 в секторах с вершинами в бесконечности и углами раствора меньше 2π. Получено семейство параметров третьего уравнения Пенлеве, при которых эти ряды Пюизо - рассмотренные как ряды от z(2/3) - являются рядами Жевре точного порядка один и, как следствие, расходятся. Найдены аналитические функции, которые приближаются по Жевре порядка один данными рядами в секторах с вершинами в бесконечности и углами раствора меньше π.

Доклад основан на совместных работах с А.В. Васильевым:

A.V.Parusnikova, A.V.Vasilyev. On Divergence of Puiseux Series Asymptotic Expansions of Solutions to the Third Painlevé Equation. arXiv:1702.05758.

А.В.Васильев, А.В.Парусникова, “Различные подходы к выявлению асимптотик решений третьего уравнения Пенлеве в окрестности бесконечности”, Дифференциальные уравнения. Математическая физика, Итоги науки и техн. Сер. Соврем. мат. и ее прил. Темат. обз., 139, ВИНИТИ РАН, М., 2017, 70–78


A.V.Parusnikova (NRU HSE, Department of Applied Mathematics)

On Divergence of Puiseux Series Asymptotic Expansions of Solutions to the Third Painlevé Equation

Abstract

In this paper we study the third Painlevé equation with the parameters γ=0, α,β,δ∈C, α,δ≠0. As we showed earlier, Puiseux series formally satisfying this equation - considered as series of z(2/3) - asymptotically approximate of Gevrey order one solutions to this equation in sectors with the vertices at infinity. We present a family of values of the parameters such that these series are series of exact Gevrey order one, and hence diverge. We prove the 1-summability of them and provide analytic functions which are approximated of Gevrey order one by these series in sectors with the vertices at infinity.

The talk is based on our joint works with Andrey V. Vasilyev

A.V.Parusnikova, A.V.Vasilyev. On Divergence of Puiseux Series Asymptotic Expansions of Solutions to the Third Painlevé Equation. arXiv:1702.05758.

A.V.Vasilyev, A.V.Parusnikova. On various approaches to asymptotics of solutions to the third Painlevé equation in a neighborhood of infinity. Itogi Nauki i Techniki. Sovremennaya matematika i ee prilojeniya. Tematicheskie obzory 139, 2017, 70-79 (Russian). To be translated in «Journal of Mathematical Sciences».

Archive/Архив

start.1590151641.txt.gz · Последние изменения: 2020/05/22 15:47 — sa
 
За исключением случаев, когда указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: Public Domain
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki