A Toeplitz algorithm for polynomial J-spectral factorization

A block Toeplitz algorithm is proposed to perform the J-spectral factorization of a para-Hermitian polynomial matrix. The input matrix can be singular or indefinite, and it can have zeros along the imaginary axis. The key assumption is that the finite zeros of the input polynomial matrix are given as input data. The algorithm is based on numerically reliable operations only, namely computation of the null-spaces of related block Toeplitz matrices, polynomial matrix factor extraction and linear polynomial matrix equations solving.     

Resolution des systemes d'equations algebriques

Let f₁,…,f_k be k multivariate polynomials which have a finite number of common zeros in the algebraic closure of the ground field, counting the common zeros at infinity. An algorithm is given and proved which reduces the computations of these zeros to the resolution of a single univariate equation which degree is the number of common zeros. This algorithm gives the whole algebraic and geometric structure of the set of zeros (multiplicities, conjugate zeros,...). When all the polynomials have the same degree, the complexity of this algorithm is polynomial relatively to the generic number of solutions.     

On polynomial matrix spectral factorization by symmetric extraction

We revise the 1963 Davis algorithm [2] for the spectral factorization of a para-Hermitian nonnegative polynomial matrixPhi, by symmetric factor extraction: this algorithm is careless about zeros at infinity. By introducing the notion of diagonal reducedness ofPhi, we obtain an easy sufficient test for the absence of zeros at infinity. We show then how to getPhi, diagonally reduced by diagonal excess reduction steps (similar to the Oono and Yasuura steps), removing all zeros at infinity, and then how to remove synunetrically finite zeros while keeping el, diagonally reduced (hence, free of zeros at infinity). This results in a revised symmetric extraction spectral factorization algorithm with monotone degree control. An example shows the didactical conceptual simplicity of the method. Appropriate symmetric extraction is discovered by revising and discovering important particular one-sided factor extraction properties of polynomial matrices.     

A New Sparse Gaussian Elimination Algorithm and the Niederreiter Linear System for Trinomials over F 2

An important factorization algorithm for polynomials over finite fields was developed by Niederreiter. The factorization problem is reduced to solving a linear system over the finite field in question, and the solutions are used to produce the complete factorization of the polynomial into irreducibles. One charactersistic feature of the linear system arising in the Niederreiter algorithm is the fact that, if the polynomial to be factorized is sparse, then so is the Niederreiter matrix associated with it. In this paper, we investigate the special case of factoring trinomials over the binary field. We develop a new algorithm for solving the linear system using sparse Gaussian elmination with the Markowitz ordering strategy. Implementing the new algorithm to solve the Niederreiter linear system for trinomials over F₂ suggests that, the system is not only initially sparse, but also preserves its sparsity throughout the Gaussian elimination phase. When used with other methods for extracting the irreducible factors using a basis for the solution set, the resulting algorithm provides a more memory efficient and sometimes faster sequential alternative for achieving high degree trinomial factorizations over F₂.     

Univariate Polynomials: Nearly Optimal Algorithms for Numerical Factorization and Root-finding

To approximate all roots (zeros) of a univariate polynomial, we develop two effective algorithms and combine them in a single recursive process. One algorithm computes a basic well isolated zero-free annulus on the complex plane, whereas another algorithm numerically splits the input polynomial of the n th degree into two factors balanced in the degrees and with the zero sets separated by the basic annulus. Recursive combination of the two algorithms leads to computation of the complete numerical factorization of a polynomial into the product of linear factors and further to the approximation of the roots. The new root-finder incorporates the earlier techniques of Schönhage, Neff/Reif, and Kirrinnis and our old and new techniques and yields nearly optimal (up to polylogarithmic factors) arithmetic and Boolean cost estimates for the computational complexity of both complete factorization and root-finding. The improvement over our previous record Boolean complexity estimates is by roughly the factor of n for complete factorization and also for the approximation of well-conditioned (well isolated) roots, whereas the same algorithm is also optimal (under both arithmetic and Boolean models of computing) for the worst case input polynomial, whose roots can be ill-conditioned, forming clusters. (The worst case complexity bounds for root-finding are supported by our previous algorithms as well.) All algorithms allow processor efficient acceleration to achieve solution in polylogarithmic parallel time.     

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.     

On the Deterministic Complexity of Factoring Polynomials

The paper focuses on the deterministic complexity of factoring polynomials over finite fields assuming the extended Riemann hypothesis (ERH). By the works of Berlekamp (1967, 1970) and Zassenbaus (1969), the general problem reduces deterministically in polynomial time to finding a proper factor of any squarefree and completely splitting polynomial over a prime field F_p. Algorithms are designed to split such polynomials. It is proved that a proper factor of a polynomial can be found deterministically in polynomial time, under ERH, if its roots do not satisfy some stringent condition, called super square balanced. It is conjectured that super square balanced polynomials do not exist.     

