Elimination and resultants. 1. Elimination and bivariate resultants

We discuss the relevance of elimination theory and resultants in computing, especially in computer graphics and CAGD. We list resultant properties to enhance overall understanding of resultants. For bivariate resultants, we present two explicit expressions: the Sylvester and the Bezout determinants. The Sylvester matrix is easier to construct, but the symmetrical Bezout matrix is structurally richer and thus sometimes more revealing. It let Kajiya (1982) observe directly that a line and a bicubic patch could intersect in at most 18 points, not 36 points, as a naive analysis would presume. For Bezier curves, there is an interesting algebraic and geometric relationship between the implicit equation in Bezout determinant form and the properties of end point interpolation and de Casteljau subdivision. When the two polynomials are of different degrees, the Bezout resultant suffers from extraneous factors. Fortunately, we can easily discard these factors. For problems related to surfaces, we need multivariate resultants: in particular, multivariate resultants for three homogeneous polynomials in three variables     

New algorithms for generating Conway polynomials over finite fields

Arithmetic in a finite field of prime characteristic p normally employs an irreducible polynomial in $\text{Z}{}_{\mathrm{p}}\text{[X]}$. A particular class of irreducible polynomials, generally known as Conway polynomials, provides a means for representing several finite fields of characteristic p in a compatible manner. Conway polynomials are used in computational algebra systems such as GAP and Magma to represent finite fields. The generation of the Conway polynomial for a particular finite field has previously been done by an often expensive brute force search. We present two new algorithms for generating Conway polynomials that avoid the brute force search. We have implemented one of these algorithms in Magma and present numerous new Conway polynomials generated by our implementation.     

Accelerating generators of iterative methods for finding multiple roots of nonlinear equations

Two accelerating generators that produce iterative root-finding methods of arbitrary order of convergence are presented. Primary attention is paid to algorithms for finding multiple roots of nonlinear functions and, in particular, of algebraic polynomials. First, two classes of algorithms for solving nonlinear equations are studied: those with a known order of multiplicity and others with no information on multiplicity. We also demonstrate the acceleration of iterative methods for the simultaneous approximations of multiple roots of algebraic polynomials. A discussion about the computational efficiency of the root-solvers considered and three numerical examples are given.     

Radical parametrizations of algebraic curves by adjoint curves

We present algorithms for parametrizing by radicals an irreducible curve, not necessarily plane, when the genus is less than or equal to 4 and the curve is defined over an algebraically closed field of characteristic zero. In addition, we also present an algorithm for parametrizing by radicals any irreducible plane curve of degree d having at least a point of multiplicity d−r, with 1≤r≤4 and, as a consequence, every irreducible plane curve of degree d≤5 and every irreducible singular plane curve of degree 6.     

Optimal Algorithm for Algebraic Factoring

This paper presents on optimized method for factoring multivariate polynomials over algebraic extension fields defined by an irreducible ascending set. The basic idea is to convert multivariate polynomials to univariate polynomials and algebraic extension fields to algebraic number fields by suitable integer substituteions.Then factorize the univariate polynomials over the algebraic number fields.Finally,construct mulativariate factors of the original polynomial by Hensel lemma and TRUEFACTOR test.Some examples with timing are included.     

找到一切非负整系数不可约多项式的一种新方法与算法

本文利用一种独特的映射方法将非负整系数多项式转化为正整数。运用该方法及数论理论，借助于计算机程序，可以找到任意多个非负整系数不可约多项式，并且可以对这些不可约多项式进行排序，这样，为扩频通信与信道密码利用不可约多项式提供了一种实用的算法，通过上机编程操作，结果说明本文提供的映射方法和寻找不可约多项式的方法十分实用，有效。     

Interval Partitions and Polynomial Factorization

The fastest algorithms for factoring a univariate polynomial f of degree n over a finite field use a baby-step/giant-step approach. The set {1,…,n} of potential factor degrees is partitioned into intervals. In a first stage, for each interval the product of all irreducible factors with degree in the interval is determined, generalizing the method of Cantor & Zassenhaus. In a second stage, each polynomial corresponding to a multi-factor interval—containing two or more irreducible factors—is completely factored. The goal in this work is to analyze the behavior of this algorithm on uniformly random squarefree input polynomials, for various partitions. To this end, we study several parameters such as the expected number of multi-factor intervals, the expected number of irreducible factors with degrees lying in multi-factor intervals, the number of gcds executed in the factoring process, the expected total degree among the irreducible factors with degrees in multi-factor intervals, and the probability of a polynomial to have no multi-factor interval. We concentrate on partitions with polynomially growing interval sizes, and determine the partition that minimizes the expected number of gcds.     

