On factoring parametric multivariate polynomials

This paper presents a new algorithm for the absolute factorization of parametric multivariate polynomials over the field of rational numbers. This algorithm decomposes the parameters space into a finite number of constructible sets. The absolutely irreducible factors of the input parametric polynomial are given uniformly in each constructible set. The algorithm is based on a parametric version of Hensel's lemma and an algorithm for quantifier elimination in the theory of algebraically closed field in order to reduce the problem of finding absolute irreducible factors to that of representing solutions of zero-dimensional parametric polynomial systems. The complexity of this algorithm is single exponential in the number n of the variables of the input polynomial, its degree d w.r.t. these variables and the number r of the parameters.     

Tropical differential equations

Tropical differential equations are introduced and an algorithm is designed which tests solvability of a system of tropical linear differential equations within the complexity polynomial in the size of the system and in the absolute values of its coefficients. Moreover, we show that there exists a minimal solution, and the algorithm constructs it (in case of solvability). This extends a similar complexity bound established for tropical linear systems. In case of tropical linear differential systems in one variable a polynomial complexity algorithm for testing its solvability is designed.We prove also that the problem of solvability of a system of tropical non-linear differential equations in one variable is NP-hard, and this problem for arbitrary number of variables belongs to NP. Similar to tropical algebraic equations, a tropical differential equation expresses the (necessary) condition on the dominant term in the issue of solvability of a differential equation in power series.     

Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time

An algorithm of polynomial complexity is described for factoring polynomials in several variables into irreducible factors over a field F which is finitely generated over the prime subfield H. An algorithm is also constructed for finding the components of the protective variety of common roots of homogeneous polynomials (let c–1 denote its dimension) with working time polynomial in. where, the number L is the size of the representation of the polynomials and.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 137, pp. 124–188, 1984.     

Convex separable minimization with box constraints

A minimization problem with convex separable objective function subject to a convex separable inequality constraint of the form “less than or equal to” and bounds on the variables (box constraints) is considered. Necessary and sufficient condition is proved for a feasible solution to be an optimal solution to this problem. An iterative algorithm of polynomial complexity for solving problems of the considered form is suggested and its convergence is proved. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R ⁿ The complexity of the algorithm depends on the number of vertices of the projection of P onto the R ² space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form.

Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.     

A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems

This paper considers a general class of continuous, nonlinear, and nonseparable knapsack problems, special cases of which arise in numerous operations and financial contexts. We develop important properties of optimal solutions for this problem class, based on the properties of a closely related class of linear programs. Using these properties, we provide a solution method that runs in polynomial time in the number of decision variables, while also depending on the time required to solve a particular one-dimensional optimization problem. Thus, for the many applications in which this one-dimensional function is reasonably well behaved (e.g., unimodal), the resulting algorithm runs in polynomial time. We next develop a related solution approach to a class of continuous, nonlinear, and nonseparable multiple-choice knapsack problems. This algorithm runs in polynomial time in both the number of variables and the number of variants per item, while again dependent on the complexity of the same one-dimensional optimization problem as for the knapsack problem. Computational testing demonstrates the power of the proposed algorithms over a commercial global optimization software package.     

Condition number based complexity estimate for computing local extrema

In this paper, we present a new algorithm for computing local extrema by modifying and combining algorithms in symbolic and numerical computation. This new algorithm improves the classical steepest descent method that may not terminate, by combining a Sturm’s theorem based separation method and a sufficient condition on infeasibility. In addition, we incorporate a grid subdivision method into our algorithm to approximate all local extrema. The complexity of our algorithm is polynomial in a newly defined condition number, and singly exponential in the number of variables.     

棋盘游戏与有限域上多项式分解算法

将有限域F_2上多项式分解问题转化为一种对应的棋盘游戏,利用后者的性质设计了一个F_2上m+n-2次多项式f(x)分解为一个m-1次多项式与一个n-1次多项式的判断、分解算法,并对算法的复杂度进行了分析.算法的一个优势是,如果f(x)不能按要求分解,也可以找到一个与f(x)相近(这里指系数相异项较少)的多项式的分解.     

Generating Functions for Computing the Myerson Value

The complexity of a computational problem is the order of computational resources which are necessary and sufficient to solve the problem. The algorithm complexity is the cost of a particular algorithm. We say that a problem has polynomial complexity if its computational complexity is a polynomial in the measure of input size. We introduce polynomial time algorithms based in generating functions for computing the Myerson value in weighted voting games restricted by a tree. Moreover, we apply the new generating algorithm for computing the Myerson value in the Council of Ministers of the European Union restricted by a communication structure.     

Level structure of Zhegalkin polynomials,properties of test sets,and an annihilator search algorithm

Properties of the Boolean functions specified by the Zhegalkin polynomials in n variables of degree not greater than k are investigated from the viewpoint of placing their unit (zero) points on a unit cube. Properties of test sets for the Zhegalkin polynomials are considered, where the key role is played by the irredundant test sets. A deterministic algorithm for finding all the annihilators for a given polynomial is described including minimal-degree annihilators that have applications in cryptology. In the available algorithms for finding annihilators, the problem is reduced to solving systems of linear Boolean equations. Reducing the dimension of these systems decreases the algorithmic complexity of solving the problem. The proposed algorithm makes it possible to decrease the complexity of finding annihilators by reducing the dimension of such systems but it does not reduce the asymptotic complexity of solving systems of linear Boolean equations.     