Computing the Primary Decomposition of Zero-dimensional Ideals

Let K be an infinite perfect computable field and let I ⊆ K [ x ] be a zero-dimensional ideal represented by a Gröbner basis. We derive a new algorithm for computing the reduced primary decomposition of I using only standard linear algebra and univariate polynomial factorization techniques. In practice, the algorithm generally works in finite fields of large characteristic as well.     

An algorithm for polynomial matrix factor extraction

An algorithm is described for extracting a polynomial matrix factor featuring any subset of the zeros of a given non-singular polynomial matrix. It is assumed that the zeros to be extracted are given as input data. Complex or repeated zeros are allowed. The algorithm is based on interpolation and relies upon numerically reliable subroutines only. It makes use of a procedure that computes the generalized characteristic vectors of a polynomial matrix at a given point. The extracted factor is provided in column- and row-reduced Popov form. Applications of the algorithm include polynomial matrix interpolation, plus/minus factorization, column- and row-reduction, or computation of the Smith form of a polynomial matrix. The numerical routines described in this paper are implemented in the new release 2.0 of the Polynomial Toolbox for MATLAB.     

Computing with algebraically closed fields

A practical computational system is described for computing with an algebraic closure of a field. The system avoids factorization of polynomials over extension fields, but gives the illusion of a genuine field to the user. All roots of an arbitrary polynomial defined over such an algebraically closed field can be constructed and are easily distinguished within the system. The difficult case of inseparable extensions of function fields of positive characteristic is also handled properly by the system. A technique of modular evaluation into a finite field critically ensures that a unique genuine field is simulated by the system but also provides fast optimizations for some fundamental operations. Fast matrix techniques are also used for several non-trivial operations. The system has been successfully implemented within the Magma Computer Algebra System, and several examples are presented, using this implementation.     

Security analysis of the public key algorithm based on Chebyshev polynomials over the integer ring ZN

Recently Kocarev and Tasev [20] proposed to use Chebyshev polynomials over real numbers to design a public key algorithm by employing the semigroup property. Bergamo et al. [4] pointed out that the public key algorithm based on Chebyshev polynomials working on real numbers is not secure and devised an attack which permits to recover the corresponding plaintext from a given ciphertext. Later Kocarev et al. [19] generalized the Chebyshev polynomials from real number fields to finite fields and finite rings to make the public key algorithm more secure and practical. However, we analyzed the period distribution of the sequences generated by the Chebyshev polynomials over finite fields [21]. When the modulus N is prime, we found this algorithm was also not secure and proposed an attack on this algorithm over finite fields. We then proposed some schemes to improve the security. In this paper, we further analyze in detail the period distribution of the sequences generated by Chebyshev polynomials over the integer ring Z_N when N is composite. It turns out that the period distribution is poor if N is not chosen properly and there are many small periods, which are not secure in the sense of cryptology. Based on these findings, we devise an attack on the public key algorithm based on Chebyshev polynomials over the integer ring Z_N. We also propose some suggestions to avoid this attack.     

A fast algorithm to compute irreducible and primitive polynomials in finite fields

In this paper we present a method to computeall the irreducible and primitive polynomials of degreem over the finite fieldGF(q). Our method finds each new irreducible or primitive polynomial with a complexity ofO(m) arithmetic operations inGF(q). The best previously known methods [3], [10] use the Berlekamp-Massey algorithm [7] and they have a complexityO(m ²). We reach mis improvement taking into account a systolic implementation [2] of the extended Euclidean algorithm instead of using the Berlekamp-Massey algorithm.This work was supported in part by Spanish Grant CICYT TIC91-0472.     

A note on Gao’s algorithm for polynomial factorization

Shuhong Gao (2003) [6] has proposed an efficient algorithm to factor a bivariate polynomial f over a field F. This algorithm is based on a simple partial differential equation and depends on a crucial fact: the dimension of the polynomial solution space G associated with this differential equation is equal to the number r of absolutely irreducible factors of f. However, this holds only when the characteristic of F is either zero or sufficiently large in terms of the degree of f. In this paper we characterize a vector subspace of G for which the dimension is r, regardless of the characteristic of F, and the properties of Gao’s construction hold. Moreover, we identify a second vector subspace of G that leads to an analogous theory for the rational factorization of f.     

A NOTE ON “DECOMPOSITION PROBLEM OF FUZZY RELATIONS”