Real algebraic numbers and polynomial systems of small degree

Based on precomputed Sturm–Habicht sequences, discriminants and invariants, we classify, isolate with rational points, and compare the real roots of polynomials of degree up to 4. In particular, we express all isolating points as rational functions of the input polynomial coefficients. Although the roots are algebraic numbers and can be expressed by radicals, such representation involves some roots of complex numbers. This is inefficient, and hard to handle in applications in geometric computing and quantifier elimination. We also define rational isolating points between the roots of the quintic. We combine these results with a simple version of Rational Univariate Representation to isolate all common real roots of a bivariate system of rational polynomials of total degree ≤2 and to compute the multiplicity of these roots. We present our software within library synaps and perform experiments and comparisons with several public-domain implementations. Our package is 2–10 times faster than numerical methods and exact subdivision-based methods, including software with intrinsic filtering.     

Deterministic distinct-degree factorization of polynomials over finite fields

A deterministic polynomial time algorithm is presented for finding the distinct-degree factorization of multivariate polynomials over finite fields. As a consequence, one can count the number of irreducible factors of polynomials over finite fields in deterministic polynomial time, thus resolving a theoretical open problem of Kaltofen from 1987.     

A new approach to the symbolic factorization of multivariate polynomials

A heuristic factorization scheme that uses learning and other heuristic programming techniques to improve the efficiency of determining the symbolic factorization of multivariate polynomials with integer coefficients and an arbitrary number of variables and terms is described. The learning program, POLYFACT, in which the factorization scheme is implemented is also described. POLYFACT uses learning through the dynamic construction and manipulation of first-order predicate calculus heuristics to reduce the amount of searching for the irreducible factors of a polynomial.Tables containing the results of factoring randomly generated multivariate polynomials are presented: (1) to demonstrate that learning does improve considerably the efficiency of factoring polynomials, and (2) to show that POLYFACT does learn from previous experience.The factorization times of polynomials factored by both the scheme implemented in POLYFACT and Wang's implementation of Berlekamp's algorithm are given. The two algorithms are compared, and two situations where POLYFACT'S algorithm can be used to improve the efficiency of Wang's algorithm are discussed.     

A complete algorithm for automated discovering of a class of inequality-type theorems

Making use of the discriminant sequence for polynomials, WR algorithm, Wu' s elimination and a partial cylindrical algebraic decomposition, we present here a practical algorithm for automated inequality discovering which can discover new inequalities automatically without requiring to put forward any conjectures beforehand. That is complete for an extensive class of inequality-type theorems. Also this algorithm is applied to the classification of the real physical solutions of geometric constraint problems. Many inequalities with various backgrounds have been discovered or rediscovered by our program, DISCOVERER, which implements the algorithm in Maple.     

Necessary conditions for Hadamard factorizations of Hurwitz polynomials

A property of Hurwitz polynomials is related with the Hadamard product. Garloff and Wagner proved that Hadamard products of Hurwitz polynomials are Hurwitz polynomials, and Garloff and Shrinivasan shown that there are Hurwitz polynomials of degree 4 which do not have a Hadamard factorization into two Hurwitz polynomials of the same degree 4. In this paper, we give necessary conditions for an even-degree Hurwitz polynomial to have a Hadamard factorization into two even-degree Hurwitz polynomials; such conditions are given in terms of the coefficients of the given polynomial alone. Furthermore, we show that if an odd-degree Hurwitz polynomial has a Hadamard factorization then a system of nonlinear inequalities has at least one solution.     

Efficient generation of secure elliptic curves

In many cryptographic applications it is necessary to generate elliptic curves (ECs) whose order possesses certain properties. The method that is usually employed for the generation of such ECs is the so-called Complex Multiplication method. This method requires the use of the roots of certain class field polynomials defined on a specific parameter called the discriminant. The most commonly used polynomials are the Hilbert and Weber ones. The former can be used to generate directly the EC, but they are characterized by high computational demands. The latter have usually much lower computational requirements, but they do not directly construct the desired EC. This can be achieved if transformations of their roots to the roots of the corresponding (generated by the same discriminant) Hilbert polynomials are provided. In this paper we present a variant of the Complex Multiplication method that generates ECs of cryptographically strong order. Our variant is based on the computation of Weber polynomials. We present in a simple and unifying manner a complete set of transformations of the roots of a Weber polynomial to the roots of its corresponding Hilbert polynomial for all values of the discriminant. In addition, we prove a theoretical estimate of the precision required for the computation of Weber polynomials for all values of the discriminant. We present an extensive experimental assessment of the computational efficiency of the Hilbert and Weber polynomials along with their precision requirements for various discriminant values and we compare them with the theoretical estimates. We further investigate the time efficiency of the new Complex Multiplication variant under different implementations of a crucial step of the variant. Our results can serve as useful guidelines to potential implementers of EC cryptosystems involving generation of ECs of a desirable order on resource limited hardware devices or in systems operating under strict timing response constraints. This work was partially supported by the IST Programme of EC under contract no. IST-2001-33116 (FLAGS), and by the Action IRAKLITOS (Fellowships for Research in the University of Patras) with matching funds from ESF (European Social Fund) and the Greek Ministry of Education.     

