Computing Frobenius maps and factoring polynomials

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented. To factor a polynomial of degreen overF _q , the number of arithmetic operations inF _q isO((n ²+nlogq). (logn)² loglogn). The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.     

Fq上具有极大1-error线性复杂度的周期序列

线性复杂度是衡量序列密码学强度的重要指标,设计具有大的线性复杂度和k-error线性复杂度的序列是密码学和通信中的热点问题.Niederreiter首次发现了F_q上许多满足这个要求的周期序列.通过序列的广义离散傅立叶变换构造了一些F_q上具有极大1-error线性复杂度的周期序列,这些结果远远优于已知的结果.     

Exact Computation of Polynomial Zeros Expressible by Square Roots

In this paper we give an efficient algorithm to find symbolically correct zeros of a polynomial f ∈ R[X] which can be represented by square roots. R can be any domain if a factorization algorithm over R[X] is given, including finite rings or fields, integers, rational numbers, and finite algebraic or transcendental extensions of those. Asymptotically, the algorithm needs O(T_f(d²)) operations in R, where T_f(d) are the operations for the factorization algorithm over R[X] for a polynomial of degree d. Thus, the algorithm has polynomial running time for instance for polynomials over finite fields or the rationals. We also present a quick test for deciding whether a given polynomial has zeros expressible by square roots and describe some additional methods for special cases.     

A deterministic test for permutation polynomials

A new deterministic algorithm is presented for testing whether a given polynomial of degreen over a finite field ofq elements is a permutation polynomial. The algorithm has computing time (nq)^6/7+, and gives a positive answer to a question of Lidl and Mullen.     

Efficient decomposition of separable algebras

We present new, efficient algorithms for computations on separable matrix algebras over infinite fields. We provide a probabilistic method of the Monte Carlo type to find a generator for the center of a given algebra $\text{A}\text{⊆}\text{F}{}^{\mathrm{m\times m}}$ over an infinite field $\text{F}$. The number of operations used is within a logarithmic factor of the cost of solving m×m systems of linear equations. A Las Vegas algorithm is also provided under the assumption that a basis and set of generators for the given algebra are available. These new techniques yield a partial factorization of the minimal polynomial of the generator that is computed, which may reduce the cost of computing simple components of the algebra in some cases.     

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.     

Parallel solution of sparse linear least squares problems on distributed-memory multiprocessors

This paper studies the parallel solution of large-scale sparse linear least squares problems on distributed-memory multiprocessors. The key components required for solving a sparse linear least squares problem are sparse QR factorization and sparse triangular solution. A block-oriented parallel algorithm for sparse QR factorization has already been described in the literature. In this paper, new block-oriented parallel algorithms for sparse triangular solution are proposed. The arithmetic and communication complexities of the new algorithms applied to regular grid problems are analyzed. The proposed parallel sparse triangular solution algorithms together with the block-oriented parallel sparse QR factorization algorithm result in a highly efficient approach to the parallel solution of sparse linear least squares problems. Performance results obtained on an IBM Scalable POWERparallel system SP2 are presented. The largest least squares problem solved has over two million rows and more than a quarter million columns. The execution speed for the numerical factorization of this problem achieves over 3.7 gigaflops per second on an IBM SP2 machine with 128 processors.     

New Results on Noncommutative and Commutative Polynomial Identity Testing

Using ideas from automata theory, we design the first polynomial deterministic identity testing algorithm for the sparse noncommutative polynomial identity testing problem. Given a noncommuting black-box polynomial f ? \mathbb F{x₁,?,x_n}f \in {\mathbb F}\{x_{1},\ldots,x_n\} of degree d with at most t monomials, where the variables x_i are noncommuting, we give a deterministic polynomial identity test that checks if C o 0C \equiv 0 and runs in time polynomial in d, n, |C|, and t. Our algorithm evaluates the black-box polynomial for x_i assigned to matrices over \mathbbF{\mathbb{F}} and, in fact, reconstructs the entire polynomial f in time polynomial in n, d and t.     

A fast algorithm for solving special tridiagonal systems

In this paper, a fast algorithm for solving the special tridiagonal system is presented. This special tridiagonal system is a symmetric diagonally dominant and Toeplitz system of linear equations. The error analysis is also given. Our algorithm is quite competitive with the Gaussian elimination, cyclic reduction, specialLU factorization, reversed triangular factorization, and Toeplitz factorization methods. In addition, our result can be applied to solve the near-Toeplitz tridiagonal system. Some examples demonstrate the good efficiency and stability of our algorithm.     

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.     

Polynomial solutions to H∞ problems