The decomposition problem of a fuzzy relation R ∈ F(X × X) can be stated as: “Given a fuzzy relation R∈F(X ×.X), to determine whether there exists a fuzzy relation Z∈f(X × X) such that R = Z [Odot] Z, where X is a finite set and “[Odot]” is the max-min composition of two fuzzy relations.” In particular, if R is a Boolean matrix, then this problem becomes to find the square root of a Boolean matrix, which is a well-known unsolved problem. In 1985, Di Nola et al. (A. Di Nola, S. Sessa and W. Pedrycz, Int J. General Systems,. 10, 1985, 123?133) had solved it in theory, and proposed a numerical algorithm, illustrated by a flowchart In this note, we first point out that the flowchart proposed by Di Nola et al. is in error and give a correct flowchart. Then we give a numerical example, which is also a counterexample of the flowchart given by Di Nola el al., to explain our flowchart.     

Zeros of equivariant vector fields: Algorithms for an invariant approach

We present a symbolic algorithm to solve for the zeros of a polynomial vector field equivariant with respect to a finite subgroup of O (n). We prove that the module of equivariant. polynomial maps for a finite matrix group is Cohen-Macaulay and give an algorithm to compute a fundamental basis. Equivariant normal forms are easily computed from this basis. We use this basis to transform the problem of finding the zeros of an equivariant map to the problem of finding zeros of a set of invariant polynomials. Solving for the values of fundamental polynomial invariants at the zeros effectively reduces each group orbit of solutions to a single point. Our emphasis is on a computationally effective algorithm and we present our techniques applied to two examples.     

A practical algorithm to design fast and optimal band-Toeplitz preconditioners for hermitian toeplitz systems

In this paper we are concerned with the iterative solution ofn×n Hermitian Toeplitz systems by means of preconditioned conjugate gradient (PCG) methods. In many applications [9] such as signal processing [24], differential equations [39], linear prediction of stationary processes [18], the related Toeplitz systems have the formA _n (f)x=b where the symbolf, the generating function, is anL ¹ function and the entries ofA _n (f) along thek-th diagnonal coincide with thek-th Fourier coefficient off. When the essential range of the generating function has a convex hull containing zero, the matricesA _n (f) are asymptotically ill-conditioned [21, 33, 28] and circulant or Hartley preconditioners do not work [15]. For this difficult case the only optimal preconditioners in the sense of [3, 29] are found in the τ algebra [15, 35] and especially in the band Toeplitz matrix class [7, 16]. In particular the band Toeplitz preconditioning strategy has been shown to be the most flexible one since it allows one to treat the nonnegative case [7, 16, 11, 31], the nondefinite one [27, 30, 34, 26]. On the other hand, the main criticism to this approach is surely the assumption that we must know the position and the order of the zeros off: in some applicative fields this is a feasible assumption, in other applications it is merely a theoretical possibility. Therefore, we discuss an economical technique in order to discover the sign off, the position of the possible zeros of the generating function and to evaluate approximately the order of these zeros. Finally, we exhibit some numerical experiments which confirm the effectiveness of the proposed idea.     

A Faster FPT Algorithm for the Maximum Agreement Forest Problem

Given two unrooted, binary trees, T₁ and T₂, leaf labelled bijectively by a set of species L, the Maximum Agreement Forest (MAF) problem asks to find a minimum cardinality collection F = {t₁, ..., t_k} of phylogenetic trees where each element of F is a subtree of both T₁ and T₂, the elements of F are pairwise disjoint, and the leaf labels for the elements of F partition the leaf label set L. We give an efficient fixed-parameter tractable (FPT) algorithm for the MAF problem, significantly improving on an FPT algorithm given in [2]. Whereas the algorithm from [2] has a running time of O(k^3k) + p(|L|), our algorithm runs in time O(4^k · k⁵) + p(|L|), where k bounds the size of the agreement forest and p(·) is a low order polynomial.     

三元域上三次和四次剩余码的幂等生成元

有限域上高次剩余码的生成多项式都是多项式[xn-1]的因式。针对多项式[xn-1]在有限域上分解的困难性,给出了三元域[F3]上三次和四次剩余码的幂等生成元表达式。利用计算机软件求解这些幂等生成元与[xn-1]最大公因式就可得到三次和四次剩余码生成多项式而不用分解[xn-1]。     

二元域上三次和四次剩余码的幂等生成元

有限域上高次剩余码的生成多项式都是多项式[xn-1]的因式。针对多项式[xn-1]在有限域上分解的困难性,给出了二元域[F2]上三次和四次剩余码的幂等生成元表达式。利用计算机软件求解该幂等生成元与[xn-1]最大公因式就可得到三次和四次剩余码生成多项式而不用分解[xn-1]。     

On the approximation of the range of values by interval expressions

If the real-valued mappingf has a representation of the formf(x)=?₀+?(x)·h(x),x∈X where for the diameter ofh(X) the inequalityd(h(X))≤σd(X) holds and for the absolute value of ?(X) we have ??(X)?≤τd(X) ⁿ, then we introduce an interval expression forf which approximates the range of values off over the compact intervalX with ordern+1. Our result contains as a special case the theorem on higher order centered forms from [2] and a series of representations off not discussed before.