International Symposium on Symbolic and Algebraic Computation
Munich, July 25-28, 2010

The International Symposium on Symbolic and Algebraic Computation is the premier conference for research in symbolic computation and computer algebra. ISSAC 2010 is the 35th meeting in the series. The conference traditionally presents a range of invited speakers, tutorials, poster sessions and vendor exhibits with a centre-piece of contributed research papers. ISSAC 2010 will be hosted by the Technische Universität München.

ISSAC 2010 invites the submission of original research contributions to be considered for publication and presentation at the conference. All areas of computer algebra and symbolic mathematical computation are of interest. These include, but are not limited to:

Algorithmic aspects:

• Exact and symbolic linear, polynomial and differential algebra.
• Symbolic-numeric, homotopy, perturbation and series methods.
• Computational geometry, group theory and number theory.
• Summation, recurrence equations, integration, solution of ODE & PDE.
• Symbolic methods in other areas of pure and applied mathematics.
• Theoretical and practical aspects, including general algorithms, techniques for important special cases, complexity analyses of algebraic algorithms and algebraic complexity.

Software aspects:

• Design of packages and systems.
• Data representation.
• Software analysis.
• Considerations for modern hardware, e.g., current memory and storage technologies, high performance systems and mobile devices.
• User interface issues, including collaborative computing and new methods for input and manipulation.
• Interfaces and use with systems for, e.g., document processing, digital libraries, courseware, simulation and optimization, automated theorem proving, computer aided design and automatic differentiation.

Application aspects:

• Applications that stretch the current limits of computer algebra algorithms or systems, use computer algebra in new areas or new ways or apply it in situations with broad impact.

Important Dates:

• Abstract submission: Thursday 14 January 2010
• Paper submission: Thursday 21 January 2010
• Reviews available: Thursday 25 March 2010
• Author response period: 29-31 March 2010
• Acceptance notification: Thursday 8 April 2010
• Camera ready copy due: Thursday 6 May 2010

More details http://www.issac-conference.org/2010

Wednesday, December 23, at 16.20 in room 792 of VMK of Moscow State University

Arkady V.Klimov (Institute of Design Problems in Microelectronics RAS)

Parallelizing compilation of Fortran requires analisys of program for building its data flow graph (grid graph, argorithm graph). Here a method of buiding the algorithm graph based on the use of selection trees is proposed. Selection tree is a kind of syntactic structure intended for conveniently representing both the intermediate results of analysis (such as statements effects and states descriptions) and the graph itself. A set of operations over such trees is proposed, in which the algorithms of analysis and grap building are easy to express. The implementation of these operations involves such known mathematical algorithms as Omega-test (the compatibility check for systems of linear diophantine equations and inequations), linear integer programming, diophantine equation and inequation solver, etc. The proposed analysis is intended to serve a basis for compiling Fortran onto dataflow language PolyDFL.

Арк.В.Климов (Институт проблем проектирования в микроэлектронике (ИППМ) РАН)

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

Wednesday, November 11, at 16.20 in room 781 of VMK of Moscow State University

Yu.A.Klimov (Keldysh Institute of Applied Mathematics, RAS)

A new program specialization technique meant for programs written in object-oriented languages has been developed. In contrast to the earlier partial evaluation techniques applicable to functional and object-oriented languages, the presented method is able to deal with all main constructs of such languages as C# and Java and enables a higher degree of polyvariance to be achieved.

The purpose of specializing a program is to gain an increase in its efficiency, which is achieved by performing some operations at specialization time, eliminating some objects and replacing some heap-allocated objects with stack-allocated local variables.

The above techniques have been implemented in an experimental specializer CILPE dealing with programs in the object-oriented language CIL, the intermediate language of the platform Microsoft.NET. Applying CILPE to a number of model programs has produced speed-ups up to 10 (and more) times.

Ю.А.Климов (ИПМ им.М.В.Келдыша РАН)

На основе существующих методов частичных вычислений для функциональных и объектно-ориентированных программ разработан новый метод специализации программ на объектно-ориентированных языках, впервые обеспечивающий специализацию всех основных конструкций таких языков, как C# и Java, и обладающий поливариантностью.

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

