Table of Contents

2007-2008

Seminar on Computer Algebra, December 24

Wednesday, December 24, at 16.20 in room 225-1 of building LKVE of Skobeltcyn Institute of Nuclear Physics, Moscow State University.

Asymptotic Expansions of Solutions of the Elliptic Two-Dimensional Boundary Problem

A.A. Gusev, O. Chuluunbaatar (JINR, Dubna)

The three-dimensional boundary problem for the elliptic partial differential equation with an axial symmetry (the Schroedinger equation with Coulomb and transverse oscillator potentials) is reduced to the two-dimensional one. Using a basis of the angular functions, the two-dimensional boundary problem is reduced to the second-order ordinary differential equations with homogeneous boundary conditions of third type in bound points of finite interval by radial variable. The recurrence relations for calculation of asymptotic expansions of required solution of the problem at small and large values of radial variable and for setting of boundary conditions is derived.


Асимптотические разложения решений двумерной краевой задачи эллиптического типа

А.А. Гусев, О. Чулуунбаатар (ОИЯИ, Дубна)

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


Seminar on Computer Algebra, October 15

Wednesday, October 15, at 16.20 in room 225-1 of building LKVE of Skobeltcyn Institute of Nuclear Physics, Moscow State University.

Extended Wreath Products

Vladimir V. Kornyak (LIT, JINR, Dubna)

Abstract


Расширенные сплетения групп

Владимир В. Корняк (ЛИТ, ОИЯИ, Дубна)

Абстракт


Seminar on Computer Algebra, September 17

Wednesday, September 17, at 16.20 in room 785 of building VMK, Moscow State University.

On Entire Solutions of Linear Difference Equations with Polynomial Coefficients

S.A.Abramov (Computing Center of RAS)

The results were obtained jointly with M.Barkatou, M.Petkovsek, M.van Hoeij

It is known that any linear difference equation of order d with polynomial (over the comlex numbers field C) coefficients has a fundamental system of entire solutions (C.Praagman, 1986). We rather strength this result: the C-linear space of the sequences, which are restrictions to Z of entire solutions of an equation of order d has dimension d. We also show that a basis for this space of such sequences can be found algorithmically.


О решениях в целых функциях линейных разностных уравнений с полиномиальными коэффициентами

С.А.Абрамов (ВЦ РАН)

Результаты получены совместно с М.Баркату, М.Петковшеком и М.ван Хое

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


Seminar on Computer Algebra in Dubna.

The traditional May seminar in Dubna will have place on May 14-16 2008.

See: http://compalg.jinr.ru/Dubna2008/index.html


Seminar on Computer Algebra, April 23.

Wednesday, April 23, at 16.20 in room 780 of building VMK, Moscow State University.

Power Series and Linear Difference Equations

S.A.Abramov (Computing center of RAS).

We discuss, in particular, some sufficient conditions for applicability of a summing operator to a solution of given linear difference equation with polynomial coefficients. The case of a multidimensional hypergeometric sequences is included.

Степенные ряды и линейные разностные уравнения

С.А.Абрамов (ВЦ РАН).

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

Block symbolic matrix algorithms

M.S.Zuev (Tambov University).

The report is dedicated to block matrix algorithms. Two new block algorithms for computing inverse of matrices over the fields and an algorithm for computing adjoint matrix and determinant for matrices over the commutative domains are described. The complexity estimations for these algorithms are adduced. Also the complexity estimations for addition and multiplication of sparse matrices over sparse polynomials, based on probabilistic approach, are computed.

New matrix storage format, based on their quadtree representation, is proposed. This format is intended for computations with block-recursive matrix algorithms.

The results of computational experiments are considered.


Блочные символьные матричные алгоритмы

М.С.Зуев (Тамбовский университет).

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

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

Обсуждаются результаты вычислительных экспериментов.

Integral representation and closed form summation

Wednesday, March 12, at 16.20 in room 780 of building VMK, Moscow State University.

Integral representation and closed form summation

E.V.Zima. Wilfrid Laurier University (Waterloo, Canada). This is joint work with G.P.Egorychev (Siberian Federal University, Krasnoyarsk).

Integral representation is applied to various problems of algorithmic indefinite and definite summation. An integral representation approach to rational summation is compared to known algorithmic approaches. It is shown that the integral representation can be used for practical improvements of known summation algorithms.


Интегральное представление и суммирование в замкнутом виде

Е.В.Зима Wilfrid Laurier University (Waterloo, Canada). Доклад подготовлен на основе совместных с Г.П.Егорычевым (Сибирский Федеральный Университет, Красноярск) работ.

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

Seminar on Computer Algebra Devoted to Memory of Evgenii Vasil'evich Pankrat'ev

Wednesday, February 06, at 16.20 in room 780 of building VMK, Moscow State University.

1. M.V. Kondratyeva (MSU). In memory of E.V.Pankrat'ev

2. Hyperdeterminats as a computer algebra challenge: their computation and relations to integrable partial difference equations

S.P.Tsarev (Krasnoyarsk Pedagogical University)

