Splitting and composition methods for explicit time dependence in separable dynamical systems

We consider splitting methods for the numerical integration of separable non-autonomous differential equations. In recent years, splitting methods have been extensively used as geometric numerical integrators showing excellent performances (both qualitatively and quantitatively) when applied on many problems. They are designed for autonomous separable systems, and a substantial number of methods tailored for different structures of the equations have recently appeared. Splitting methods have also been used for separable non-autonomous problems either by solving each non-autonomous part separately or after each vector field is frozen properly. We show that both procedures correspond to introducing the time as two new coordinates. We generalize these results by considering the time as one or more further coordinates which can be integrated following either of the previous two techniques. We show that the performance as well as the order of the final method can strongly depend on the particular choice. We present a simple analysis which, in many relevant cases, allows one to choose the most appropriate split to retain the high performance the methods show on the autonomous problems. This technique is applied to different problems and its performance is illustrated for several numerical examples.     

On the Complexity of Sparse Elimination

Sparse elimination exploits the structure of a multivariate polynomial by considering its Newton polytope instead of its total degree. We concentrate on polynomial systems that generate zero-dimensional ideals. A monomial basis for the coordinate ring is defined from a mixed subdivision of the Minkowski sum of the Newton polytopes. We offer a new simple proof relying on the construction of a sparse resultant matrix, which leads to the computation of a multiplication map and all common zeros. The size of the monomial basis equals the mixed volume and its computation is equivalent to computing the mixed volume, so the latter is a measure of intrinsic complexity. On the other hand, our algorithms have worst-case complexity proportional to the volume of the Minkowski sum. In order to derive bounds in terms of the sparsity parameters, we establish new bounds on the Minkowski sum volume as a function of mixed volume. To this end, we prove a lower bound on mixed volume in terms of Euclidean volume which is of independent interest.     

Volume-preserving Fields and Reeb Fields on 3-manifolds

Volume-preserving field X on a 3-manifold is the one that satisfies LxΩ = 0 for some volume Ω. The Reeb vector field of a contact form is of volume-preserving, but not conversely. On the basis of Geiges-Gonzalo＇s parallelization results, we obtain a volume-preserving sphere, which is a triple of everywhere linearly independent vector fields such that all their linear combinations with constant coefficients are volume-preserving fields. From many aspects, we discuss the distinction between volume-preserving fields and Reeb-like fields. We establish a duality between volume-preserving fields and h-closed 2-forms to understand such distinction. We also give two kinds of non-Reeb-like but volume-preserving vector fields to display such distinction.     

Memory‐efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis

Novel memory‐efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so‐called quadratic Arnoldi method and two‐level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift‐and‐invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright © 2013 John Wiley & Sons, Ltd.     

Explicit Geometric Integration of Polynomial Vector Fields

We present a unified framework in which to study splitting methods for polynomial vector fields in R ⁿ . The vector field is to be represented as a sum of shears, each of which can be integrated exactly, and each of which is a function of k<n variables. Each shear must also inherit the structure of the original vector field: we consider Hamiltonian, Poisson, and volume-preserving cases. Each case then leads to the problem of finding an optimal distribution of points on an appropriate homogeneous space, generally the Grassmannians of k-planes or (in the Hamiltonian case) isotropic k-planes in R ⁿ . These optimization problems have the same structure as those of constructing optimal experimental designs in statistics.     

保结构算法的相位误差分析及其修正

辛算法和保能量算法是应用最为广泛的两种保结构算法.本文从相位误差的角度给出了他们的比较结果.我们针对线性动力系统,分别分析了基于Pade对角逼近给出的辛算法和基于平均向量场法得到的能量守恒算法的相位误差,并通过数值验证了分析结果.文章还给出了保结构算法相位误差的改进方法,并通过数值例子验证了方法的有效性.     

单边单项式序下的SAGBI基

设K是一个域,R是具有SM-基B的一个K-代数,且是B上一个单边（即左或右）单项式序.那么关于交换多项式代数和非交换自由代数的子代数在双边单项式序下经典的SAGBI基理论可完整地推广到R的子代数上来.特别地,对于一类N-分次代数,存在计算有限n-截断SAGBI基的有效算法,并且第一次阐明了在单边单项式序下讨论SAGBI...     

Bases for rings of coinvariants

We study the multiplicative structure of rings of coinvariants for finite groups. We develop methods that give rise to natural monomial bases for such rings over their ground fields and explicitly determine precisely which monomials are zero in the ring of coinvariants. We apply our methods to the Dickson, upper triangular and symmetric coinvariants. Along the way, we recover theorems of Steinberg [17] and E. Artin [1]. Using these monomial bases we prove that the image of the transfer for a general linear group over a finite field is a principal ideal in the ring of invariants. This research is supported in part by the Natural Sciences and Engineering Research Council of Canada     

Primitivity of finitely presented monomial algebras

We study prime monomial algebras. Our main result is that a prime finitely presented monomial algebra is either primitive or it has GK dimension one and satisfies a polynomial identity. More generally, we show that this result holds for the class of automaton algebras; that is, monomial algebras that have a basis consisting of the set of words recognized by some finite state automaton. This proves a special case of a conjecture of the first author and Agata Smoktunowicz.     

Notes on linear factor polynomial deflation in polynomial bases

Scalar polynomials as approximations to more general scalar functions lead to the study of scalar polynomials represented in a variety of classical systems of polynomials, including orthogonal systems and Lagrange polynomials, for example. This article, motivated in part by analogy with the existing methods for linear factor polynomial deflation in the monomial basis, finds forward and backward deflation formulae for several such representations. It also finds the sensitivity factor of the deflation process for each representation.     