Разработанный метод реализован в экспериментальном специализаторе CILPE для промежуточного объектно-ориентированного языка CIL платформы Microsoft .NET и апробирован на модельных задачах, показавших возможность ускорения программ до 10 и более раз.

Wednesday, October 21, at 16.20 in room 781 of VMK of Moscow State University

Alexey Zobnin (MSU)

Differential standard bases are generalisation of Groebner bases to the case of differential polynomials. In contrast to ordinary polynomial ideals, most differential ideals do not have finite differential standard bases. Moreover, the existence of finite basis depends on monomial ordering too. The most interesting cases are when the ideal has finite standard basis w.r.t. orderings that are similar to lexicographical or degree reverse lexicographical. We consider new solved and unsolved problems concerning differential standard bases (in particular, finiteness criteria w.r.t. different orderings).

Алексей Зобнин (МГУ)

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

Wednesday, September 30, at 16.20 in room 781 of building VMK of Moscow State University

S.P.Polyakov (Computing Centre of RAS)

The problems of the indefinite summation of rational functions and the construction of telescoping operators for multivariate hypergeometric sequences are considered. Two approaches for the summation of rational functions are examined. The first approach avoids the full factorization of denominators while the second one uses such factorization. Within both approaches the algorithms for summation of rational functions are discussed, and new algorithms for summation with additional degree minimization of the summed part denominator and of the remainder numerator are proposed. The correctness of the Zeilberger algorithm in the homogeneous case is proved. This case is demonstrated to occur for any order of the telescoping operator. The algorithm for constructing the annihilating operator of minimal order is proposed. All the discussed algorithms are implemented in Maple.

С.П.Поляков (ВЦ РАН)

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

Wednesday, May 20, at 16.20 in room 786 of building VMK of Moscow State University

Alexander Aranson (Scientific Research Institute of Long-Range Radio Communication)

We consider algorithms of Power Geometry to calculate asymphtotic expansions of solutions of ODE systems. Author develops the collection of functions of the computer algebra system Maxima to apply these algorithms. We tested these functions by computation of known asymphtotic expansions of solutions of the autonomous Henon-Heiles ODE system. We consider the usage of these functions to calculate asymphtotic expansions of solutions of the non autonomous N. Kowalewski ODE system.

Александр Арансон (Научно Исследовательский институт Дальней Радиосвязи)

Рассматриваются алгоритмы степенной геометрии для вычисления асимптотических разложений решений систем ОДУ. Обсуждается разрабатываемый автором набор процедур для реализации этих алгоритмов в системе компьютерной алгебры Maxima . Процедуры протестированы на вычислении известных асимптотических разложений решений автономной системы ОДУ Хенона-Хейлеса. Рассматривается применение этих процедур для вычисления асимптотических разложений решений неавтономной системы ОДУ Н. Ковалевского.

Wednesday, April 15, at 16.20 in room 786 of building VMK of Moscow State University

Victor Edneral (Moscow State University)

The results were obtained jointly with Prof. A.D. Bruno, Keldysh Institute for Applied Mathematics RAS

We consider an autonomous system of ordinary differential equations, which is solved with respect to derivatives. To study local integrability of the system, we use an approach based on Power Geometry method and on the computation of the resonant normal form. For a planar 5-parametric example of such system, we found the set of necessary and sufficient conditions on parameters of the system at which the system is locally integrable near the degenerated stationary point.

Виктор Еднерал. Московский государственный университет им. М.В. Ломоносова

Работа выполнена совместно с Проф. А.Д. Брюно, ИПМ РАН им. М.В. Келдыша

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

Wednesday, March 18, at 16.20 in room 786 of building VMK of Moscow State University

Sergey D. Makhortov (Voronezh State University)

The term rewrite systems (TRS) occupy, to a certain extent, a boundary position between computer algebra and artificial intelligence. On the one hand, by means of TRS, the tasks of simplification of algebraic expressions are accomplished, on the other hand, the tasks of automatic theorem proving.