The theory of hyperdeterminants is more than 150 years old. A.Cayley had proposed a general definition and computed the simplest perdeterminant of a 2x2x2 hypermatrix (i.e. a tensor with 3 indices in R^2). The expression is a polynomial of total degree 4 in all 8 variables (the elements of the hypermatrix) and has only 12 terms.

For the next step - computation of a 2x2x2x2 hyperdeterminant (for a tensor with 4 indices in R^2) B.Sturmfels in 2006 was helped by 3 programmers who have glued several millions of terms produced by Maple in several steps (cf. their e-preprint at www.arxiv.org, math.CO/0602149 v2 3 Oct 2006). The resulting expression is a polynomial of total degree 24 in 16 variables with 2894276 terms. The problem of computation of this hyperdeterminant was proposed by I.M.Gelfand in 2005. It is closely related to some problems in enumeration of combinatorial data.

In the end of 2007 we could repeat this computation without any dedicated C code using the symbolic computation program FORM in 8 hours on a modest computer. Moreover, in the process of verification of symmetry properties of the obtained expression FORM correctly generated and processed (in some 10 hours using 200 Gb of disk space for temporary file storage) an expression with 800 million terms. This is not the largest possible expression computable by FORM.

In this talk we give the basic definitions and known theoretical results about hyperdeterminants, briefly sketch their modern applications (quantum computing, biomathematics, numerics, stochastic calculus etc.) and give an account of two recent results obtained with hyperdeterminants: a) The Principal Minor Assignment Problem, i.e. the problem of description of relations between principal minors of a symmetric matrix; b) proof of integrability of a difference equation defined by the 2x2x2 hyperdeterminant.

It turns out that these two problems are intimately related and imply the following hypothesis: the difference equations defined by hyperdeterminants are integrable.

We plan to discuss the current limits of complexity of expressions feasible for handling by real-world symbolic computation packages. A natural question arises: is the conjecture of integrability of hyperdeterminantal equations true? How large the hyperdeterminant of a 2x2x2x2x2 hypermatrix may be?


1. М.В.Кондратьева (Мехмат МГУ). В память о Евгении Васильевиче Панкратьеве

2. Вычислительный вызов (challenge) в компьютерной алгебре: вычисление гипердетерминантов и их связь с интегрируемыми уравнениями в частных разностях

С.П.Царев (Красноярский педагогический университет)

Теории гипердетерминантов более 150 лет - от первых работ А.Кэли, который сделал первый шаг: ввел общее определение и вычислил простейший гипердетерминант пространственной матрицы размера 2x2x2, т.е. тензора с тремя индексами в двумерном пространстве. Полученное выражение имеет полную степерь 4 по всем 8 переменным (элементам гиперматрицы) и имеет всего 12 слагаемых.

Для следующего шага - вычисления гипердетерминанта 2x2x2x2 (от тензора с четырьмя индексами в двумерном пространстве) - Б.Штурмфельсу в 2006 г. потребовалась помощь трех программистов, сделавших “склейку” нескольких миллионов слагаемых, раздельно посчитанных в Мэйпле (см. препринт www.arxiv.org, math.CO/0602149 v2 3 Oct 2006) В результате получился полином от 16 переменных степени 24 с 2894276 слагаемыми. Задача вычисления такого гипердетерминанта была предложена И.М.Гельфандом в 2005 г. и связана с задачами перечислительной комбинаторики.

В конце прошлого года, используя систему символьных вычислений FORM, оказалось возможным всего за 8 часов работы на среднем компьютере повторить данное вычисление без написания специализированных добавочных программ. Более того, при проверке свойств инвариантности полученного гипердетерминанта FORM оказался способен (за 10 часов при использовании временных файлов размера 200 Гб) корректно сгенерировать и привести подобные в выражении из 800 миллионов слагаемых. И это далеко не предельный размер выражений, доступных для FORM'а.

В докладе будут даны основные определения и известные теоретические результаты о гипердетерминантах, обрисованы области их современных приложений (квантовые вычисления, мат. биология, численные задачи, стохастические системы и т.п.). Планируется рассказать о двух задачах, решенных недавно с помощью гипердетерминантов: а) задаче описания соотношений между главными минорами симметрических матриц (О.Хольц+Б.Штурмфельс); б) доказательство интегрируемости одной разностной системы, описываемой гипердетерминантом 2x2x2

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

Планируется обсудить текущие “рекордные” показатели сложности реальных вычислений, доступных в настоящее время компьютерной алгебре. Естественно поставить вопрос: верна ли гипетеза об интегрируемости разностных систем, определяемых любыми гипердетерминантами, и насколько может быть велик гипердетерминант гиперматрицы размера 2x2x2x2x2 ?

E.V.Pankratev

Dear Colleague,

With great anguish we regret to inform you that Evgenii Vasil'evich Pankrat'ev was lost in a road accident on January 23 2008.

He was the large scientist, the magnificent teacher and the reliable friend.

Farewell will take place on Saturday, January 26 at 11:00 in building VMK, Moscow State University.