On the algebraic fitting of experimental thermodynamic data with special regard to employing of orthonormal polynomials

Following the Weierstrass approximation theorem the thermodynamic excess functions are representable with arbitrary high accuracy by means of polynomials of sufficient high degrees in the mole fraction x. So, algebraic fitting of experimental thermodynamic excess data can be based upon mathematical polynomial expressions without any loss of generality. With respect to the necessary scattering of experimental results, algebraic evaluation of those data can only be solved by employing the calculus of observations. The least square method is the only principle of fitting with full justification by statistical mathematics, and which can be applied directly for algebraic fitting of experimental data by means of a computer. The general linear problem of fitting is solved explicitly (i) by means of Gauss method of elimination, and (ii) by employing the property of “orthonormality” of polynomials. In the latter case the explicit form of the “orthonormal” polynomials depends strongly on the number of experimental data which has to be fitted. A convenient procedure is presented to generate polynomials which are orthonormal with respect to an actual set of experimental data. Computer-programs in PORTRAN-language are enclosed 1) to employ Gauss method of elimination, and 2) to generate discrete orthonormal polynomials.     

Simultaneous stabilization of two discrete-time plants using a2-periodic controller

A generic method for designing a 2-periodic controller for the simultaneous placement of the closed-loop poles of two single-input-single-output discrete shift-invariant plants at the origin is presented. The method consists of first recasting the simultaneous pole-placement problem as one of solving a coupled pair of linear polynomial equations involving three unknown polynomials, and then obtaining the controller parameters in terms of the coefficients of these polynomials. The isolated cases for which such pole placement is not possible have been listed. Simulation results show that the performances of systems thus compensated are superior to their performances when compensated using the higher periodicity controllers suggested in literature     

On the sensitivities of multiple eigenvalues

We consider the generalized symmetric eigenvalue problem where matrices depend smoothly on a parameter. It is well known that in general individual eigenvalues, when sorted in accordance with the usual ordering on the real line, do not depend smoothly on the parameter. Nevertheless, symmetric polynomials of a number of eigenvalues, regardless of their multiplicity, which are known to be isolated from the rest depend smoothly on the parameter. We present explicit readily computable expressions for their first derivatives. Finally, we demonstrate the utility of our approach on a problem of finding a shape of a vibrating membrane with a smallest perimeter and with prescribed four lowest eigenvalues, only two of which have algebraic multiplicity one.     

Finding maximal orders in semisimple algebras over Q

We consider the algorithmic problem of constructing a maximal order in a semisimple algebra over an algebraic number field. A polynomial time ff-algorithm is presented to solve the problem. (An ffalgorithm is a deterministic method which is allowed to call oracles for factoring integers and for factoring polynomials over finite fields. The cost of a call is the size of the input given to the oracle.) As an application, we give a method to compute the degrees of the irreducible representations over an algebraic number fieldK of a finite groupG, in time polynomial in the discriminant of the defining polynomial ofK and the size of a multiplication table ofG.     

On Polynomial Decompositions

We present a new polynomial decomposition which generalizes the functional and homogeneous bivariate decomposition of irreducible monic polynomials in one variable over the rationals. With these decompositions it is possible to calculate the roots of an imprimitive polynomial by solving polynomial equations of lower degree.     

On robust Hurwitz polynomials

In this note, Kharitonov's theorem on robust Hurwitz polynomials is simplified for low-order polynomials. Specifically, forn = 3, 4, and 5, the number of polynomials required to check robust stability is one, two, and three, respectively, instead of four. Furthermore, it is shown that forn geq 6, the number of polynomials for robust stability checking is necessarily four, thus further simplification is not possible. The same simplifications arise in robust Schur polynomials by using the bilinear transformation. Applications of these simplifications to two-dimensional polynomials as well as to robustness for single parameters are indicated.