The paper presents a polynomial solution to the standard H_∞-optimal control problem. Based on two polynomial J-spectral factorization problems, a parameterization of all suboptimal compensators is obtained. A bound on the McMillan degree of suboptimal compensators is derived and an algorithm is formulated that may be used to solve polynomial J-spectral factorization problems.     

Efficient and optimal exponentiation in finite fields

Optimal sequential and parallel algorithms for exponentiation in a finite field containing F _q are presented, assuming thatqth powers can be computed for free.     

F [ x ]-lattice basis reduction algorithm and multisequence synthesis

By means ofF[x]-lattice basis reduction algorithm, a new algorithm is presented for synthesizing minimum length linear feedback shift registers (or minimal polynomials) for the given multiple sequences over a fieldF. Its computational complexity isO(N ²) operations inF whereN is the length of each sequence. A necessary and sufficient condition for the uniqueness of minimal polynomials is given. The set and exact number of all minimal polynomials are also described whenF is a finite field.     

Factorization of Polynomials over Finite Fields and Characteristic Sequences

A new factorization algorithm for polynomials over finite fields was recently developed by the first author. For finite fields of characteristic 2, it is known from previous work that this algorithm has several advantages over the classical Berlekamp algorithm. In this paper we show that the linearization step in the new algorithm is feasible—in the sense that it can be carried out in polynomial time—for arbitrary finite fields, by using an approach based on decimation operators and characteristic linear recurring sequences. We also introduce a general principle for the linearization of the factorization problem for polynomials over finite fields.     

Highly scalable parallel algorithms for sparse matrix factorization

In this paper, we describe scalable parallel algorithms for symmetric sparse matrix factorization, analyze their performance and scalability, and present experimental results for up to 1,024 processors on a Gray T3D parallel computer. Through our analysis and experimental results, we demonstrate that our algorithms substantially improve the state of the art in parallel direct solution of sparse linear systems-both in terms of scalability and overall performance. It is a well known fact that dense matrix factorization scales well and can be implemented efficiently on parallel computers. In this paper, we present the first algorithms to factor a wide class of sparse matrices (including those arising from two- and three-dimensional finite element problems) that are asymptotically as scalable as dense matrix factorization algorithms on a variety of parallel architectures. Our algorithms incur less communication overhead and are more scalable than any previously known parallel formulation of sparse matrix factorization. Although, in this paper, we discuss Cholesky factorization of symmetric positive definite matrices, the algorithms can be adapted for solving sparse linear least squares problems and for Gaussian elimination of diagonally dominant matrices that are almost symmetric in structure. An implementation of one of our sparse Cholesky factorization algorithms delivers up to 20 GFlops on a Gray T3D for medium-size structural engineering and linear programming problems. To the best of our knowledge, this is the highest performance ever obtained for sparse Cholesky factorization on any supercomputer     

Discrete logarithms inGF(p)

Several related algorithms are presented for computing logarithms in fieldsGF(p),p a prime. Heuristic arguments predict a running time of exp((1+o(1)) ) for the initial precomputation phase that is needed for eachp, and much shorter running times for computing individual logarithms once the precomputation is done. The running time of the precomputation is roughly the same as that of the fastest known algorithms for factoring integers of size aboutp. The algorithms use the well known basic scheme of obtaining linear equations for logarithms of small primes and then solving them to obtain a database to be used for the computation of individual logarithms. The novel ingredients are new ways of obtaining linear equations and new methods of solving these linear equations by adaptations of sparse matrix methods from numerical analysis to the case of finite rings. While some of the new logarithm algorithms are adaptations of known integer factorization algorithms, others are new and can be adapted to yield integer factorization algorithms.     

New Algorithms for Polynomial J-Spectral Factorization

In this paper new algorithms are developed for J-spectral factorization of polynomial matrices. These algorithms are based on the calculus of two-variable polynomial matrices and associated quadratic differential forms, and share the common feature that the problem is lifted from the original one-variable polynomial context to a two-variable polynomial context. The problem of polynomial J-spectral factorization is thus reduced to a problem of factoring a constant matrix obtained from the coefficient matrices of the polynomial matrix to be factored. In the second part of the paper, we specifically address the problem of computing polynomial J-spectral factors in the context of H _∞ control. For this, we propose an algorithm that uses the notion of a Pick matrix associated with a given two-variable polynomial matrix. Date received: January 1, 1998. Date revised: October 15, 1998.     

On sparse lu factorization procedures for the solution of parabolic differential equations in three space dimensions

The numerical solution of partial differential equations in 3 dimensions by finite difference methods leads to the problem of solving large order sparse structured linear systems.

In this paper, a factorization procedure in algorithmic form is derived yielding direct and iterative methods of solution of some interesting boundary value problems in physics and engineering.     

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.