Applying Gröbner basis techniques to group theory

We apply the machinery of Gröbner bases to finitely presented groups. This allows for computational methods to be developed which prove that a given finitely presented group is not n-linear over a field k assuming some mild conditions. We also present an algorithm which determines whether or not a finitely presented group G is trivial given that an oracle has told us that G is n-linear over an algebraically closed field k.     

The symmetric group given by a Gröbner basis

We present a Gröbner basis associated with the symmetric group of degree n, which is determined by a strong generating set of the symmetric group and is defined by means of a term ordering with the elimination property.     

A family of centered forms for a polynomial

The general centered form for multi-variate polynomials is investigated and a computing procedure is proposed that results in a certain superset. Based on this procedure the optimal centered forms for monomials and for some special cases of polynomials are investigated.     

Frozen divided difference scheme for solving systems of nonlinear equations

The development of an inverse first-order divided difference operator for functions of several variables, as well as a direct computation of the local order of convergence of an iterative method is presented. A generalized algorithm of the secant method for solving a system of nonlinear equations is studied and the maximum computational efficiency is computed. Furthermore, a sequence that approximates the order of convergence is generated for the examples and it confirms in a numerical way that the order of the methods is well deduced.     

The number of centered forms for a polynomial

A general centered form for polynomials is defined. This centered form is based on the concept of an arrangement of the variables of the polynomial. A formula for the number of arrangements of a term and of a polynomial is given. Some examples are computed showing that even polynomials with moderately many variables may have a very large number of possible centered forms.     

Gröbner bases of ideals cogenerated by Pfaffians

We characterise the class of one-cogenerated Pfaffian ideals whose natural generators form a Gröbner basis with respect to any anti-diagonal term order. We describe their initial ideals as well as the associated simplicial complexes, which turn out to be shellable and thus Cohen-Macaulay. We also provide a formula for computing their multiplicity.     

On the Gröbner complexity of matrices

In this paper we show that if for an integer matrix A the universal Gröbner basis of the associated toric ideal I_A coincides with the Graver basis of A, then the Gröbner complexity u(A) and the Graver complexity g(A) of its higher Lawrence liftings agree, too. In fact, if the universal Gröbner basis of I_A coincides with the Graver basis of A, then also the more general complexities u(A,B) and g(A,B) agree for arbitrary B. We conclude that for the matrices A_3×3 and A_3×4, defining the 3×3 and 3×4 transportation problems, we have u(A_3×3)=g(A_3×3)=9 and u(A_3×4)=g(A_3×4)≥27. Moreover, we prove that u(A_a,b)=g(A_a,b)=2(a+b)/gcd(a,b) for positive integers a,b and .     

Nonlinear reduction for solving deficient polynomial systems by continuation methods

Summary Neither continuation methods, nor symbolic elimination methods can be directly applied to compute all finite solutions to polynomial systems, because the amount of computational time is mostly not proportional to the dimension of the system and to the number of finite solutions. The notion of S-polynomials is used to developed a reduction algorithm to lower the total degree of the deficient polynomial system, so that computing the solutions at infinity can be avoided. Applying the reduction algorithm before solving the system with continuation methods, yields a reliable solution method.     

An efficient start system for multi-homogeneous polynomial continuation

Summary When solving a system of polynomial equations using homotopy continuation, the number of solution paths can often be significantly reduced by casting the equations in multi-homogeneous form. This requires a multi-homogeneous start system having a full set of nonsingular solutions that can be easily computed. We give a general form of such a start system that works for any multi-homogeneous structure and that can be used efficiently in continuation.     

Finding all solutions of separable systems of piecewise-linear equations using integer programming

Finding all solutions of nonlinear or piecewise-linear equations is an important problem which is widely encountered in science and engineering. Various algorithms have been proposed for this problem. However, the implementation of these algorithms are generally difficult for non-experts or beginners. In this paper, an efficient method is proposed for finding all solutions of separable systems of piecewise-linear equations using integer programming. In this method, we formulate the problem of finding all solutions by a mixed integer programming problem, and solve it by a high-performance integer programming software such as GLPK, SCIP, or CPLEX. It is shown that the proposed method can be easily implemented without making complicated programs. It is also confirmed by numerical examples that the proposed method can find all solutions of medium-scale systems of piecewise-linear equations in practical computation time.     

Study of linear information for classes of polynomial equations

Summary We study linear sequential (adaptive) information for approximating zeros of polynomials of unbounded degree and establish a theorem on constrained approximation of smooth functions by polynomials.For a positive we seek a pointx ^* such that|x ^* – _p | , where _p is a zero of a real polynomialp in the interval [a, b]. We assume thatp belongs to the classF ₁ of polynomials of bounded arbitrary seminorm and having a root in [a, b] or to the classF ₂ of polynomials which are nonpositive ata, nonnegative atb and have exactly one simple zero in [a, b]. The information onp consists ofn sequential (adaptive) evaluations of arbitrary linear functionals. The pointx ^* is constructed by means of an algorithm which is an arbitrary mapping depending on the information onp. We show that there exists no information and no algorithm for computingx ^* for everyp fromF ₁, no matter how large the value ofn is. This is a stronger result than that obtained by us for smooth functions.For the classF ₂ we can find a pointx ^* for arbitraryp and. Anoptimal algorithm, i.e., an algorithm with the smallest error, is thebisection of the smallest known interval containing the root ofp. We also exhibitoptimal information operators, i.e., the linear functionals for which the error of an optimal algorithm that uses them is minimal. It turns out that in the class of nonsequential (parallel) information, i.e., when the functionals are given simultaneously, optimal information consists of the evaluations of a polynomial atn-equidistant points in [a, b]. In the class of sequential continuous information, optimal information consists of evaluations of a polynomial atn points generated by thebisection method. To prove this result we establish a theorem on constrained approximation of smooth functions by polynomials. More precisely, we prove that a smooth function can be arbitrarily well uniformly approximated by a polynomial which satisfies constrains given byn arbitrary continuous linear functionals.Our results indicate that the problem of finding an -approximation to a real zero of a real polynomial (of unknown degree) is essentially of the same difficulty as the problem of finding an -approximation to a zero of an infinitely differentiable function.     

