21-22 мая 2013 года состоялся традиционный совместный семинар - фактически, двухдневная конференция - с Лабораторией информационных технологий ОИЯИ (Дубна).
The traditional joint meeting with the seminar of Laboratory of Information Technologies of JINR (Dubna) was held on May 21st-22nd, 2013. Essentially, this was a two-days conference.
Extended Abstract (Mikhalev), Slides (Gutnik et al.)
Это заседание семинара посвящено памяти Лешека Гадомского (25.12.1953-09.04.2013).
1. А.А.Михалев (Мехмат МГУ)
ПБВ-пары многообразий линейных алгебр и символьные вычисления в свободных алгебрах
Аннотация
Рассматривается понятие ПБВ-пары многообразий линейных алгебр над полем. Если (V,W) - ПБВ-пара многообразий и многообразие V шрайерово, то W - также шрайерово многообразие. Аналогичные результаты справедливы для теоремы о свободе и для проблемы равенства. Если V(X) и W(X) - свободные алгебры с множеством X свободных образующих многообразий V и W соответственно, то алгебра V(X) является универсальной обертывающей алгеброй для алгебры W(X). В случае, когда V(X) - свободная неассоциативная алгебра, это дает возможность для построения алгоритмов символьных вычислений в алгебре W(X) (распознавание автоморфизмов, примитивных элементов, построение нормальных форм элементов и стандартных базисов идеалов). Доклад основан на статье А.А.Михалева и И.П,Шестакова.
2. С.А.Гутник (МФТИ), В.А.Сарычев (ИПМ им. М.В.Келдыша РАН)
Символьно-численные методы исследования динамики спутника-гиростата
Аннотация
Исследована динамика спутника-гиростата, движущегося в центральном ньютоновом силовом поле по круговой орбите. Предложен метод определения всех положений равновесия спутника-гиростата в орбитальной системе координат при заданных значениях вектора гиростатического момента и главных центральных моментов инерции и получены условия их существования в зависимости от четырех безразмерных параметров системы. Найдены бифуркационные значения параметров, при которых изменяется число положений равновесия. Проведен детальный численный анализ эволюции областей существования различного числа равновесий в пространстве безразмерных параметров. Рассмотрена взаимосвязь полученных областей существования с областями существования равновесий осесимметричного спутника. Показано, что число положений равновесия спутника-гиростата в общем случае не превышает 24 и не может быть меньше 8 а число устойчивых равновесий изменяется от 4 до 2.
This session of the seminar is dedicated to the memory of Leszek Gadomski (25.12.1953-09.04.2013).
1. A.A.Mikhalev (Department of Mathematics and Mechanics, MSU)
PBW-pairs of varieties of linear algebras and symbolic computation in free algebras
Abstract
The notion of a PBW-pair of varieties of linear algebras over a field is under consideration. If (V,W) is a PBW-pair of varities and V is Schreier, then so is W. Similar results are also true for Freiheitssatz and Word problem. If V(X) and W(X) are free algebras with the set X of free generators of the varieties V and W, respectively, then V(X) is the universal enveloping algebra of W(X). In the case where V(X) is a free nonassociative algebra it gives a possibility to construct algorithms for symbolic computation in the algebra W(X) (recognizing automorphisms, primitive elements, constructing of normal forms of elements and standard bases of ideals). The talk is based on the article by A.A.Mikhalev and I.P.Shestakov.
2. S.A. Gutnik (Moscow Institute of Physics and Technology (University)), V.A.Sarychev (Keldysh Institute of Applied Mathematics, Russian Academy of Sciences)
Symbolic-Numerical Investigation of Gyrostat Satellite Dynamics
Abstract
Dynamics of gyrostat satellite moving along a circular orbit in the central Newtonian gravitational field is studied. A symbolic-numerical method for determination of all equilibrium orientations of gyrostat satellite in the orbital coordinate system with given gyrostatic torque and given principal central moments of inertia is proposed. A computer algebra method based on the algorithm for the construction of a Groebner basis and the resultant concept for solving the problem is used. All bifurcation values of parameters at which there is a change of numbers of equilibrium orientations are determined. Evolution of domains in the space of parameters of the system which correspond to various numbers of equilibria are carried out numerically in detail. The stability analysis of equilibria is performed on the basis of Lyapunov's theorem. It is shown that the number of equilibria of the gyrostat satellite in general case not be less than 8 and not more than 24 and number of stable equilibria changes from 4 to 2.
Slides (Galkin) Slides (Abramov et al.)
1. В.В.Галкин (Мехмат МГУ)
Сигнатурные алгоритмы вычисления базисов Грёбнера для решения полиномиальных систем
Аннотация
Одним из универсальных методов решения полиномиальных систем уравнений от нескольких переменных является использование базисов Грёбнера. Их применение к практическим задачам с приближёнными входными данными затруднено двумя причинами: практической - большим временем работы алгоритмов, и теоретической - трудностью определения понятия равенства нулю приближённого коэффициента. Проблема сложности вычислений в определённой степени решается сигнатурными алгоритмами. Доклад рассматривает предложенный Фожером сигнатурный алгоритм F5 и представляет свойства выбираемых в нём многочленов, позволяющие как получить доказательство его остановки, так и сформулировать новый сигнатурный алгоритм, обладающий простым обоснованием и реализацией. Решение проблемы определения равенства нулю приближённых коэффициентов начинается со введения строгого понятия приближённых вычислений и классификации возможных типов близких к нулю элементов. После этого она решается применительно к введённому ранее сигнатурному алгоритму двумя дополняющими друг друга довольно общими способами, специальным образом приспособленными к данной задаче. Во-первых, строится вероятностная модулярная методика, позволяющая избежать вычислительно-затратных расчётов в рациональных числах, и даётся явное правило выбора простого модуля, позволяющее получить корректный результат в этом вероятностном методе с вероятностью не менее заданной. Вторым является метод замены мономов переменными (TSV), позволяющий «переставлять назад» старший коэффициент многочлена путём обозначения старшего монома за новую переменную, и находящий в итоге базис Грёбнера в некотором расширенном кольце многочленов. Предлагается адаптация данного метода, позволяющая проводить рассмотренный сигнатурный алгоритм таким образом, что после добавления новых переменных не требуется запуск вычислений сначала, в отличие от применений TSV к другим сигнатурным алгоритмам. В завершении описывается способ использования расширенного базиса, построенного таким образом, к решению исходной задачи в множестве многочленов без дополнительных переменных.
2. С.А.Абрамов (Вычислительный центр РАН), М.А.Баркату (Лиможский университет), Д.Е.Хмельнов (Вычислительный центр РАН)
О дифференциальных системах полного ранга с коэффициентами в виде степенных рядов
Аннотация
Рассматривается следующая задача: дана система линейных обыкновенных дифференциальных уравнений произвольного порядка с коэффициентами в виде формальных степенных рядов, требуется установить, имеет ли система ненулевые решения в виде лорановых рядов, и найти все такие решения если они существуют (в усеченном виде с сохранением размерности пространства таких решений). Предполагается, что ряды, представляющие собой коэффициенты исходной системы, заданы алгоритмами вычисления коэффициентов; таким образом, мы в общем случае не можем сказать, является ли данный ряд нулевым. Рассматриваемая задача оказывается алгоритмически неразрешимой. Тем не менее, мы показываем, что она разрешима в случае, когда мы заранее знаем, что данная система имеет полный ранг.
Доказано кроме этого, что ширина данной системы полного ранга S с коэффициентами в виде формальных степенных рядов может быть найдена алгоритмически, при этом ширина системы S определяется как наименьшее неотрицательное целое число w такое, что любое l-усечение S с l>=w является системой полного ранга. (Если a(x) = a_0 + a_1 x a_2 x^2 + … - формальный степенной ряд, l - неотрицательное целое, то полином a_0 + a_1 x +a_2 x^2 + … + a_l x^l является l-усечениием a(x); l-усечение системы S - это система, коэффициенты которой суть l-усечения соответствующих коэффициентов S. Пример системы S полной ранга и неотрицательного целого l таких, что l-усечение системы S имеет полный ранг, а ее (l+1)-усечение - нет, дается в докладе. Однако мы показываем, что указанное значение w существуют для любой системы полного ранга.)
Предлагаемые алгоритмы реализованы в Maple.
1. V.V.Galkin (Department of Mathematics and Mechanics, MSU)
Gröbner basis signature-based algorithms for solving polynomial systems
Abstract
One of the methods for solving polynomial systems in several variables is the use of Gröbner bases. Their application to problems with approximate input data is difficult for two reasons. The practical reason is slow computations. The theoretical reason arises from the difficulty of the zero-equality concept applied to approximate coefficients. The problem of computational complexity is partially solved by signature-based algorithms. The paper analyzes the Faugère's signature algorithm F5 and shows the properties of polynomials the algorithm choose. This leads to the proof of F5 termination and to formulation of a new signature-based algorithm, which has a simple proof and implementation. The investigation in the area of approximate zero coefficients begins with the introduction of a strict notion of approximate calculations and classification of near-zero elements. In the next step the problem of zero-equality is solved for the previously introduced signature algorithm, with two complementing each other quite general methods which are specially adapted to the task. The first method is based on the probabilistic modular technique for avoiding computationally expensive calculations in rational numbers, and give an explicit rule for choosing a prime module that allows to get the correct result in the probabilistic method with a probability greater than given. The second is the term substitutions with variables (TSV) method which allows «swap back» leading coefficient by renaming the leading monomial to a new variable, and eventually finding a Gröbner basis in some extended polynomial ring. This method's adaptation is proposed to allow the considered signature algorithm to continue after adding new variables without the need to run the calculations from scratch, unlike the TSV's applications to other signature algorithms. Finally the paper describes how to apply extended basis computed by TSV for solving the original problem in a set of polynomials without additional variables.
2. S.A.Abramov (Computing Centre of the Russian Academy of Science), M.A.Barkatou (Limoges University), D.E.Khmelnov (Computing Centre of the Russian Academy of Science)
On full rank differential systems with power series coefficients
Abstract
We consider the following problem: given a linear ordinary differential system of arbitrary order with formal power series coefficients, decide whether the system has non-zero Laurent series solutions, and find all such solutions if they exist (in a truncated form preserving the space dimension). If the series coefficients of the original systems are represented algorithmically (thus we are not able, in general, to recognize whether a given series is equal to zero or not) then these problems are algorithmically undecidable. However, it turns out that they are decidable in the case when we know in advance that a given system is of full rank.
We prove additionally that the width of a given full rank system $S$ with formal power series coefficients can be found algorithmically, where the width of S is the smallest non-negative integer w such that any l-truncation of S with l>=w is a full rank system. (If a(x)=a_0+a_1 x+a_2 x^2+ … is a formal power series, l is a non-negative integer then the polynomial a_0 + a_1 x + a_2 x^2+ … + a_l x^l is the l-truncation of a(x); the l-truncation of S is the system whose coefficients are the l-truncations of corresponding coefficients of S. An example of a full rank system S and a non-negative integer l such that l-truncation of S is of full rank while its (l+1)-truncation is not, is given in the talk; however it is shown as well that the mentioned value w exists for any full rank system.)
We propose corresponding algorithms and their Maple implementation, and report some experiments.
М.Н.Геворкян (аспирант факультета физико-математических и естественных наук, Российский университет дружбы народов)
Анализ составных симплектических методов и симплектических методов семейства Рунге-Кутты для протяженных во времени задач
Аннотация
Цель работы: оценка применимости симплектических численных методов к различным задачам, оценка точности сохранения различных физически значимых инвариантов (полная энергия, момент импульса и т.д.)
При разработке классических численных методов основное внимание уделяется уменьшению локальной ошибки вычислений. Однако по мере усложнения решаемых задач возникла необходимость производить вычисления для протяженных во времени процессов. В таких задачах проявился недостаток классических методов давать верную локальную картину, но искажать общую (например, не сохранялась полная энергия системы). В связи с этим начали развиваться геометрические интеграторы, которые учитывали геометрические структуры решаемой задачи. В случае гамильтоновой механики такими методами являются симплектические численные методы.
Симплектическими численными методами называются такие численные схемы, каждая итерация которых в точности сохраняет симплектическую структуру уравнений Гамильтона (симплектическую 2-форму). Достоинство таких методов в том, что погрешность вычисления инвариантов системы не растет со временем, а изменяется в очень ограниченных пределах. Благодаря этому свойству симплектические численные методы нашли применение в небесной механике, молекулярной динамике и компьютерной анимации.
В докладе дается краткий обзор симплектических методов и представлены некоторые теоретические результаты, касающиеся условий симплектичности при композиции раздельного метода Рунге–Кутты со своим присоединенным. Также записан составной симплектический метод для ограниченной задачи трех тел, который не сводится к методу типа Рунге–Кутты. Проведено сравнение различных симплектических методов (раздельные методы Рунге–Кутты, методы Рунге–Кутты–Нюстрёма, различные составные методы) и оценка точности сохранения инвариантов (полная энергия, момент импульса, вектор Лапласа–Рунге–Ленца).
M.N.Gevorkyan (Department of Physics, Mathematics and Natural Sciences, Peoples' Friendship University)
Analysis of the symplectic splitting methods and symplectic Runge-Kutta type methods for long-time tasks
Abstract
Objective: To evaluate the applicability of symplectic numerical methods to various problems. Evaluation of the calculation accuracy of various invariants (total energy, momentum, etc.)
Historically the classical numerical methods are focused on minimisation the local error. However, complication of the studied problems make necessary to perform calculations for long-time processes. In such problems classical methods give the correct picture in local, but not in global (eg, do not preserve the total energy of the system). In this regard, began to develop geometric integrators, which take into account the geometric structures of the problem being solved. In the case of Hamiltonian mechanics, such methods are symplectic numerical methods.
Symplectic numerical methods are such numerical schemes, every iteration of which preserves the symplectic structure of Hamilton equations (the symplectic 2-form). The advantage of such methods is that calculation errors of system's invariants do not grow limitless with time. They changes in a very limited range. Due to this property symplectic numerical methods are widly used in celestial mechanics, molecular dynamics and computer animation.
The report provides an overview of symplectic methods and presents some theoretical results concerning the symplecticness conditions of composition partitioned symplectic Runge-Kutta method with its adjoin. Also the splited symplectic method for restricted three-body problem is presented This method can not be written as Runge-Kutta method. Different symplectic methods (partitioned Runge-Kutta methods, Runge-Kutta-Nyström methods, the various splitting methods) are compared and conservation accuracy of invariants (total energy, angular momentum, Laplace-Runge-Lenz's vector) are studied.
Е.С.Шемякова (ВЦ РАН)
Обратимые преобразования Дарбу
Аннотация
Нелинейное уравнение с частными производными называется интегрируемым, если существует два линейных уравнения такие, что исходное нелинейное является условием совместности этих двух линейных уравнений. Зная одно из решений исходного уравнения, можно рассмотреть эту пару линейных уравнений под действием преобразований Дарбу, и далее, используя метод задачи обратного рассеяния, получить целое семейство существенно новых решений исходного нелинейного уравнения.
В общем случае, задача построения преобразований Дарбу довольно сложна. Особенно сложно построить обратимые преобразования Дарбу, где под обратимостью понимается обратимость соответствующего отображения, действующего на ядрах соответствующих линейных операторов.
Для классического стационарного уравнения Шредингера от двух переменных только два преобразования Дарбу преобразования Лапласа (и их композиции) обратимы. В данном докладе, будет показано, что для операторов высших порядков существуют обратимые преобразования Дарбу. Помимо некоторых сопутствующих утверждений, будет представлен критерий существования обратимого преобразования Дарбу для операторов произвольных порядков.
E.S.Shemyakova (CC RAS)
Invertible Darboux transformations
Abstract
A non-linear PDE is integrable if there exists a pair of linear operators such that the original non-linear PDE is the compatibility condition of the corresponding system of linear PDEs. Having one solution of the initial non-linear PDE one applies Darboux transformations to the corresponding pair of linear partial differential operators, and following further the method known as the inverse scattering method generates a whole family of essentially new solutions of the initial non-linear PDE.
In general, given a PDE, it is not easy to construct a Darboux transformation for it, and it is very hard to fi nd a Darboux transformation that is invertible, in the sense that the corresponding mappings of the operator kernels are not invertible.
For classical two-dimentional stationary Schroedinger equation only two special cases of Darboux transformations Laplace transformations (and their compositions) are invertible. In the talk we show that for operator of higher orders there are many Darboux transformations that are invertible. Among other results, we give a criteria for such operators to have invertible Darboux transformations.
А.А.Рябенко (ВЦ РАН)
Символьное решение линейных обыкновенных дифференциальных уравнений с помощью степенных рядов
Аннотация
Представляются алгоритмы компьютерной алгебры решения линейных обыкновенных дифференциальных уравнений с полиномиальными коэффициентами. Для неоднородных уравнений предлагаются алгоритмы построения решений в виде рядов с полиномиальными, рациональными, гипергеометрическими коэффициентами и алгоритмы поиска точек, в которых такие решения существуют. Для однороднх уравнений представляется модулярно-вероятностный алгоритм поиска m-точек (m — целое, m>=2), то есть точек, в которых существуют решения в виде ряда, только каждый m-ый коэффициент которого не равен нулю.
Представляются алгоритмы построения в особых точках однородных уравнений формальных экспоненциально-логарифмических решений, содержащих ряды с гипергеометрическими, с даламберовыми коэффициентами.
Представляется пакет Slode для решения линейных обыкновенных дифференциальных уравнений с помощью степенных рядов в системе компьютерной алгебры Maple. Пакет предлагает процедуры построения решений и процедуры поиска точек, где решение может иметь вид ряда с полиномиальными, рациональными, гипергеометрическими, даламберовыми коэффициентами, иметь вид m-разреженного ряда, m-разреженного m-гипергеометрического ряда.
A.A.Ryabenko (CC RAS)
Solving linear ordinary differential equations symbolically by power series
Abstract
Symbolic algorithms to solve linear ordinary differential equations with polynomial coefficients are presented. For nonhomogeneous equations, we propose algorithms to construct power series solutions with polynomial, rational, hypergeometric coefficients and algorithms to find points where such solutions exist. For homogeneous equations, we present a modular-probabilistic algorithm to find m-points (m is integer, m>=2), i.e. points where sparse power solutions exist. A power series is called m-sparse if (for large enough indices) only each m-th coefficient can be nonzero.
For singular points of homogeneous equations, we present algorithms to construct formal exponential-logarithmic solutions with hypergeometric power series, with d'Alembertian power series.
In a computer algebra system Maple, we present a package Slode for solving linear ordinary differential equations by power series. The package suggests procedures to construct solutions and procedures to find points where power series solutions with polynomial, rational, hypergeometric, d'Alembertian coefficients, sparse power series can exist.
А.Б.Батхин (Институт прикладной математики им. М.В.Келдыша)
Двояко симметричные периодические решения системы Гамильтона
Аннотация
Рассматривается автономная система Гамильтона с двумя степенями свободы, система канонических уравнений которой t-инвариантна относительно конечной группы преобразований с двумя образующими. Методами компьютерной алгебры исследуется структура матрицы монодромии двояко симметричного периодического решения системы Гамильтона. Показано, что наименьшее значение индекса устойчивости такого периодического решения равно -1, при котором всегда имеется пара периодических решений второго рода по Пуанкаре с удвоенным периодом и с одной симметрией. Полученные результаты применяются к исследованию новых семейств периодических решений плоской круговой задачи Хилла.
A.B.Batkhin (Keldysh Institute of Applied Mathematics of RAS)
Double symmetric periodic solutions of a Hamiltonian system
Abstract
We consider an autonomous Hamiltonian system with two degrees of freedom, which canonic system is t-invariant under finite group of transformations with two generators. We investigate the structure of the monodromy matrix of a double symmetric periodic solution of such Hamiltonian system with the help of computer algebra. It is shown that the stability index of such solution has minimal value equal to -1. There is a pair of single symmetric periodic solutions of second genre with double period when the stability index of the double symmetric periodic solution of the first genre is equal to -1. New families of symmetric periodic solutions of the planar Hill's problem are investigated with the help of obtained results.
С.Ф.Адлай (ВЦ РАН, Москва)
Приложение алгебраического подхода Софуса Ли к исследованию эллиптических функций
Аннотация
Первостепенным шагом к исследованию решений дифференциального уравнения является определение структуры его фиксирующей группы, то есть структуры группы преобразований, переводящих одно решение данного дифференциального уравнения в другое. Такой подход позволяет объединить два традиционных подхода к исследованию эллиптических функций, а именно подход Якоби и подход Вейерштрасса. Две группы, соответственно, фиксирующая дифференциальное уравнение, которому удовлетворяет эллиптический синус Якоби и фиксирующая дифференциальное уравнение, которому удовлетворяет эллиптическая функция Вейерштрасса, оказываются изоморфными друг другу. Обе группы изоморфны четырёхэлементной группе Клейна. Цель доклада – показать, что такой единый подход оправдан не только как методологически верный, позволяющий получить классические известные результаты, но и новые результате, в том числе опровергающие современные сложившиеся представления об эллиптических интегралах и функциях. Источником ложных современных представлений оказалось существенно недостаточное изучение предсмертного письма Галуа (написанное накануне дуэли 30 мая 1832 года, которое, по выражению Германа Вейля, является самым значительным когда-либо написанным документом). Стремление к более полному восстановлению вклада Галуа породило качественно новые алгоритмы, позволяющие вычислять с непревзойдённой эффективностью и точностью, что будет продемонстрировано многочисленными примерами, и, в частности, будет (c легкостью!) указан непревзойдённый алгоритм вычисления вездесущей константы Пи.
S.F.Adlaj (CC RAS, Moscow)
Applying Sophus Lie algebraic approach to investigating elliptic functions
Abstract
A foremost step for investigating solutions of a differential equation is identifying the structure of its fixing group, that is, the structure of the group of transformations, sending a solution, of the given differential equation, to another solution. Such an approach permits a unification of two traditional approaches to studying elliptic functions, namely, the Jacobi approach and the Weierstrass approach. The two groups, respectively, that fixing the differential equation, satisfied by the Jacobi sine function and that fixing the differential equation, satisfied by the Weierstrass elliptic function, turn out being isomorphic to each other. Both groups are isomorphic to the Klein four group. The aim of this talk is showing that such a unifying approach is justified not merely because it, being methodologically correct, enables an attainment of classical known results, but, as well as, new results, some of which overturn evolved contemporary views about elliptic integrals and functions. The source of contemporary misgivings appears to lie in significantly insufficient studying of Galois’ last letter (written on the eve of his fatal duel on May 30, 1832) which according to Hermann Weyl is «the most substantial piece of writing in the whole literature of mankind.» Aiming at fuller restoration of Galois’ contribution, qualitatively new algorithms, enabling calculations with unsurpassable efficiency and precision, have emerged and will be abundantly demonstrated via examples, including an (easy!) outline of an unsurpassable algorithm for computing the ubiquitous constant Pi.
О.Н.Переславцева (ТГУ имени Г.Р. Державина, Тамбов)
Вычисление характеристических полиномов плотных матриц: последовательные и параллельные алгоритмы
Аннотация
Рассматриваются алгоритмы вычисления характеристических полиномов матриц в коммутативных кольцах. Предлагается новый алгоритм вычисления характеристических полиномов матриц в коммутативной области с меньшим числом кольцевых операций.
Исследуются два класса алгоритмов – прямые алгоритмы и алгоритмы, основанные на методе гомоморфных образов. Для прямых алгоритмов получены выражения для сложности в числе мультипликативных операций над машинными словами. Эти выражения дают возможность сравнивать исследуемые алгоритмы вычисления характеристических полиномов.
Приводится экспериментальное сравнение программ, которые были разработаны по этим алгоритмов. Исследуется время работы программ. Сопоставляются теоретические и экспериментальные результаты.
Описывается способ организации параллельного вычислительного процесса для алгоритма вычисления характеристического полинома, основанного на методе гомоморфных образов. На этой основе разработаны параллельный алгоритм и программа вычисления характеристических полиномов для целочисленных и полиномиальных матриц.
Приводятся результаты экспериментов, проведенных на вычислительном кластере MVS100k Межведомственного суперкомпьютерного центра РАН.
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, August 29, at 16:20, room 788 of CMC faculty.
O.N.Pereslavtseva (TSU named after GR Derzhavin, Tambov)
Computing the characteristic polynomials of dense matrices: sequential and parallel algorithms
Abstract
Algorithms for computing the characteristic polynomials of matrices in commutative rings are considered. An algorithm for computing the characteristic polynomials of matrices in a commutative domain with a smaller number of ring operations is proposed.
Two classes of algorithms are investigated: standard algorithms and algorithms based on the method of homomorphic images. We obtain complexity expressions for the number of multiplicative operations on machine words. These expressions allow to compare the algorithms for computing the characteristic polynomials.
The algorithms are implemented in software. An experimental comparison of these algorithms is provided.
The organization of a parallel computing process based on the method of homomorphic images is described. We develop a parallel algorithm and a parallel program for calculating the characteristic polynomials for integer and polynomial matrices by means of the organization of the parallel computing process.
The results of experiments on supercomputer MVS100k of Joint Supercomputer Center of the RAS are discussed.
22-23 мая 2012 года был проведен традиционный совместный семинар - фактически, двухдневная конференция - с Лабораторией информационных технологий ОИЯИ (Дубна). Этот совместный семинар был посвящен 80-летию В.А.Ростовцева.
The traditional joint meeting with the seminar of Laboratory of Information Technologies of JINR (Dubna) was organized on May 22nd-23rd, 2012. Essentially, this was a two-days conference, dedicated to the 80-th birthday of V.A.Rostovtsev.
Slides (Zinin) Extended Abstract (Denisov)
1. А.М.Денисов (ВМК МГУ)
Неединственность решения бесконечной системы дифференциальных уравнений в частных производных в пространстве Шварца
Аннотация
Рассматривается задача, возникающая в двумерной Доплеровской томографии. Требуется определить две функции u(x,y) и v(x,y) из пространства Шварца в ограниченной области, являющиеся решением бесконечной системы уравнений в частных производных . Система обладает некоторыми своиствами симметрии. Решение сформулированной задачи неединственно. Было бы интересно обсудить вопрос о выделении некоторых специальных классов единственности решения сформулированной задачи.
2. М.В.Зинин (ООО «Андер Девелопмент», Москва)
Символьные алгоритмы и программы вычисления булевых базисов Грёбнера
Аннотация
Базисы Грёбнера являются теоретически и практически значимым математическим объектом с обширной областью применения. Это справедливо и в отношении базисов Грёбнера в целом, и в отношении булевых базисов. Например, базисы Грёбнера оказываются весьма полезны в случаях, когда решение некоторой задачи связано с исследованием соответствующей полиномиальной системы уравнений.
В случае булевых базисов (о которых и пойдет речь в докладе ) наиболее распространенными подобными задачами являются задачи криптоанализа и булевой выполнимости. Еще одним многообещающим применением булевых базисов Грёбнера является моделирование квантовых вычислений на классическом компьютере.
Таким образом, можно утверждать, что в настоящее время существует потребность в быстрых и эффективных алгоритмах для вычисления булевых базисов Грёбнера и их реализациях. В докладе кратко описаны наиболее распространенные алгоритмы вычисления базисов Грёбнера, обсуждаются аспекты применений этих алгоритмов в задаче построения булевых базисов Грёбнера и предлагается вариант инволютивного алгоритма для эффективного решения этой задачи.
Далее в докладе подробно представлена реализация вышеупомянутого алгоритма. Реализация существует в виде отдельной утилиты и в виде пакетов для открытых систем компьютерной алгебры REDUCE и Macaulay2. Завершают доклад результаты сравнения быстродействия представленной реализации и с другими системами и пакетами, позволяющими вычислять булевы базисы Грёбнера.
1. A.M.Denisov (Faculty CMC of MSU)
Nonuniqueness of solution to infinite system of partial differential equations in the Schwartz space
Abstract
The following problem arising in 2D Doppler tomography problem is considered. Let functions u(x,y) and v(x,y) belong the Schwartz space in the bounded domain. Determine functions u(x,y) and v(x,y) solving infinite system of nonlinear partial differential. The system has some symmetric properties. Solution of this problem is nonunique. Is it possible to find some special classes of uniqueness of solutions to this problem? It will be interesting to discuss this question.
2. M.V.Zinin (LLC «Under Development», Moscow)
Symbolic algorithms and software for computation of Boolean Groebner bases
Abstract
Groebner bases are theoretically and practically significant mathematical objects with wide area of practical application. All this is true for Groebner bases in general and for Boolean ones as well. For instance, Groebner bases are highly useful for problems that are reduced to multivariate polynomial systems.
In the case of Boolean Groebner bases (the main topic of the talk) their most important application areas are cryptoanalysis and Boolean satisfiability. One more promising application of such bases is simulation of quantum computation on classical computers.
Therefore, one can claim that nowadays there are practical needs in efficient algorithms for computing Boolean Groebner bases and in their optimal implementation. In this talk we will briefly describe the algorithms used for construction of Groebner bases, discuss some aspects of applying these algorithms to computing Boolean bases and propose a version of an involutive algorithm aimed to solve the task efficiently.
Furthermore, the implementation of the algorithm is to be described in details. This implementation is available in the form of a standalone utility and in the form of packages for open source computer algebra systems REDUCE and Macaulay2. In the final part of the talk we benchmark our results with those other implementations and software packages oriented to construction of Boolean Groebner bases.
Slides (Kulyabov et al.) Slides (Abramov, Khmelnov)
1. Д.С.Кулябов, А.В.Королькова, М.Н.Геворкян, Л.А.Севастьянов (факультет физико-математических и естественных наук, Российский университет дружбы народов)
Применение симплектических интеграторов для задачи распространения электромагнитных волн
Аннотация
Предлагается для численного решения дифференциальных уравнений использовать методы, сохраняющие структуру решений, а именно, группу методов геометрических интеграторов. Рассматривается метод симплектического интегратора в применении к задачам распространения электромагнитных волн в волноводе. Подробно рассматриваются вспомогательные задачи: запись уравнений Максвелла в криволинейных голономных координатах; получение гамильтониана для уравнений Максвелла.
2. С.А.Абрамов, Д.Е.Хмельнов (Вычислительный центр РАН)
О валюацях мероморфных решений линейных разностных систем произвольного порядка с полиномиальными коэффициентами
Аннотация
Рассматривается несколько алгоритмов получения нижних оценок валюаций (например, порядков полюсов) компонент мероморфных решений разностных линейных систем произвольного порядка с полиномиальными коэффициентами. Наряду с алгоритмами, основанными на идеях, в каком-то виде уже применявшихся в компьютерной алгебре при работе с нормальными разностными системами первого порядка, предлагается новый алгоритм, использующий «тропические» вычисления. Показывается, что последний алгоритм, обеспечивая хорошую точность оценок, является при этом и достаточно быстрым.
1. D.S.Kulyabov, A.V.Korolkova, M.N.Gevorkyan, L.A.Sevastianov (Department of Physics, Mathematics and Natural Sciences, Peoples' Friendship University)
Symplectic integrators and the problem of propagation of electromagnetic waves
Abstract
For the numerical solving differential equations structure-preserving algorithms are proposed, namely, a kind of geometric integrators algorithms. The symplectic integrators method applied to the problem of electromagnetic wave propagation. Detailed discussion of the auxiliary problem: write Maxwell's equations in curvilinear coordinates; obtaining the Hamiltonian for the Maxwell equations.
2. S.A.Abramov, D.E.Khmelnov (Computing Centre of the Russian Academy of Sciences)
On valuations of meromorphic solutions of arbitrary-order linear difference systems with polynomial coefficients
Abstract
Algorithms for computing lower bounds on valuations (e.g., orders of the poles) of the components of meromorphic solutions of arbitrary-order linear difference systems with polynomial coefficients are considered. In addition to algorithms based on ideas which have been already utilized in computer algebra for treating normal first-order systems, a new algorithm using ``tropical'' calculations is proposed. It is shown that the latter algorithm is rather fast, and produces the bounds with good accuracy.
А.Б.Батхин (Институт прикладной математики им. М.В.Келдыша)
Точные решения шестого уравнения Пенлеве
Аннотация
Уравнения Пенлеве играют важную роль в математической физике и имеют многочисленные применения. Для приложений важным является знание точных решений уравнений Пенлеве для определенных значений параметров, входящих в уравнение. Предлагается метод построения точных решений шестого уравнения Пенлеве (PVI) в виде конечных сумм степенных функций с рациональными показателями степени. Метод существенно использует алгоритмы степенной геометрии для построения степенных разложений решений обыкновенного дифференциального уравнения и алгоритмы компьютерной алгебры.
A.B.Batkhin (Keldysh Institute of Applied Mathematics of RAS)
The exact solutions to the six Painleve equation
Abstract
Painleve equations play an important role in mathematical physics, and have numerous applications. For applications it is important to know the exact solutions to the Painleve equations of the certain values of the parameters in the equation. We propose a method for constructing exact solutions of the sixth Painleve equation (PVI) in the form of finite sums of power functions with rational power exponents. The method essentially uses the algorithms of Power Geometry for the construction of power series solutions of ordinary differential equation and algorithms of computer algebra.
Slides (Smirnov) Slides (Tsarev)
1. А.В.Смирнов (Научно-исследовательский вычислительный центр МГУ)
Алгоритмы вычисления фейнмановских интегралов
Аннотация
Фейнмановские интегралы являются фундаментальными величинам при построении квантово-полевых амплитуд в рамках теории возмущений, в частности, они возникают при вычислениях в рамках Стандартной Модели физики элементарных частиц. На современном уровне исследований в конкретной задаче может требоваться вычисление миллионов интегралов Фейнмана, что, естественно, невозможно без разработки и применения алгоритмов на современных компьютеров. Согласно классическому подходу, задача вычисления фейнмановских интегралов распадается на их редукцию к относительно небольшому числу мастер-интегралов и вычисление последних. Автором были разработаны алгоритмы, применяющиеся как при редукции, так и вычислении фейнмановских интегралов. Алгоритм редукции относится к области решения очень больших рассеянных систем линейных уравнений с полиномиальными коэффициентами. Алгоритм вычисления представляет собой алгебраическое упрощение выражений, выделение особенностей и последующее численное интегрирование. Оба алгоритма будут описаны в докладе.
2. С.П.Царев (Сибирский Федеральный Университет, Красноярск)
О структуре решетки правых делителей линейного обыкновенного дифференциального оператора
Аннотация
В 1996 г. автором был предложен алгоритм полного перечисления всех возможных факторизаций заданного линейного обыкновенного дифференциального оператора (ЛОДО) на неприводимые множители над полем рациональных функций. К сожалению, полное описание всех возможных структур, выдаваемых данным алгоритмом, до сих пор неизвестно. В докладе будут изложены недавние результаты о структуре всех возможных факторизаций заданного ЛОДО над произвольным дифференциальным полем коэффициентов. Удобным алгебраическим инструментом для этого описания является теория модулярных решеток.
1. A.V.Smirnov (Scientific research computing center, MSU)
The algorithms used to evaluate Feynman integrals
Abstract
Feynman integrals are fundamental objects used to represent quantum field theoretical amplitudes in the framework of perturbation theory, particularly they appear in calculations in the framework of the Standard Model in particle field theory. Currently for a give problem one might require to evaluate millions of Feynman integrals, which is of course impossible without developing proper computer algorithms. A classical approach is to decompose the evaluation of integrals into two tasks. First of all, one has to reduce (without evaluating) all integrals to a small number of so-called master integrals, then one has to evaluate the remaining ones. The speaker has developed algorithms contributing to both of these problems. The reduction algorithm is relating to solving huge systems of linear equations with polynomial coefficients. The evaluation algorithm consists of algebraic transformations of given expressions, resolution of singularities and numerical integration. Both algorithms will be presented in this talk.
2. S.P.Tsarev (Siberian Federal University, Krsanoyarsk)
Structure of the lattice of right divisors of a linear ordinary differential operator
Abstract
Since 1996 an algorithm for complete enumeration of all factorizations of a given linear ordinary differential operator (LODO) into irreducible factors over the field of rational functions is known. Unfortunately the complete description of possible structures of such factorizations is yet unknown. We expose recent results on such structures for LODOs with coefficients in any differential field. A very useful algebraic tool for the description of appearing factorization structures is given by the theory of modular lattices.
А.А.Михалев (Механико-математический факультет, Московский государственный университет)
Примитивные элементы свободных алгебр
Аннотация
Многообразие линейных алгебр над полем называется шрайеровым, если любая подалгебра свободной алгебры этого многообразия является свободной. Многообразие всех алгебр, многообразие всех коммутативных алгебр, многообразие всех антикоммутативных алгебр, многообразие всех алгебр Ли, многообразие всех супералгебр Ли, многообразия всех p-алгебр Ли и всех p-супералгебр Ли являются основными типами шрайеровых многообразий алгебр.
Пусть A(X) – свободная алгебра шрайерового многообразия алгебр с множеством X свободных образующих. Система элементов u1,…, un алгебры A(X) называется примитивной, если существует множество Y свободных образующих алгебры A(X), содержащее элементы u1,…, un.
Для свободных алгебр основных типов шрайеровых многообразий алгебр построены и реализованы алгоритмы распознавания примитивных систем элементов, а также алгоритмы дополнения примитивных систем элементов до свободных порождающих множеств.
Доклад основан на совместных работах автора с К.Шампаньер, А.А.Чеповским, А.В.Михалевым, И.П.Шестаковым, У.У.Умирбаевым, Дж.Ю, А.А.Золотых.
—————————————————————————————————
A.A.Mikhalev (Faculty of Mechanics and Mathematics, Moscow State University, Russia)
Primitive elements of free algebras
Abstract
A variety of linear algebras over a field is said to be Schreier if any subalgebra of a free algebra of this variety is free. The variety of all algebras, the variety of all commutative algebras, the variety of all anti-commutative algebras, the variety of all Lie algebras, the variety of all Lie superalgebras, varieties of all Lie p-algebras and Lie p-superalgebras are the main types of Schreier varieties of algebras.
Let A(X) be the free algebra of a Schreier variety of algebras with the set X of free generators. A system of elements u1,…, un of A(X) is primitive if there is a set Y of free generators of the free algebra A(X) such that u1,…, un belong to Y.
Algorithms to recognize primitive systems of elements of free algebras of the main types of Schreier varieties of algebras are constructed and implemented. We obtain also algorithms to construct complements of primitive systems of elements with respect to free generating sets.
This talk is based on joint works with C.Champagnier, A.A.Chepovskii, A.V.Klimakov, A.V.Mikhalev, I.P.Shestakov, U.U.Umirbaev, J.-T.Yu, and A.A.Zolotykh.
В.В. Корняк (Лаборатория информационных технологий, Объединенный институт ядерных исследований, Дубна)
Вычислительная теория групп и квантовая физика
Аннотация
Вычислительная теория групп - это подраздел символьной алгебры. Она изучает конечные (или конечно-представленные) группы конструктивными алгоритмическими методами. Имея в виду физические приложения, мы всегда можем предполагать конечность всех элементов описания: введение континуума или других бесконечностей в физику приводит только к техническим усложнениям без какой-либо необходимости в них для описания эмпирических данных. Более того, имеются веские экспериментальные свидетельства (главным образом из нейтринной физики) того, что конечные группы относительно небольших порядков лежат в основе некоторых фундаментальных физических процессов. В более общем контексте конечные группы и их представления над конструктивными числовыми системами ведут к очень простому и естественному переформулированию квантовой механики. Мы кратко обсуждаем алгоритмы, необходимые для построения «конечной» квантовой механики.
—————————————————————————————————
V. V. Kornyak (Laboratory of Information Technologies, Joint Institute for Nuclear Research, Dubna)
Computational Group Theory and Quantum Physics.
Abstract
Computational group theory is a subfield of symbolic algebra. It studies finite (or finitely presented) groups by constructive algorithmic methods. Having in view physical applications, we can always assume finiteness of all elements of description: introduction of continuum or other infinities into physics leads only to technical complications without any need for them in description of empirical data. Moreover, there are strong experimental evidences (coming mainly from the neutrino physics) that finite groups of relatively small orders underlie some fundamental physical processes. In the more general context, the finite groups and their representations over constructive number systems lead to very simple and natural reformulation of quantum mechanics. We discuss briefly the algorithms needed for construction of the «finite» quantum mechanics.
В.П.Гердт (Лаборатория информационных технологий, Объединенный институт ядерных исследований, Дубна)
Анализ аппроксимируемости систем уравнений в частных производных конечными разностями
Аннотация
В докладе рассматриваются конечно-разностные аппроксимации полиномиально-нелинейных систем дифференциальных уравнений в частных производных, коэффициенты которых являются рациональными функциями от независимых переменных. Общепринятое понятие (слабой) аппроксимации исходных уравнений сопоставляется с понятием сильной аппроксимации, введенным ранее автором для линейных дифференциальных систем и обобщенным недавно на нелинейные системы. Для ортогональных и равномерных сеток предлагается алгоритмическая процедура проверки сильной аппроксимируемости методами компьютерной алгебры, основанная на приведении в инволюцию исходной дифференциальной системы и построении разностного стандартного базиса для рассматриваемой аппроксимации. В качестве примеров изучаются конечно-разностные аппроксимации некоторых переопределенных линейных дифференциальных систем и две различные аппроксимации для двумерных нелинейных уравнений Навье-Стокса. Предлагаемая в докладе алгоритмическая процедура устанавливает, что одна из этих двух аппроксимаций является сильной, а другая нет.
—————————————————————————————————
V.P.Gerdt (Laboratory of Information Technologies, Joint Institute for Nuclear Research, Dubna)
Consistency Analysis of Finite Difference Approximations to Systems of Partial Differential Equations
Abstract
In the given talk we consider finite difference approximations (FDA) to systems of polynomially-nonlinear partial differential equations (PDEs) whose coefficients are rational functions over rationals in the independent variables. We confront the conventional notion of (weak) consistency of FDAs with the notion of strong consistency which we introduced earlier for linear PDE systems and extended recently to nonlinear equations. For orthogonal and uniform grids we describe an algorithmic procedure for verification of strong consistency by sing computer algebra methods based on completion of the initial differential system to involution and computation of a difference standard basis for its approximation. The concepts and algorithmic methods of the present paper are to be illustrated by FDAs to some linear overdetermined PDE systems and by two FDAs to the two-dimensional nonlinear Navier-Stokes equations. One of these last approximations is strongly consistent and another is not.