### 第四期符号计算暑期讲习班

#### 2015年8月3-9日，中国北京

### 专题学术演讲

报告题目 Involutive Monomial Division and Involutive Bases

报告人 Vladimir Gerdt 教授, Joint Institute for Nuclear Research, Russia

## 摘要(点击以展开/隐藏)

The concept of Gröbner bases for polynomial ideals together with the algorithmic characterization of these bases was invented 50 years ago by Austrian mathematician B.Buchberger in his PhD thesis. Since that time Gröbner bases have become the most universal algorithmic tool in commutative algebra and algebraic geometry. Moreover, this role of Gröbner bases was extended to rings of linear differential and shift operators and also to some noncommutative algebras. The fundamental property of a Gröbner basis of a polynomial ideal is the divisibility of any element in the related initial ideal by the leading monomial of an element in the basis. In our paper an algorithmic approach was developed based on an axiomatically formulated restriction for the conventional monomial division. This restricted division which we called involutive carries over the involutive methods from differential equations to commutative algebra and leads to a general concept of involutive bases. An involutive basis is a (generally redundant) Gröbner basis. An impetus was given to the involutive division technique with the experimental demonstration the efficiency of involutive algorithms as an alternative method to compute Gröbner bases.

The talk is a tutorial to the theory of involutive monomial division and involutive bases. First, we shall present a general receipt for construction of an involutive division and study their algorithmic properties needed for computation of involutive bases. Given a polynomial set and an admissible monomial order, the involutive division is defined by a suitable partition of the variables for each polynomial in the set under consideration. Among involutive divisions we single out is a wide class of pairwise divisions that includes classical separation of variables invented last century by French mathematician Janet . A pairwise division is generated by a total monomial ordering that need not to coincide with the admissible monomial ordering used for determination of the set of leading monomials.

Then we consider our involutive bases algorithms and study their efficiency issues. In so doing, we shall analyze computational efficiency of algorithms based on different involutive divisions. One of the important characterizations of computational efficiency of an involutive division is compactness of the corresponding involutive bases, i.e. the degree of their redundancy as Gröbner bases. We present a new class of partitions of variables determined in terms of the reduced Gröbner basis of the ideal generated by the leading monomial set and show that the new partition yields a more compact involutive basis then the conventional pairwise involutive division generated by the same total ordering. In particular, we show that the most compact involutive bases are generated by the antigraded monomial orderings. Our computer experiments demonstrate that the output bases for the antigraded lexicographic ordering have exponentially smaller, in the number of variables, cardinality than the conventional involutive bases.

报告题目 Understanding Quaternions

报告人 Ron Goldman 教授, Rice University, United States

## 摘要(点击以展开/隐藏)

Quaternions are vectors in 4-dimensions endowed with a rule for multiplication that is associative but not commutative, distributes through addition, and has an identity and inverses. Thus the quaternions form a division algebra. Ever since the discovery of quaternions, quaternion multiplication has been used to rotate vectors in 3-dimensions by sandwiching a vector between a unit quaternion and its conjugate.

In Computer Graphics quaternions have three principal applications: to increase speed and reduce memory for calculations involving rotations; to avoid distortions arising from numerical inaccuracies caused by floating point computations with rotations; and to interpolate between two rotations for key frame animation.

Yet while the formal algebra of quaternions -- multiplication, sandwiching, interpolation -- is well established in Computer Graphics, the geometry of quaternions is not well understood. The formulas for multiplication and sandwiching work, but it is hard to see how anyone ever came up with these formulas. Even the geometric meaning of a quaternion -- a scalar added to a vector -- is an enigma. The purpose of this talk is to develop a better intuitive understanding of quaternions, and to remove much of the mystery surrounding these formulas.

The main goal of this talk is to make five principal contributions:

1. To provide a fresh, geometric interpretation for quaternions, appropriate to contemporary
Computer Graphics;

2. To present better ways to visualize quaternions, and the effect of quaternion multiplication
on points and vectors in 3-dimensions;

3. To derive the formula for quaternion multiplication from first principles;

4. To develop simple, intuitive proofs of the sandwiching formulas for rotation and
reflection;

5. To show how to apply sandwiching to compute perspective projections.

报告题目 The moment-LP and moment-SOS hierarchies

报告人 Jean B. Lasserre 研究员, LAAS-CNRS and Institute of Mathematics, University of Toulouse, France

