Probabilistic absolute irreducibility test for polynomials

The absolute irreducibility of a polynomial with rational coefficients can usually be proved by detecting rational conditions on one of its reductions modulo some prime numbers. We show that the probability for these conditions to be realized is very high. The resulting fast algorithm is thus a good preliminary step for absolute factorization procedures of computer algebra systems.     

The computation of multiple roots of a polynomial

This paper considers structured matrix methods for the calculation of the theoretically exact roots of a polynomial whose coefficients are corrupted by noise, and whose exact form contains multiple roots. The addition of noise to the exact coefficients causes the multiple roots of the exact form of the polynomial to break up into simple roots, but the algorithms presented in this paper preserve the multiplicities of the roots. In particular, even though the given polynomial is corrupted by noise, and all computations are performed on these inexact coefficients, the algorithms ‘sew’ together the simple roots that originate from the same multiple root, thereby preserving the multiplicities of the roots of the theoretically exact form of the polynomial. The algorithms described in this paper do not require that the noise level imposed on the coefficients be known, and all parameters are calculated from the given inexact coefficients. Examples that demonstrate the theory are presented.     

Supertropical algebra

We develop the algebraic polynomial theory for “supertropical algebra,” as initiated earlier over the real numbers by the first author. The main innovation there was the introduction of “ghost elements,” which also play the key role in our structure theory. Here, we work somewhat more generally over an ordered monoid, and develop a theory which contains the analogs of several basic theorems of classical commutative algebra. This structure enables one to develop a Zariski-type algebraic geometric approach to tropical geometry, viewing tropical varieties as sets of roots of (supertropical) polynomials, leading to an analog of the Hilbert Nullstellensatz.Particular attention is paid to factorization of polynomials. In one indeterminate, any polynomial can be factored into linear and quadratic factors, and although unique factorization may fail, there is a “preferred” factorization that is explained both geometrically and algebraically. The failure of unique factorization in several indeterminates is explained by geometric phenomena described in the paper.     

Continuity properties for flat families of polynomials (I) Continuous parametrizations

Inspired by classical results in algebraic geometry, we study the continuity with respect to the coefficients, of the zero set of a system of complex homogeneous polynomials with a given pattern and when the Hilbert polynomial of the generated ideal is fixed. In this work we prove topological properties of some classifying spaces, e.g. the space of systems with given pattern, fixed Hilbert polynomial is locally compact, and we establish continuous parametrizations of Nullstellensatz formulae. In the general case we get local rational results but in the complex case we get global results using rational polynomials in the real and imaginary parts of the coefficients. In a second companion paper, we shall treat the continuity of zero sets for the Hausdorff distance, i.e., from a metric point of view.     

Number theory of matrix semigroups

Unlike factorization theory of commutative semigroups which are well-studied, very little literature exists describing factorization properties in noncommutative semigroups. Perhaps the most ubiquitous noncommutative semigroups are semigroups of square matrices and this article investigates the factorization properties within certain subsemigroups of M_n(Z), the semigroup of n×n matrices with integer entries. Certain important invariants are calculated to give a sense of how unique or non-unique factorization is in each of these semigroups.     

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.     

Explicit determination of generalized symmetric and alternating Galois groups

This paper shows a probabilistic algorithm to decide whether the Galois group of a given irreducible polynomial with rational coefficients is the generalized symmetric group C_p?S_m or the generalized alternating group C_p?A_m. In the affirmative case, we give generators of the group with their action on the set of roots of the polynomial.     

Multiplication of a Schubert polynomial by a Schur polynomial

Schur polynomials are a special case of Schubert polynomials. In this paper, we give an algorithm to compute the product of a Schubert polynomial with a Schur polynomial on the basis of Schubert polynomials. This is a special case of the general problem of the multiplication of two Schubert polynomials, where the corresponding algorithm is still missing. The main tools for the given algorithm is a factorization property of a special class of Schubert polynomials and the transition formula for Schubert polynomials.     

Gauss’ lemma and valuation theory

Gauss’ lemma is not only critically important in showing that polynomial rings over unique factorization domains retain unique factorization; it unifies valuation theory. It figures centrally in Krull’s classical construction of valued fields with pre-described value groups, and plays a crucial role in our new short proof of the Ohm-Ja?ard-Kaplansky theorem on Bezout domains with given lattice-ordered abelian groups. Furthermore, Eisenstein’s criterion on the irreducibility of polynomials as well as Chao’s beautiful extension of Eisenstein’s criterion over arbitrary domains, in particular over Dedekind domains, are also obvious consequences of Gauss’ lemma. We conclude with a new result which provides a Gauss’ lemma for Hermite rings.     

Using the Sherman-Morrison-Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems

A fast numerical algorithm for solving systems of linear equations with tridiagonal block Toeplitz matrices is presented. The algorithm is based on a preliminary factorization of the generating quadratic matrix polynomial associated with the Toeplitz matrix, followed by the Sherman-Morrison-Woodbury inversion formula and solution of two bidiagonal and one diagonal block Toeplitz systems. Tight estimates of the condition numbers are provided for the matrix system and the main matrix systems generated during the preliminary factorization. The emphasis is put on rigorous stability analysis to rounding errors of the Sherman-Morrison-Woodbury inversion. Numerical experiments are provided to illustrate the theory.     