Plane foliations with a saddle singularity

We study the set of planar vector fields with a unique singularity of hyperbolic saddle type. We found conditions to assure that a such vector field is topologically equivalent to a linear saddle. Furthermore, we describe the plane foliations associated to these vector fields. Such a foliation can be split in two subfoliations. One without restriction and another one that is topologically characterized by means of trees.     

Stanley conjecture in small embedding dimension

We show that Stanley's conjecture holds for a polynomial ring over a field in four variables. In the case of polynomial ring in five variables, we prove that the monomial ideals with all associated primes of height two, are Stanley ideals.     

Trees, parking functions, syzygies, and deformations of monomial ideals

For a graph , we construct two algebras whose dimensions are both equal to the number of spanning trees of . One of these algebras is the quotient of the polynomial ring modulo certain monomial ideal, while the other is the quotient of the polynomial ring modulo certain powers of linear forms. We describe the set of monomials that forms a linear basis in each of these two algebras. The basis elements correspond to -parking functions that naturally came up in the abelian sandpile model. These ideals are instances of the general class of monotone monomial ideals and their deformations. We show that the Hilbert series of a monotone monomial ideal is always bounded by the Hilbert series of its deformation. Then we define an even more general class of monomial ideals associated with posets and construct free resolutions for these ideals. In some cases these resolutions coincide with Scarf resolutions. We prove several formulas for Hilbert series of monotone monomial ideals and investigate when they are equal to Hilbert series of deformations. In the appendix we discuss the abelian sandpile model.

     

The proper interpolation space for multivariate Birkhoff interpolation

Multivariate Birkhoff interpolation problem has many important applications, such as in finite element method. In this paper two algorithms are given to compute the basis of the minimal interpolation space and the lower interpolation space respectively for an arbitrary given node set and the corresponding interpolation conditions on each node. We can get the monomial basis, Newton-type basis as well as Lagrange-type basis. The interpolation polynomial can be derived from the basis directly.     

A note on the representation of positive polynomials with structured sparsity

We consider real polynomials in finitely many variables. Let the variables consist of finitely many blocks that are allowed to overlap in a certain way. Let the solution set of a finite system of polynomial inequalities be given, where each inequality involves only variables of one block. We investigate polynomials that are positive on such a set and sparse in the sense that each monomial involves only variables of one block. In particular, we derive a short and direct proof for Lasserre’s theorem on the existence of sums of squares certificates respecting the block structure. The motivation for the results can be found in the literature on numerical methods for global optimization of polynomials that exploit sparsity. The first and the third author were supported by the DFG grant “Barrieren”. The second author was supported by “Studienstiftung des deutschen Volkes”.     

A monomial cycle basis on Koszul homology modules

We give a class of p-Borel principal ideals of a polynomial algebra over a field K for which the graded Betti numbers do not depend on the characteristic of K and the Koszul homology modules have a monomial cyclic basis.     

The improved split‐step θ methods for stochastic differential equation

Two improved split‐step θ methods, which, respectively, named split‐step composite θ method and modified split‐step θ‐Milstein method, are proposed for numerically solving stochastic differential equation of Itô type. The stability and convergence of these methods are investigated in the mean‐square sense. Moreover, an approach to improve the numerical stability is illustrated by choices of parameters of these two methods. Some numerical examples show the accordance between the theoretical and numerical results. Further numerical tests exhibit not only the Hamiltonian‐preserving property of the improved split‐step θ methods for a stochastic differential system but also the positivity‐preserving property of the modified split‐step θ‐Milstein method for the Cox–Ingersoll–Ross model. Copyright © 2013 John Wiley & Sons, Ltd.     

A parallel finite volume scheme preserving positivity for diffusion equation on distorted meshes

Parallel domain decomposition methods are natural and efficient for solving the implicity schemes of diffusion equations on massive parallel computer systems. A finite volume scheme preserving positivity is essential for getting accurate numerical solutions of diffusion equations and ensuring the numerical solutions with physical meaning. We call their combination as a parallel finite volume scheme preserving positivity, and construct such a scheme for diffusion equation on distorted meshes. The basic procedure of constructing the parallel finite volume scheme is based on the domain decomposition method with the prediction‐correction technique at the interface of subdomains: First, we predict the values on each inner interface of subdomains partitioned by the domain decomposition. Second, we compute the values in each subdomain using a finite volume scheme preserving positivity. Third, we correct the values on each inner interface using the finite volume scheme preserving positivity. The resulting scheme has intrinsic parallelism, and needs only local communication among neighboring processors. Numerical results are presented to show the performance of our schemes, such as accuracy, stability, positivity, and parallel speedup.© 2017 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 2159–2178, 2017     

Mixed finite elements for elasticity

Summary. There have been many efforts, dating back four decades, to develop stable mixed finite elements for the stress-displacement formulation of the plane elasticity system. This requires the development of a compatible pair of finite element spaces, one to discretize the space of symmetric tensors in which the stress field is sought, and one to discretize the space of vector fields in which the displacement is sought. Although there are number of well-known mixed finite element pairs known for the analogous problem involving vector fields and scalar fields, the symmetry of the stress field is a substantial additional difficulty, and the elements presented here are the first ones using polynomial shape functions which are known to be stable. We present a family of such pairs of finite element spaces, one for each polynomial degree, beginning with degree two for the stress and degree one for the displacement, and show stability and optimal order approximation. We also analyze some obstructions to the construction of such finite element spaces, which account for the paucity of elements available. Received January 10, 2001 / Published online November 15, 2001