## 摘要(点击以展开/隐藏)

We review basic properties of the moment-LP and moment-SDP hierarchies for polynomial optimization and compare them. We also illustrate how to use such a methodology in two applications outside optimization. Namely:

+ For approximating (as closely as desired in a strong sense) sets defined with quantifiers of the form

*R _{f}* = {

**x**∈

**B**:

*f*(

**x**,

**y**) ≤ 0 for all

**y**such that (

**x**,

**y**)∈

**K**}

*D*= {

_{f}**x**∈

**B**:

*f*(

**x**,

**y**) ≤ 0 for some

**y**such that (

**x**,

**y**)∈

**K**}

by a hierarchy of *inner sublevel set approximations* Θ**k** = {**x** ∈ **B** : *J _{k}* (

**x**) ≤ 0} ⊂

*R*, or

_{f}*outer sublevel set approximations*Θ

**k**= {

**x**∈

**B**:

*J*(

_{k}**x**) ≤ 0} ⊃

*D*, for some polynomials (

_{f}*J*) of increasing degree.

_{k}+ For computing

*convex polynomial underestimators*of a given polynomial

*f*on a box

**B**⊂ R

^{n}.

报告题目 方程求解与密码算法分析

报告人 林东岱 研究员, 中国科学院信息工程研究所, 中国

## 摘要(点击以展开/隐藏)

密码学是数学应用的重要分支之一，是信息安全的核心技术，是保障信息的机密性、完整性和鉴别性的重要手段。密码算法的代数攻击是本世纪以来非常活跃的前沿研究课题之一，是密码算法设计与分析的有力工具，其核心则是代数方程组的求解。本报告将从流密码算法的代数攻击出发，介绍代数攻击的思想、方法以及由此产生的密码设计新准则。

报告题目 稀疏微分结式

报告人 袁春明 副研究员，中国科学院数学与系统科学研究院, 中国

## 摘要(点击以展开/隐藏)

结式给出超定方程组有公共解的充分必要条件，是代数几何与符号计算的基本概念和消去理论的主要计算工具之一。代数稀疏结式由著名数学家Gelfand等于上世纪90年代提出，充分考虑了多项式的稀疏结构，它构成了稀疏消去理论的基石。对于微分情形，作为微分结式的自然推广，同样应该考虑微分多项式的稀疏结构，因此，一个自然的问题是如何定义微分稀疏结式并研究其基本性质。我们在微分结式理论的基础上建立了微分稀疏结式的理论，同时给出了计算微分稀疏结式的高效算法。我们给出了微分稀疏结式存在的充分必要条件，证明了微分稀疏结式具有类似于微分结式的性质，比如分次齐次性，Poisson类型的分解公式等。同时，还给出了稀疏微分结式的阶及次数界的估计，特别的, 我们进一步证明了稀疏微分结式的微分阶数的上界是Jacobi界, 并以此为基础给出了计算稀疏微分结式的单指数算法。

报告题目 The Symbolic Side of Symbolic Computation

报告人 Stephen M. Watt 教授, University of Waterloo, Canada

## 摘要(点击以展开/隐藏)

Today, most of the work in computer algebra is focused on algorithms for the classical objects of algebra, including polynomials and linear algebra with coefficients from a variety of domains. This lecture shows how to extend the domain of symbolic computation to computing with mathematical quantities where the sizes or shapes are not known in advance. We will consider

+ polynomials where the exponents can be given by symbolic expressions,

+ matrices with blocks or other internal structure of symbolic size, and

+ piecewise functions where the shapes of the domains are given by symbolic expressions

For symbolic polynomials, there are various operations we want to be able to do, such as squaring *x ^{2n}*-1 to get

*x*-2

^{4n}*x*

^{2n}+1, or differentiating it to get 2

*nx*

^{2n-1}. In this lecture, we show how to compute their GCD, factorization and functional decomposition. For symbolic matrices, we show how to do arithmetic with blocks, bands and other structures where the dimensions are given by symbolic expressions. Finally, we consider the case of piecewise functions, where the regions of definition are symbolic. We show how hybrid sets, a generalization of multi-sets allowing negative multiplicities, can be used to reduce the computational complexity of working with these objects.

Siegfried M. Rump 教授, Hamburg University of Technology, Germany