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 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.     

Improved dense multivariate polynomial factorization algorithms

We present new deterministic and probabilistic algorithms that reduce the factorization of dense polynomials from several variables to one variable. The deterministic algorithm runs in sub-quadratic time in the dense size of the input polynomial, and the probabilistic algorithm is softly optimal when the number of variables is at least three. We also investigate the reduction from several to two variables and improve the quantitative version of Bertini’s irreducibility theorem.     

Optimal and nearly optimal algorithms for approximating polynomial zeros

We substantially improve the known algorithms for approximating all the complex zeros of an n^th degree polynomial p(x). Our new algorithms save both Boolean and arithmetic sequential time, versus the previous best algorithms of Schönhage [1], Pan [2], and Neff and Reif [3]. In parallel (NC) implementation, we dramatically decrease the number of processors, versus the parallel algorithm of Neff [4], which was the only NC algorithm known for this problem so far. Specifically, under the simple normalization assumption that the variable x has been scaled so as to confine the zeros of p(x) to the unit disc x : |x| ≤ 1, our algorithms (which promise to be practically effective) approximate all the zeros of p(x) within the absolute error bound 2^−b, by using order of n arithmetic operations and order of (b + n)n² Boolean (bitwise) operations (in both cases up to within polylogarithmic factors). The algorithms allow their optimal (work preserving) NC parallelization, so that they can be implemented by using polylogarithmic time and the orders of n arithmetic processors or (b + n)n² Boolean processors. All the cited bounds on the computational complexity are within polylogarithmic factors from the optimum (in terms of n and b) under both arithmetic and Boolean models of computation (in the Boolean case, under the additional (realistic) assumption that n = O(b)).     

The algebraic Riccati equation — A polynomial approach

Polynomial models are used to give a unified approach to the problem of classifying the set of all real symmetric solutions of the algebraic Riccati equation.     

一个53位数的分解

本文描述一个在序列密码设计中有重要意义的５３位数Ｎ＝的素因子分解。按Ｐｏｍｅｒａｎｃｅ－Ｍｏｎｔｇｏｍｅｒｙ多个多项式二次筛算法编写的Ｐａｓｃａｌ程序在一台ＰＣ３８６微机上把Ｎ分解成三个素数之积。此Ｐａｓｃａｌ程序在一台３８６／４８６微机上分解一个６０位数大约需一天左右的时间。     

Number-theoretic functions which are equivalent to number of divisors

Let d(n) denote the number of positive integral divisors of n. In this paper we show that the Möbius function, μ(N), can be computed by a single call to an oracle for d(n). We also show that any function that depends solely on the exponents in the prime factorization of N can be computed by at most log₂ N calls to an oracle for d(N).     

A statistical approach for economization of the polynomial functions

Due to having the minimax property, Chebyshev polynomials are used today to economize the arbitrary polynomial functions. In this work, we present a statistical approach to show that, contrary to current thought, the Chebyshev polynomials of the first kind are not appropriate for economizing these polynomials if one uses this statistical approach. In this way, a numerical results section is also given to clearly prove our claim.     

A new proximity test for polynomial zeros

We combine some known techniques and results of Turan and Schönhage to improve substantially numerical performance of the computation of the minimum and the maximum distances from a fixed complex point to roots (zeros) of a fixed univariate polynomial.     

Algorithms for near solutions to polynomial equations

Let F(x,y)$F(x,y)$ be a polynomial over a field K$K$ and m$m$ a nonnegative integer. We call a polynomial g$g$ over K$K$ an m$m$-near solution of F(x,y)$F(x,y)$ if there exists a c∈K$c\in K$ such that F(x,g)=cx^m$F(x,g)=c{x}^m$, and the number c$c$ is called an m$m$-value of F(x,y)$F(x,y)$ corresponding to g$g$. In particular, c$c$ can be 0. Hence, by viewing F(x,y)=0$F(x,y)=0$ as a polynomial equation over K[x]$K\left[x\right]$ with variable y$y$, every solution of the equation F(x,y)=0$F(x,y)=0$ in K[x]$K\left[x\right]$ is also an m$m$-near solution. We provide an algorithm that gives all m$m$-near solutions of a given polynomial F(x,y)$F(x,y)$ over K$K$, and this algorithm is polynomial time reducible to solving one variable equations over K$K$. We introduce approximate solutions to analyze the algorithm. We also give some interesting properties of approximate solutions.     

A polynomial newton method for linear programming

