Euclid's algorithm and the Lanczos method over finite fields

This paper shows that there is a close relationship between the Euclidean algorithm for polynomials and the Lanczos method for solving sparse linear systems, especially when working over finite fields. It uses this relationship to account rigorously for the appearance of self-orthogonal vectors arising in the course of the Lanczos algorithm. It presents an improved Lanczos method which overcomes problems with self-orthogonality and compares this improved algorithm with the Euclidean algorithm.

     

Bezoutians, Euclidean Algorithm, and Orthogonal Polynomials

We prove a quadratic expression for the Bezoutian of two univariate polynomials in terms of the remainders for the Euclidean algorithm. In case of two polynomials of the same degree, or of consecutive degrees, this allows us to interpret their Bezoutian as the Christoffel- Darboux kernel for a finite family of orthogonal polynomials, arising from the Euclidean algorithm. We give orthogonality properties of remainders, and reproducing properties of Bezoutians. Received December 13, 2004     

Simple algorithms for approximating all roots of a polynomial with real roots

We present a simple algorithm for approximating all roots of a polynomial p(x) when it has only real roots. The algorithm is based on some interesting properties of the polynomials appearing in the Extended Euclidean Scheme for p(x) and p′(x). For example, it turns out that these polynomials are orthogonal; as a consequence, we are able to limit the precision required by our algorithm in intermediate steps. A parallel implementation of this algorithm yields a P-uniform NC₂ circuit, and the bit complexity of its sequential implementation is within a polylog factor of the bit complexity of the best known algorithm for the problem.     

Fourier Expansion of Disk Automorphisms via Scattering in Layered Media

A family of orthogonal polynomials on the disk (which we call scattering polynomials) serves to formulate a remarkable Fourier expansion of the composition of a sequence of Poincaré disk automorphisms. Scattering polynomials are tied to an exotic Riemannian structure on the disk that is hybrid between hyperbolic and Euclidean geometries, and the expansion therefore links this exotic structure to the usual hyperbolic one. The resulting identity is intimately connected with the scattering of plane waves in piecewise constant layered media. Indeed, a recently established combinatorial analysis of scattering sequences provides a key ingredient of the proof. At the same time, the polynomial obtained by truncation of the Fourier expansion elegantly encodes the structure of the nonlinear measurement operator associated with the finite time duration scattering experiment.     

Computing Syzygies by Faug��re��s F5 algorithm

In this paper, we introduce a new algorithm for computing a set of generators for the syzygies on a sequence of polynomials. For this, we extend a given sequence of polynomials to a Gr?bner basis using Faugère??s F₅ algorithm (A new efficient algorithm for computing Gr?bner bases without reduction to zero (F ₅). ISSAC, ACM Press, pp 75?C83, 2002). We show then that if we keep all the reductions to zero during this computation, then at termination (by adding principal syzygies) we obtain a basis for the module of syzygies on the input polynomials. We have implemented our algorithm in the computer algebra system Magma, and we evaluate its performance via some examples.     

On testing the divisibility of lacunary polynomials by cyclotomic polynomials

An algorithm is described that determines whether a given polynomial with integer coefficients has a cyclotomic factor. The algorithm is intended to be used for sparse polynomials given as a sequence of coefficient-exponent pairs. A running analysis shows that, for a fixed number of nonzero terms, the algorithm runs in polynomial time.

     