Some remarks on Dvorcuk's root-finding method

Some properties of a method for factorization of a polynomial into quadratic factors and some remarks on Dvorcuk root-finding method are discussed. The results can be applied to the consideration of the global convergence of iterative processes.This work is partially supported by the Bulgarian Ministry of Science and Education, Contract MM-208/92.     

On coefficients of polynomials over finite fields

In this paper we study the relation between coefficients of a polynomial over finite field Fq and the moved elements by the mapping that induces the polynomial. The relation is established by a special system of linear equations. Using this relation we give the lower bound on the number of nonzero coefficients of polynomial that depends on the number m of moved elements. Moreover we show that there exist permutation polynomials of special form that achieve this bound when m|q−1. In the other direction, we show that if the number of moved elements is small then there is an recurrence relation among these coefficients. Using these recurrence relations, we improve the lower bound of nonzero coefficients when m?q−1 and . As a byproduct, we show that the moved elements must satisfy certain polynomial equations if the mapping induces a polynomial such that there are only two nonzero coefficients out of 2m consecutive coefficients. Finally we provide an algorithm to compute the coefficients of the polynomial induced by a given mapping with O(q3/2) operations.     

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     

The fast quartic solver

A fast and highly accurate algorithm for solving quartic equations is introduced. This new algorithm is more than six times as fast and several times more accurate than the quasi-standard Companion matrix eigenvalue quartic solver. Moreover, the method is exceptionally robust in cases of extreme root spread. The new algorithm is based on a factorization of the quartic in two quadratics, which are solved in closed form. The performance key at this point is a fixed-point iteration based fitting algorithm for backward optimization of the underlying quartic-to-quadratic polynomial decomposition. Detailed experimental results confirm our claims.     

Linear relations among algebraic solutions of differential equations

For any univariate polynomial with coefficients in a differential field of characteristic zero and any integer, q, there exists an associated nonzero linear ordinary differential equation (LODE) with the following two properties. Each term of the LODE lies in the differential field generated by the rational numbers and the coefficients of the polynomial, and the qth power of each root of the polynomial is a solution of this LODE. This LODE is called a qth power resolvent of the polynomial. We will show how one can get a resolvent for the logarithmic derivative of the roots of a polynomial from the αth power resolvent of the polynomial, where α is an indeterminate that takes the place of q. We will demonstrate some simple relations among the algebraic and differential equations for the roots and their logarithmic derivatives. We will also prove several theorems regarding linear relations of roots of a polynomial over constants or the coefficient field of the polynomial depending upon the (nondifferential) Galois group. Finally, we will use a differential resolvent to solve the Riccati equation.     

Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations

Summary. By providing a matrix version of Koenig's theorem we reduce the problem of evaluating the coefficients of a monic factor r(z) of degree h of a power series f(z) to that of approximating the first h entries in the first column of the inverse of an Toeplitz matrix in block Hessenberg form for sufficiently large values of n. This matrix is reduced to a band matrix if f(z) is a polynomial. We prove that the factorization problem can be also reduced to solving a matrix equation for an matrix X, where is a matrix power series whose coefficients are Toeplitz matrices. The function is reduced to a matrix polynomial of degree 2 if f(z) is a polynomial of degreeN and . These reductions allow us to devise a suitable algorithm, based on cyclic reduction and on the concept of displacement rank, for generating a sequence of vectors that quadratically converges to the vector having as components the coefficients of the factor r(z). In the case of a polynomial f(z) of degree N, the cost of computing the entries of given is arithmetic operations, where is the cost of solving an Toeplitz-like system. In the case of analytic functions the cost depends on the numerical degree of the power series involved in the computation. From the numerical experiments performed with several test polynomials and power series, the algorithm has shown good numerical properties and promises to be a good candidate for implementing polynomial root-finders based on recursive splitting strategies. Applications to solving spectral factorization problems and Markov chains are also shown. Received September 9, 1998 / Revised version received November 14, 1999 / Published online February 5, 2001     

A Factorization Theorem of Characteristic Polynomials of Convex Geometries

A convex geometry is a closure system whose closure operator satisfies the anti-exchange property. As is described in Sagan’s survey paper, characteristic polynomials factorize over nonnegative integers in several situations. We show that the characteristic polynomial of a 2-tight convex geometry K factorizes over nonnegative integers if the clique complex of the nbc-graph of K is pure and strongly connected. This factorization theorem is new in the sense that it does not belong to any of the three categories mentioned in Sagan’s survey. Received September 25, 2005     

General solution of certain matrix equations arising in filter design applications

In this work we present the explicit expression of all rectangular Toeplitz matrices B,C which verify the equation BB^H+CC^H=aI for some a>0. This matrix equation arises in some signal processing problems. For instance, it appears when designing the even and odd components of paraunitary filters, which are widely used for signal compression and denoising purposes. We also point out the relationship between the above matrix equation and the polynomial Bézout equation |B(z)|²+|C(z)|²=a>0 for |z|=1. By exploiting this fact, our results also yield a constructive method for the parameterization of all solutions B(z),C(z). The main advantage of our approach is that B and C are built without need of spectral factorization. Besides these theoretical advances, in order to illustrate the effectiveness of our approach, some examples of paraunitary filters design are finally given.