An algorithm is presented for solving a set of linear equations on the nonnegative orthant. This problem can be made equivalent to the maximization of a simple concave function subject to a similar set of linear equations and bounds on the variables. A Newton method can then be used which enforces a uniform lower bound which increases geometrically with the number of iterations. The basic steps are a projection operation and a simple line search. It is shown that this procedure either proves in at mostO(n ² m ² L) operations that there is no solution or, else, computes an exact solution in at mostO(n ³ m ² L) operations.The linear programming problem is treated as a parametrized feasibility problem and solved in at mostO(n ³ m ² L) operations.     

Solvability of systems of polynomial congruences modulo a large prime

We consider the following polynomial congruences problem: given a prime p, and a set of polynomials of total degree at most d, solve the system for solution(s) in . We give a randomized algorithm for the decision version of this problem. For a fixed number of variables, the sequential version of the algorithm has expected time complexity polynomial in d, m and log p; the parallel version has expected time complexity polylogarithmic in d, m and p, using a number of processors, polynomial in d, m and log p. The only point which prevents the algorithm from being deterministic is the lack of a deterministic polynomial time algorithm for factoring univariate polynomials over . Received: April 9, 1997.     

一种解稳定性问题的迭代法

本文提出一种确定特征多项式的全部根是否位于左半平面的迭代法,方法简单,敛速高。     

A polynomial factorization approach to the discrete time GI/G/1/(N) queue size distribution

The queue of a single server is considered with independent and identically distributed interarrivai and service times and an infinite (GI/G/1) or finite (GI/G/1/N) waiting room. The queue discipline is non-preemptive and independent of the service times.

A discrete time version of the system is analyzed, using a two-component state model at the arrival and departure instants of customers. The equilibrium equations are solved by a polynomial factorization method. The steady state distribution of the queue size is then represented as a linear combination of geometrical series, whose parameters are evaluated by closed formulae depending on the roots of a characteristic polynomial.

Considering modified boundary constraints, systems with finite waiting room or with an exceptional first service in each busy period are included.     

Non-linear variable selection for artificial neural networks using partial mutual information

Artificial neural networks (ANNs) have been widely used to model environmental processes. The ability of ANN models to accurately represent the complex, non-linear behaviour of relatively poorly understood processes makes them highly suited to this task. However, the selection of an appropriate set of input variables during ANN development is important for obtaining high-quality models. This can be a difficult task when considering that many input variable selection (IVS) techniques fail to perform adequately due to an underlying assumption of linearity, or due to redundancy within the available data.This paper focuses on a recently proposed IVS algorithm, based on estimation of partial mutual information (PMI), which can overcome both of these issues and is considered highly suited to the development of ANN models. In particular, this paper addresses the computational efficiency and accuracy of the algorithm via the formulation and evaluation of alternative techniques for determining the significance of PMI values estimated during selection. Furthermore, this paper presents a rigorous assessment of the PMI-based algorithm and clearly demonstrates the superior performance of this non-linear IVS technique in comparison to linear correlation-based techniques.     

Optimal reserve site selection with distance requirements

The reserve set covering problem minimizes the total cost or area of sites needed to represent all species within a system of nature reserves, but does not address spatial characteristics such as distances between reserve sites. Inter-site distance, as a surrogate for connectivity, is likely to affect species persistence and other functional aspects of reserve systems. Two new 0-1 programming models that build upon the reserve set covering problem are formulated for controlling inter-site distance. Depending on the circumstances, longer or shorter inter-site distances may be desirable, and arguments for each case are discussed. The first model requires reserves to be at least a minimum separation distance apart. The second model requires at least two representations of each species and also requires the sites that represent a species to be no farther apart than a stated proximity distance. These models are applied to four demonstration problems in which both synthetic and real presence/absence data are used. Results and computational experience are discussed. The first model achieves site dispersal while the second model achieves site connectivity to the extent that each is compatible with set covering.     

An explicit solution to polynomial matrix right coprime factorization with application in eigenstructure assignment

In this paper, an explicit solution to polynomial matrix right coprime factorization of input-state transfer function is obtained in terms of the Krylov matrix and the Pseudo-controllability indices of the pair of coefficient matrices. The proposed approach only needs to solve a series of linear equations. Applications of this solution to a type of generalized Sylvester matrix equations and the problem of parametric eigenstructure assignment by state feedback are investigated. These new solutions are simple, they possess better structural properties and are very convenient to use. An example shows the effect of the proposed results.     

On the pseudoachromatic number of join of graphs

Given an undirected graph G = (V, E), with vertex set V and edge set E, the pseudoachromatic number ψ(G) of the graph G is the maximum number of colors used to color the vertices in such a way that, for any given pair of colors i, j there exists an edge e = (u, v) ∈ E(G) such that u is colored i and v is colored j. In this paper we give a complete characterization of when the ψ of the join of any two graphs is the sum of the ψ of the two graphs.