Gröbner bases for spaces of quadrics of codimension 3

Let R=⊕_i≥0R_i be an Artinian standard graded K-algebra defined by quadrics. Assume that dimR₂≤3 and that K is algebraically closed, of characteristic ≠2. We show that R is defined by a Gröbner basis of quadrics with, essentially, one exception. The exception is given by K[x,y,z]/I where I is a complete intersection of three quadrics not containing a square of a linear form.     

The random product homotopy and deficient polynomial systems

Summary Most systems ofn polynomial equations inn unknowns arising in applications aredeficient, in the sense that they have fewer solutions than that predicted by the total degree of the system. We introduce the random product homotopy, an efficient homotopy continuation method for numerically determining all isolated solutions of deficient systems. In many cases, the amount of computation required to find all solutions can be made roughly proportional to the number of solutions.     

Adaptive polynomial preconditioning for hermitian indefinite linear systems

This paper explores the use of polynomial preconditioned CG methods for hermitian indefinite linear systems,Ax=b. Polynomial preconditioning is attractive for several reasons. First, it is well-suited to vector and/or parallel architectures. It is also easy to employ, requiring only matrix-vector multiplication and vector addition. To obtain an optimum polynomial preconditioner we solve a minimax approximation problem. The preconditioning polynomial,C(), is optimum in that it minimizes a bound on the condition number of the preconditioned matrix,C(A)A. We also characterize the behavior of this minimax polynomial, which makes possible a thorough understanding of the associated CG methods. This characterization is also essential to the development of an adaptive procedure for dynamically determining the optimum polynomial preconditioner. Finally, we demonstrate the effectiveness of polynomial preconditioning in a variety of numerical experiments on a Cray X-MP/48. Our results suggest that high degree (20–50) polynomials are usually best.This research was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Dept. of Energy, by Lawrence Livermore National Laboratory under contract W-7405-ENG-48.This research was supported in part by the Dept. of Energy and the National Science Foundation under grant DMS 8704169.This research was supported in part by U.S. Dept. of Energy grant DEFG02-87ER25026 and by National Science Foundation grant DMS 8703226.     

Degree bounds for Gröbner bases in algebras of solvable type

We establish doubly-exponential degree bounds for Gröbner bases in certain algebras of solvable type over a field (as introduced by Kandri-Rody and Weispfenning). The class of algebras considered here includes commutative polynomial rings, Weyl algebras, and universal enveloping algebras of finite-dimensional Lie algebras. For the computation of these bounds, we adapt a method due to Dubé based on a generalization of Stanley decompositions. Our bounds yield doubly-exponential degree bounds for ideal membership and syzygies, generalizing the classical results of Hermann and Seidenberg (in the commutative case) and Grigoriev (in the case of Weyl algebras).     

Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons

Computations with univariate polynomials, like the evaluation of product, quotient, remainder, greatest common divisor, etc, are closely related to linear algebra computations performed with structured matrices having the Toeplitz-like or the Hankel-like structures.

The discrete Fourier transform, and the FFT algorithms for its computation, constitute a powerful tool for the design and analysis of fast algorithms for solving problems involving polynomials and structured matrices.

We recall the main correlations between polynomial and matrix computations and present two recent results in this field: in particular, we show how Fourier methods can speed up the solution of a wide class of problems arising in queueing theory where certain Markov chains, defined by infinite block Toeplitz matrices in generalized Hessenberg form, must be solved. Moreover, we present a new method for the numerical factorization of polynomials based on a matrix generalization of Koenig's theorem. This method, that relies on the evaluation/interpolation technique at the Fourier points, reduces the problem of polynomial factorization to the computation of the LU decomposition of a banded Toeplitz matrix with its rows and columns suitably permuted. Numerical experiments that show the effectiveness of our algorithms are presented     

On the computational efficiency index and some iterative methods for solving systems of nonlinear equations

In this paper two new iterative methods are built up and analyzed. A generalization of the efficiency index used in the scalar case to several variables in iterative methods for solving systems of nonlinear equations is revisited. Analytic proofs of the local order of convergence based on developments of multilineal functions and numerical concepts that will be used to illustrate the analytic results are given. An approximation of the computational order of convergence is computed independently of the knowledge of the root and the necessary time to get one correct decimal is studied in our examples.     

Interval iteration for zeros of systems of equations

Easily verifiable existence and convergence conditions are given for a class of interval iteration algorithms for the enclosure of a zero of a system of nonlinear equations. In particular, a quadratically convergent method is obtained which throughout the iteration uses the same interval enclosure of the derivative.     

Incomplete factorizations of singular linear systems

Recent works have shown that, whenA is a Stieltjes matrix, its so-called modified incomplete factorizations provide effective preconditioning matrices for solvingAx=b by polynomially accelerated iterative methods. We extend here these results to the singular case with the conclusion that the latter techniques are able to solve singular systems at the same speed as regular systems.Research supported by the Fonds National de la Recherche Scientifique (Belgium) — Aspirant.     

The generalized superoptimal preconditioner

For any given n-by-n matrix A, a specific circulant preconditioner t_F(A) introduced by Tyrtyshnikov [E. Tyrtyshnikov, Optimal and super-optimal circulant preconditioners, SIAM J. Matrix Anal. Appl. 13 (1992) 459-473] is defined to be the solution of