Kinematic analysis of multibody systems

We discuss how to use constructive methods in commutative algebra to study multibody systems. The main focus is in the kinematic analysis, i.e. the analysis of the geometry of the configuration space. We show how to define and compute the mobility of the system and study various singularities of the configuration space. We also discuss implications of this analysis for numerical computations. AMS subject classification (2000)  13P10, 65L05, 68W30, 70B10     

A bivariate preprocessing paradigm for the Buchberger-Möller algorithm

For the last almost three decades, since the famous Buchberger-Möller (BM) algorithm emerged, there has been wide interest in vanishing ideals of points and associated interpolation polynomials. Our paradigm is based on the theory of bivariate polynomial interpolation on cartesian point sets that gives us a related degree reducing interpolation monomial and Newton bases directly. Since the bases are involved in the computation process as well as contained in the final output of the BM algorithm, our paradigm obviously simplifies the computation and accelerates the BM process. The experiments show that the paradigm is best suited for the computation over finite prime fields that have many applications.     

An Implementation for the Algorithm of Janet bases of Linear Differential Ideals in the Maple System

In this paper, an algorithm for computing the Janet bases of linear differential equations is described, which is the differential analogue of the algorithm JanetBasis improved by Gerdt. An implementation of the algorithm in Maple is given. The implemented algorithm includes some subalgorithms: Janet division,Pommaret division, the judgement of involutive divisor and reducible, the judgement of conventional divisor and reducible, involutive normal form and conventional normal form, involutive autoreduction and conventional autoreduction, PJ-autoreduction and so on. As an application, the Janet Bases of the determining system of classical Lie symmetries of some partial differential equations are obtained using our package.     

多元分次Lagrange插值

对多元多项式分次插值适定结点组的构造理论进行了深入的研究与探讨.在沿无重复分量代数曲线进行Lagrange插值的基础上,给出了沿无重复分量分次代数曲线进行分次Lagrane插值的方法,并利用这一结果进一步给出了在R~2上构造分次Lagrange插值适定结点组的基本方法.另外,利用弱Gr(o|¨)bner基这一新的数学概念,以及构造平面代数曲线上插值适定结点组的理论,进一步给出了构造平面分次代数曲线上分次插值适定结点组的方法,从而基本上弄清了多元分次Lagrange插值适定结点组的几何结构和基本特征.     

Monotonieeigenschaften des Steffensen-Verfahrens

Steffensen's method is slightly generalized by introducing a real parameter. In this way one can get different monotonicity properties, depending on the choice of this parameter. These monotonicity statements give the possibility of bracketing the solution of a given problem. In a special case they even ensure the convergence and the existence of a solution. Furthermore there are given sufficient conditions, which show that Steffensen's method converges at least as quickly as Newton's method. A numerical example shows the efficiency of the theorems and compares Steffensen's and Newton's method.

     

Numerical experiments on the accuracy of the Chebyshev–Frobenius companion matrix method for finding the zeros of a truncated series of Chebyshev polynomials

For a function f(x)$f(x)$ that is smooth on the interval x∈[a,b]$x\in [a,b]$ but otherwise arbitrary, the real-valued roots on the interval can always be found by the following two-part procedure. First, expand f(x)$f(x)$ as a Chebyshev polynomial series on the interval and truncate for sufficiently large N. Second, find the zeros of the truncated Chebyshev series. The roots of an arbitrary polynomial of degree N  , when written in the form of a truncated Chebyshev series, are the eigenvalues of an N×N$N\times N$ matrix whose elements are simple, explicit functions of the coefficients of the Chebyshev series. This matrix is a generalization of the Frobenius companion matrix. We show by experimenting with random polynomials, Wilkinson's notoriously ill-conditioned polynomial, and polynomials with high-order roots that the Chebyshev companion matrix method is remarkably accurate for finding zeros on the target interval, yielding roots close to full machine precision. We also show that it is easy and cheap to apply Newton's iteration directly to the Chebyshev series so as to refine the roots to full machine precision, using the companion matrix eigenvalues as the starting point. Lastly, we derive a couple of theorems. The first shows that simple roots are stable under small perturbations of magnitude ε$\epsilon$ to a Chebyshev coefficient: the shift in the root _x*$x_{*}$ is bounded by ε/df/dx(_x*)+O(ε²)$\epsilon /\mathrm{d}f/\mathrm{d}x(x_{*})+\mathrm{O}({\epsilon }^2)$ for sufficiently small ε$\epsilon$. Second, we show that polynomials with definite parity (only even or only odd powers of x) can be solved by a companion matrix whose size is one less than the number of nonzero coefficients, a vast cost-saving.     

Analysis of two Chebyshev-like third order methods free from second derivatives for solving systems of nonlinear equations

In this paper, two Chebyshev-like third order methods free from second derivatives are considered and analyzed for systems of nonlinear equations. The methods can be obtained by having different approximations to the second derivatives present in the Chebyshev method. We study the local and third order convergence of the methods using the point of attraction theory. The computational aspects of the methods are also studied using some numerical experiments including an application to the Chandrasekhar integral equations in Radiative Transfer.     

Computing border bases