С большим прискорбием вынуждены сообщить, что Евгений Васильевич Панкратьев погиб в автомобильной катастрофе 23 января 2008.

Он был выдающимся ученым, великолепным учителем и надежным другом.

Прощание состоится в субботу, 26 января в 11 часов в корпусе ф-та ВМиК Московского государственного университета (2-ой Гуманитарный корпус, вход, ближайший к Главному зданию, далее - по указателям).

Victor Edneral 25/01/2008

Algebraic Models of Production Logic and Opportunity of Their Application in Computer Algebra System

Wednesday, January 16, at 16.20 in room 780 of building VMK, Moscow State University.

S.D.Makhortov (Voronezh State University)

The lattice based algebraic systems representing production type logic models are introduced. The main idea is modeling of production connections by special binary relation with appropriate properties. Each model is defined by its own set of such properties. The base relation of the partial order that generates a lattice reflects the universal tautologies and is fixed. The second (production) relation originates from the logical connections of problem domain and can be exposed to optimizing transformations.

For each model standard questions are considered: closure, equivalent transformations, closure structure, and logical reduction.

Possibilities of application of the proposed theory in the computer algebra systems development are discussed.


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

С.Д.Махортов (Воронежский госуниверситет)

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

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

Обсуждаются возможности применения изложенной теории при разработке систем символьной математики.

Specialization of functional programs by supercompilation

Wednesday, December 19, at 16.20 in 780 room of building VMK, Moscow State University.

A.P. Nemytykh (Program Systems Institute of RAS, Pereslavl-Zalessky)

Given a program p(x,y). Let us fix a value of the first argument x_0. The simplest task of program specialization is to construct another program q_p(y) such that q_p(y) = p(x_0, y) on the domain of the program p and the program q_p(y) is more optimal than the p (with respect to run-time).

Supercompilation is a set of specialization methods of programs written in functional programming languages. The methods are based on meta-interpretation of the programs to be specialized.

On the seminar the speaker intends to give a brief introduction to supercompilation and to discuss some methods and algorithms of supercompilation, on the base of which the speaker implemented the fist automatic experimental supercompiler SCP4.


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

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

Рассмотрим программу от двух аргументов p(x,y). Зафиксируем значение первого аргумента x_0. В простейшей постановке задачи специализации требуется построить другую программу q_p(y) такую, что на области определения программы p выполнено равенство q_p(y) = p(x_0, y) и программа по времени исполнения q_p(y) более оптимальна, чем программа p.

Суперкомпиляция есть набор методов специализации программ, написанных на функциональных языках программирования. Методы суперкомпиляции основаны на метаинтерпретации специализируемых программ.

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

Parametric polynomial system solving with Maple

Wednesday, November 21, at 16.20 in П-8а room (the second floor) of building VMK, Moscow State University.

J. Gerhard (Maplesoft, Waterloo, Canada)

A new Maple package RootFinding[Parametric] for solving parametric systems of polynomial equations and inequalities is described. The main idea for solving such a system is as follows. The parameter space R^d is divided into two parts: the discriminant variety W and its complement R^d \ W. The discriminant variety is a generalization of the well-known discriminant of a univariate polynomial and contains all those parameter values leading to non-generic solutions of the system. The complement R^d \ W can be expressed as a finite union of open cells such that the number of real solutions of the input system is constant on each cell. In this way, all parameter values leading to generic solutions of the system can be described systematically. The underlying techniques used are Groebner bases, polynomial real root finding, and Cylindrical Algebraic Decomposition. This package offers a friendly interface for scientists and engineers to solve parametric problems, as illustrated by an example from control theory.

Jacobi bound for systems of ordinary differential equations

Wednesday, October 24, at 16.20 in room 720 of building VMK, Moscow State University.

M.V. Kondratieva ( Lomonosov MSU )

The Jacobi bound estimates the “number of arbitrary constants in the general solution of a system of ordinary differential equations.” The investigation of this bound is one of the problems of differential algebra stated by E. Kolchin in his talk on the Moscow International Mathematical Congress in 1966. In the talk, the state of the art in this area will be discussed.


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

М.В. Кондратьева ( Механико-математический ф-т МГУ )

Граница Якоби оценивает “число произвольных констант в общем решении системы дифференциальных уравнений”. Исследование этой границы является одной из задач дифференциальной алгебры, сформулированных Е. Колчиным в докладе на Московском математическом конгрессе в 1966 году. В докладе будет рассказано о современном состоянии проблемы границы Якоби.

Analysis of the local integrability by methods of normal form and power geometry

Wednesday, September 26, at 16.20 in room 780 of building VMK, Moscow State University.

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

V.F. Edneral (Skobeltsyn Institute of Nuclear Physics of MSU)

On an example of the reduced equation of Young-Mills, representing Hamilton's system of four equations, the approach of research of local integrability by methods of normal forms and Power Geometry is considered. It is proved, that in a neighborhood of one of infinitely far stationary points this system is locally nonintegrable.


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

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

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

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