The application of the Ehrlich-Aberth method to structured polynomial eigenvalue problems

An algorithm for the application of the Ehrlich-Aberth method to polynomial eigenvalue problems (PEPs) is proposed. The computational complexity of the algorithm is only quadratic with respect to the degree of the polynomial, where customary matrix methods have cubic complexity. For the case of some structured PEPs a strategy is given in order to exploit the structure and obtain the induced coupling in the spectrum. Numerical experiments are provided for the particular case of even/odd PEPs. This communication is based on joint work with Dario A. Bini and Luca Gemignani. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Algorithm of polynomial complexity for factoring polynomials over local fields

An algorithm is obtained for factoring polynomials in several variables over local fields with complexity which is polynomial in the length of notation of the input data and the characteristic of the residue field of the local field. Here by definition we assume that an infinite series can be calculated in polynomial time if its i-th partial sum can be calculated in time which is polynomial in the length of notation of the input data and i for any i.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 192, pp. 112–148, 1991.     

The Computational Complexity of the Chow Form

We present a bounded probability algorithm for the computation of the Chowforms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.     

The complexity of anl p method for discrete Tchebycheff approximation in exact arithmetic

A discrete Tchebycheff problem is approximated by a sequence ofl _p norm problems. This is an algorithm to be used if a large number of variables is involved as is the case in the approximation of a function of several variables by a polynomial. The complexity of this procedure is investigated and a lower bound for the number of steps to reach ε-optimality is established. Supported by NIH Grant RR01243 at the University of Washington     

框式线性规划的多项式预估校正内点算法

本文研究带线性约束的框式线性规划问题,给出了一个预估校正内点算法,分析了该算法的多项式计算复杂性,并证明其迭代复杂度为Ο(nL).     

Unconstrained and constrained global optimization of polynomial functions in one variable

In Floudas and Visweswaran (1990), a new global optimization algorithm (GOP) was proposed for solving constrained nonconvex problems involving quadratic and polynomial functions in the objective function and/or constraints. In this paper, the application of this algorithm to the special case of polynomial functions of one variable is discussed. The special nature of polynomial functions enables considerable simplification of the GOP algorithm. The primal problem is shown to reduce to a simple function evaluation, while the relaxed dual problem is equivalent to the simultaneous solution of two linear equations in two variables. In addition, the one-to-one correspondence between the x and y variables in the problem enables the iterative improvement of the bounds used in the relaxed dual problem. The simplified approach is illustrated through a simple example that shows the significant improvement in the underestimating function obtained from the application of the modified algorithm. The application of the algorithm to several unconstrained and constrained polynomial function problems is demonstrated.     

P*(κ)线性互补问题的一个大步校正内点算法的迭代复杂性

本文基于一个带参数的函数,为P*(κ)线性互补问题设计出了一个大步校正内点算法.算法讨论沿用了Peng等在文[9]对互补问题基于自正则函数的讨论模式.但是,与Peng的算法不同的是,我们所考虑的带参数的函数是非自正则的.算法最终被证明具有较好的多项式复杂性.     

A quadratically convergent polynomial long-step algorithm for A class of nonlinear monotone complementarity problems *

Several interior point algorithms have been proposed for solving nonlinear monotone complementarity problems. Some of them have polynomial worst-case complexity but have to confine to short steps, whereas some of the others can take long steps but no polynomial complexity is proven. This paper presents an algorithm which is both long-step and polynomial. In addition, the sequence generated by the algorithm, as well as the corresponding complementarity gap, converges quadratically. The proof of the polynomial complexity requires that the monotone mapping satisfies a scaled Lipschitz condition, while the quadratic rate of convergence is derived under the assumptions that the problem has a strictly complementary solution and that the Jacobian of the mapping satisfies certain regularity conditions     

Complexity of solving parametric polynomial systems

In this paper, we present three algorithms: the first one solves zero-dimensional parametric homogeneous polynomial systems within single exponential time in the number n of unknowns; it decomposes the parameter space into a finite number of constructible sets and computes the finite number of solutions by parametric rational representations uniformly in each constructible set. The second algorithm factirizes absolutely multivariate parametic polynomials within single exponential time in n and in the upper bound d on the degree of the factorized polynomials. The third algorithm decomposes algebraic varieties defined by parametric polynomial systems of positive dimension into absolutely irreducible components uniformly in the values of the parameters. The complexity bound for this algorithm is double exponential in n. On the other hand, the lower bound on the complexity of the problem of resolution of parametric polynomial systems is double exponential in n. Bibliography: 72 titles.     

A discrete logarithm-based approach to compute low-weight multiples of binary polynomials

Being able to compute efficiently a low-weight multiple of a given binary polynomial is often a key ingredient of correlation attacks to LFSR-based stream ciphers. The best known general purpose algorithm is based on the generalized birthday problem. We describe an alternative approach which is based on discrete logarithms and can take advantage of the structure of the polynomial. In some cases it has much lower memory complexity requirements with a comparable time complexity.