This paper presents several algorithms that compute border bases of a zero-dimensional ideal. The first relates to the FGLM algorithm as it uses a linear basis transformation. In particular, it is able to compute border bases that do not contain a reduced Gröbner basis. The second algorithm is based on a generic algorithm by Bernard Mourrain originally designed for computing an ideal basis that need not be a border basis. Our fully detailed algorithm computes a border basis of a zero-dimensional ideal from a given set of generators. To obtain concrete instructions we appeal to a degree-compatible term ordering σ and hence compute a border basis that contains the reduced σ-Gröbner basis. We show an example in which this computation actually has advantages over Buchberger's algorithm. Moreover, we formulate and prove two optimizations of the Border Basis Algorithm which reduce the dimensions of the linear algebra subproblems.     

Inclusion of the roots of a polynomial based on Gerschgorin's theorem

Summary In this note a new companion matrix is presented which can be interpreted as a product of Werner's companion matrices [13]. Gerschgorin's theorem yields an inclusion of the roots of a polynomial which is best in the sense of [4] and generalizes a result of L. Elsner [5]. This inclusion is better than the one due to W. Börsch-Supan in [1].Dedicated to Professor E. Stein on the occasion of his 60th birthday.     

Artinian level modules of embedding dimension two

We prove that a sequence of positive integers (h₀,h₁,…,h_c) is the Hilbert function of an artinian level module of embedding dimension two if and only if h_i−1−2h_i+h_i+1≤0 for all 0≤i≤c, where we assume that h₋₁=h_c+1=0. This generalizes a result already known for artinian level algebras. We provide two proofs, one using a deformation argument, the other a construction with monomial ideals. We also discuss liftings of artinian modules to modules of dimension one.     

Gorenstein injective, Gorenstein flat modules and the section functor

Let R be a commutative Noetherian ring of Krull dimension d, and let a be an ideal of R. In this paper, we will study the strong cotorsioness and the Gorenstein injectivity of the section functor Γ_a(−) in local cohomology. As applications, we will find new characterizations for Gorenstein and regular local rings. We also study the effect of the section functors Γ_a(−) and the functors on the Auslander and Bass classes.     

Some geometric results arising from the Borel fixed property

In this paper, we will give some geometric results using generic initial ideals for the degree reverse lex order. The main goal of the paper is to improve on results of Bigatti, Geramita and Migliore concerning geometric consequences of maximal growth of the Hilbert function of the Artinian reduction of a set of points. When the points have the Uniform Position Property, the consequences are even more striking. Here we weaken the growth condition, assuming only that the values of the Hilbert function of the Artinian reduction are equal in two consecutive degrees, and that the first of these degrees is greater than the second reduction number of the points. We continue to get nice geometric consequences even from this weaker assumption. However, we have surprising examples to show that imposing the Uniform Position Property on the points does not give the striking consequences that one might expect. This leads to a better understanding of the Hilbert function, and the ideal itself, of a set of points with the Uniform Position Property, which is an important open question. In the last section we describe the role played by the Weak Lefschetz Property (WLP) in this theory, and we show that the general hyperplane section of a smooth curve may not have the WLP.     

BiCGStab,VPAStab and an adaptation to mildly nonlinear systems

The key equations of BiCGStab are summarised to show its connections with Padé and vector-Padé approximation. These considerations lead naturally to stabilised vector-Padé approximation of a vector-valued function (VPAStab), and an algorithm for the acceleration of convergence of a linearly generated sequence of vectors. A generalisation of this algorithm for the acceleration of convergence of a nonlinearly generated system is proposed here, and comparative numerical results are given.     

A generalized Taylor factorization for Hermite subdivision schemes

In a recent paper, we investigated factorization properties of Hermite subdivision schemes by means of the so-called Taylor factorization. This decomposition is based on a spectral condition which is satisfied for example by all interpolatory Hermite schemes. Nevertheless, there exist examples of Hermite schemes, especially some based on cardinal splines, which fail the spectral condition. For these schemes (and others) we provide the concept of a generalized Taylor factorization and show how it can be used to obtain convergence criteria for the Hermite scheme by means of factorization and contractivity.     

Termination of algorithm for computing relative Gr?bner bases and difference differential dimension polynomials

We introduce the concept of difference-differential degree compatibility on generalized term orders. Then we prove that in the process of the algorithm the polynomials with higher and higher degree would not be produced, if the term orders ‘?’ and ‘?′’ are difference-differential degree compatibility. So we present a condition on the generalized orders and prove that under the condition the algorithm for computing relative Gr?bner bases will terminate. Also the relative Gr?bner bases exist under the condition. Finally, we prove the algorithm for computation of the bivariate dimension polynomials in difference-differential modules terminates.     

On the hierarchy of cohomological dimensions of groups

Using Auslander’s G-dimension, we assign a numerical invariant to any group Γ. It provides a refinement of the cohomological dimension and fits well into the well-known hierarchy of dimensions assigned already to Γ. We study this dimension and show its power in reflecting the properties of the underlying group. We also discuss its connections to relative and Tate cohomology of groups.     

Cohomology theories for complexes

We introduce and study a complete cohomology theory for complexes, which provides an extended version of Tate–Vogel cohomology in the setting of (arbitrary) complexes over associative rings. Moreover, for complexes of finite Gorenstein projective dimension a notion of relative Ext is introduced. On the basis of these cohomology groups, some homological invariants of modules over commutative noetherian local rings, such as Martsinkovsky’s ξ-invariants and relative and Tate versions of Betti numbers, are extended to the framework of complexes with finite homology. The relation of these invariants with their prototypes is explored.