Fast algorithms for determining the linear complexities of sequences over GF(p~m) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p-1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(pm)(any positive integer m) with the period 3n (n and pm - 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-lmamura algorithm, we can determine the linear complexity of any sequence over GF(pm) with the period 3n (n and pm - 1 are coprime) more efficiently.     

The F<Subscript>4</Subscript>-algorithm for Euclidean rings

In this short note, we extend Faugére’s F₄-algorithm for computing Gröbner bases to polynomial rings with coefficients in an Euclidean ring. Instead of successively reducing single S-polynomials as in Buchberger’s algorithm, the F₄-algorithm is based on the simultaneous reduction of several polynomials.     

The stable computation of formal orthogonal polynomials

For many applications — such as the look-ahead variants of the Lanczos algorithm — a sequence of formal (block-)orthogonal polynomials is required. Usually, one generates such a sequence by taking suitable polynomial combinations of a pair of basis polynomials. These basis polynomials are determined by a look-ahead generalization of the classical three term recurrence, where the polynomial coefficients are obtained by solving a small system of linear equations. In finite precision arithmetic, the numerical orthogonality of the polynomials depends on a good choice of the size of the small systems; this size is usually controlled by a heuristic argument such as the condition number of the small matrix of coefficients. However, quite often it happens that orthogonality gets lost.We present a new variant of the Cabay-Meleshko algorithm for numerically computing pairs of basis polynomials, where the numerical orthogonality is explicitly monitored with the help of stability parameters. A corresponding error analysis is given. Our stability parameter is shown to reflect the condition number of the underlying Hankel matrix of moments. This enables us to prove the weak and strong stability of our method, provided that the corresponding Hankel matrix is well-conditioned.This work was partially supported by the HCM project ROLLS, under contract CHRX-CT93-0416.     

Function-valued Padé-type approximant via the formal orthogonal polynomials and its applications in solving integral equations

A kind of function-valued Padé-type approximant via the formal orthogonal polynomials (FPTAVOP) is introduced on the polynomial space and an algorithm is sketched by means of the formal orthogonal polynomials. This method can be applied to approximate characteristic values and the corresponding characteristic function of Fredholm integral equation of the second kind. Moreover, theoretical analyses show that FPTAVOP method is the most effective one for accelerating the convergence of a sequence of functions. In addition, a typical numerical example is presented to illustrate when the estimates of characteristic value and characteristic function by using this new method are more accurate than other methods.     

An Algorithm for Computing a Gröbner Basis of a Polynomial Ideal over a Ring with Zero Divisors

An algorithm for computing a Gr?bner basis of an ideal of polynomials whose coefficients are taken from a ring with zero divisors, is presented; such rings include \mathbb Z_n\mathbb {Z}_n and \mathbb Z_n[i]\mathbb {Z}_n[i], where n is not a prime number. The algorithm is patterned after (1) Buchberger’s algorithm for computing a Gr?bner basis of a polynomial ideal whose coefficients are from a field and (2) its extension developed by Kandri-Rody and Kapur when the coefficients appearing in the polynomials are from a Euclidean domain. The algorithm works as Buchberger’s algorithm when a polynomial ideal is over a field and as Kandri-Rody–Kapur’s algorithm when a polynomial ideal is over a Euclidean domain. The proposed algorithm and the related technical development are quite different from a general framework of reduction rings proposed by Buchberger in 1984 and generalized later by Stifter to handle reduction rings with zero divisors. These different approaches are contrasted along with the obvious approach where for instance, in the case of \mathbb Z_n{\mathbb {Z}}_n, the algorithm for polynomial ideals over \mathbb Z{\mathbb {Z}} could be used by augmenting the original ideal presented by polynomials over \mathbb Z_n{\mathbb {Z}}_n with n (similarly, in the case of \mathbb Z_n[i]{\mathbb {Z}}_n[i], the original ideal is augmented with n and i² + 1).     

An approximation algorithm for the hierarchical median problem

The hierarchical median problem asks for a hierarchical sequence of solutions to the k-median problems of growing cardinality. The best algorithm known for this problem in the general metric case has competitive ratio 20.71. In the paper, the case is under study that the clients and facilities lie on the real line, as well as the case of a Euclidean space. An algorithm is proposed with competitive ratio 8 in the case of the real line, and 8 + 4√2 (approximately 13.66), in the Euclidean case.     

Computation of eigenvalues and eigenvectors of a symmetric quindiagonal matrix

A recursive algorithm for the implicit derivation of the determinant of a symmetric quindiagonal matrix is developed in terms of its leading principal minors. The algorithm is shown to yield a Sturmian sequence of polynomials from which the eigenvalues can be obtained by use of the bisection process. Further modifications to the inverse iteration method using Wilkinson's technique (1962) yields the required eigenvectors.     

A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets

The method of projections onto convex sets to find a point in the intersection of a finite number of closed convex sets in a Euclidean space, may lead to slow convergence of the constructed sequence when that sequence enters some narrow “corridor” between two or more convex sets. A way to leave such corridor consists in taking a big step at different moments during the iteration, because in that way the monotoneous behaviour that is responsible for the slow convergence may be interrupted. In this paper we present a technique that may introduce interruption of the monotony for a sequential algorithm, but that at the same time guarantees convergence of the constructed sequence to a point in the intersection of the sets. We compare experimentally the behaviour concerning the speed of convergence of the new algorithm with that of an existing monotoneous algorithm.     

Fast algorithms for determining the linear complexities of sequences over GF(p m) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p ? 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m ? 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m ? 1 are coprime) more efficiently.     

Discriminants of polynomials in the Archimedean and non-Archimedean metrics

An upper bound for the number of cubic polynomials which have small discriminant in terms of the Euclidean and p-adic metrics simultaneously is obtained.     

On the GF(p) Linear Complexity of Hall's Sextic Sequences and Some Cyclotomic-Set-Based

Klapper (1994) showed that there exists a class of geometric sequences with the maximal possible linear complexity when considered as sequences over $GF(2)$, but these sequences have very low linear complexities when considered as sequences over $GF(p)(p$ is an odd prime). This linear complexity of a binary sequence when considered as a sequence over $GF(p)$ is called $GF(p)$ complexity. This indicates that the binary sequences with high $GF(2)$ linear complexities are inadequate for security in the practical application, while, their $GF(p)$ linear complexities are also equally important, even when the only concern is with attacks using the Berlekamp-Massey algorithm [Massey, J. L., Shift-register synthesis and bch decoding, {\it IEEE Transactions on Information Theory}, {\bf 15}(1), 1969, 122--127]. From this perspective, in this paper the authors study the $GF(p)$ linear complexity of Hall''s sextic residue sequences and some known cyclotomic-set-based sequences.     

Effective Isometric Embeddings for Certain Hermitian Holomorphic Line Bundles

We consider bihomogeneous polynomials on complex Euclidean spacesthat are positive outside the origin and obtain effective estimateson certain modifications needed to turn them into squares ofnorms of vector-valued polynomials on complex Euclidean space.The corresponding results for hypersurfaces in complex Euclideanspaces are also proved. The results can be considered as Hermitiananalogues of Hilbert's seventeenth problem on representing apositive definite quadratic form on Rⁿ as a sum of squares ofrational functions. They can also be regarded as effective estimateson the power of a Hermitian line bundle required for isometricprojective embedding. Further applications are discussed.     

Fast algorithms for determining the linear complexities of sequences over GF(pm) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p − 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m − 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m − 1 are coprime) more efficiently.     

Delaunay triangulation and the convex hull ofn points in expected linear time

An algorithm is presented which produces a Delaunay triangulation ofn points in the Euclidean plane in expected linear time. The expected execution time is achieved when the data are (not too far from) uniformly distributed. A modification of the algorithm discussed in the appendix treats most of the non-uniform distributions. The basis of this algorithm is a geographical partitioning of the plane into boxes by the well-known Radix-sort algorithm. This partitioning is also used as a basis for a linear time algorithm for finding the convex hull ofn points in the Euclidean plane.