The important problems of rewrite systems are equivalent transformations and optimization of their sets of rules. In the case of standard systems the minimization problem is reduced to a transitive reduction of some binary relation. For conditional TRS, it is possible to speak about a more difficult and not yet solved problem of finding a logical reduction.

A starting point in defining a rewrite system is usually the equational theory, whose set of rules consists of equalities.

In the report the algebraic lattice-based models of conditional equational theories are presented. Each model is intended for the study and minimization of a set of rules at a certain level of detailing. Theorems of existence and method of construction of a logical reduction of the algebraic systems under consideration are proved, which in the application means the solution to the minimization problem of the corresponding sets of rules.

Sergei A. Abramov (Computing centre of RAS)

We consider linear difference equations with polynomial coefficients dependent on parameters, and prove that the existence problem of numeric values of parameters such that a given equation has a polynomial (a rational function) solution is undecidable (similarly to the proven by J.-A. Weil undecidability of the same problem in the differential case).

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

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

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

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

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

Абстракт доклада в формате PDF

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

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

Wednesday, February 18, at 16.20 in room 786 of building VMK of Moscow State University

Sergey Yu. Vernov (SINP MSU)

Cosmological models driven by a nonlocal scalar field inspired by the string field theory is studied. Distinguish property of those models is that the equations of motion are linear in Minkowski space-time. In non-flat space-time the Einstein equations are nonlinear, but equations of motion are linear in scalar field. This property allows localizing model to find special solutions. The considering linear nonlocal model is equivalent to an infinite number of local models. We have found exact special solutions of the nonlocal Friedmann equations. One of these solutions describes a monotonically increasing Universe with the phantom dark energy. The exact solutions of the equations were calculated by the MAPLE system.

Сергей Ю. Вернов (НИИЯФ МГУ)

Изучаются космологические модели с нелокальным скалярным полем, порождённые полевой теорией струн. Отличительным свойством данных моделей является линейность уравнений движения в пространстве Минковского. В искривлённом пространстве-времени уравнения Эйнштейна оказываются нелинейными, однако сохраняется свойство линейности уравнения движения относительно скалярного поля. Данное свойство позволяет локализовать модель для поиска частных решений. Рассматриваемая линейная нелокальная модель оказывается эквивалентной бесконечному числу локальных моделей. Найдены точные частные решения нелокальных уравнений Эйнштейна в метрике Фридмана. Одно из полученных решений описывает монотонно ускоряющуюся Вселенную с фантомной тёмной энергией. Точные решения соответствующих уравнений получены в системе MAPLE.

Thursday, January 22, 2009, at 17.00 in room 225-1 of building LKVE of Skobeltcyn Institute of Nuclear Physics, Moscow State University.

Nikolay K. Zaytsev. Professor of Chair of Industrial Ecology of Gubkin National University of Natural Oil and Gas

In December, 2008 the Dr. Alexander Aranson has kindly given to a management of our seminar a selection of scientific articles from area of chemical kinetics in which the formulation of studied problems is finished to statement of a mathematical problem. Research of the corresponding differential equations, probably, can be considered by computer algebra methods. We have asked Prof. Nikolay Zaytsev to tell us briefly an essence of the processes modeled by these equations.

The list of mentioned papers:

Damian E. Strier and Silvina Ponce Dawson. Rescaling of diffusion coefficients in two-time scale chemical systems.

Julie Dam, Carlos A. Velikovsky, Roy A. Mariuzza, Claus Urbanke and Peter Schuck. Sedimentation Velocity Analysis of Heterogeneous Protein-Protein Interactions: Lamm Equation Modeling and Sedimentation Coefficient Distributions c(s).

Hiroaki Takagi and Kunihiko Kaneko. Pattern Dynamics of a Multi-Component Reaction Diffusion System: Differentiation of Replicating Spots.

Yuichi Togashi and Kunihiko Kaneko. Molecular Discreteness in Reaction-Diffusion Systems Yields Steady States Not Seen in the Continuum Limit.

Николай К. Зайцев. Профессор кафедры промышленной экологии РГУ нефти и газа им. И.М. Губкина

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