THE SPECTRALITY DECISION PROBLEM

An effcient algorithm for deciding whether a given integer vector is thespectrum of some Boolean function is presented.The algorithm performs astep-by-step spectral decomposition of the input vector and checks at eachstep a set of necessary conditions for spectrality for the resulting vectors.The algorithm concludes that the input vector cannot lead to a valid Booleanfunction as soon as a vector not satisfying the conditions is found,which,as proved in the paper,for almost all cases happens after the first step ofthe decomposition.     

A Unified Rounding Error Bound for Polynomial Evaluation

We present a unified rounding error bound for polynomial evaluation. The bound presented here takes the same general form for the evaluation of a polynomial written in any polynomial basis when the evaluation algorithm can be expressed as a linear recurrence or a first-order linear matrix recurrence relation. Examples of these situations are: Horner's algorithm in the evaluation of power series, Clenshaw's and Forsythe's algorithms in the evaluation of orthogonal polynomial series, de-Casteljau's algorithm for Bernstein polynomial series, the modification of Clenshaw's algorithms in the evaluation of Szeg polynomial series, and so on.     

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.     

The construction of extensible polynomial lattice rules with small weighted star discrepancy

In this paper we introduce a construction algorithm for extensible polynomial lattice rules and we prove that the construction algorithm yields generating vectors of polynomials which are optimal for a range of moduli chosen in advance. The construction algorithm uses a sieve where the generating vectors are extended by one coefficient in each component at each step and where one keeps a certain number of good ones and discards the rest. We also show that the construction can be done component by component.

     

An Adaptive Algorithm for Vector Partitioning

The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.     

Independence and port oracles for matroids,with an application to computational learning theory

Given a matroidM with distinguished elemente, aport oracie with respect toe reports whether or not a given subset contains a circuit that containse. The first main result of this paper is an algorithm for computing ane-based ear decomposition (that is, an ear decomposition every circuit of which contains elemente) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case thatM is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation forM. Thus, this algorithm solves a problem in computational learning theory; it learns the class ofbinary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroidM. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.Research partially funded by NSF PYI Grant No. DDM-91-96083.Research partially funded by NSF Grant No CCR-92-10957.     

AN ADAPTIVE VARIANT OF CGNR ALGORITHM

1　IntroductionConsider large linear systemAx =b, ( 1 .1 )where A and b are given,A isa nonsingularn×n real matrix,and b is an n-vector.When A issymmetric positive definite ( s.p.d.) ,the classical conjugate gradient method ( CG) [7] used inconjunction with incomplete factorization preconditioning technique[1 0 ] is a succesful method inview of the high robustness and efficiency.But for general non-s.p.d.systems,the situationis less satisfactory.The generalized minimal residual algorithm( …     

Representations of orthogonal polynomials

Zeilberger's algorithm provides a method to compute recurrence and differential equations from given hypergeometric series representations, and an adaption of Almquist and Zeilberger computers recurrence and differential equations for hyperexponential integrals. Further versions of this algorithm allow the computation of recurrence and differential equations from Rodrigues type formulas and from generating functions. In particular, these algorithms can be used to compute the differential/difference and recurrence equations for the classical continuous and discrete orthogonal polynomials from their hypergeometric representations, and from their Rodrigues representations and generating functions.In recent work, we used an explicit formula for the recurrence equation of families of classical continuous and discrete orthogonal polynomials, in terms of the coefficients of their differential/difference equations, to give an algorithm to identify the polynomial system from a given recurrence equation.In this article we extend these results by presenting a collection of algorithms with which any of the conversions between the differential/difference equation, the hypergeometric representation, and the recurrence equation is possible.The main technique is again to use explicit formulas for structural identities of the given polynomial systems.     

有理插值的一种递推算法

针对给定的数据型值点,利用多项式带余除法,给出有理函数插值的一种新型递推算法,可以求出满足插值条件的所有有理插值函数,并举例说明其有效性.     

Polar Varieties,Real Equation Solving,and Data Structures: The Hypersurface Case

In this paper we apply for the first time a new method for multivariate equation solving which was developed for complex root determination to therealcase. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem-adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit). The algorithm finds the complex solutions of any affine zero-dimensional equation system in nonuniform sequential time that ispolynomialin the length of the input (given in straight-line program representation) and an adequately definedgeometric degree of the equation system.Replacing the notion of geometric degree of the given polynomial equation system by a suitably definedreal (or complex) degreeof certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above.     

An Adaptive CGNR Algorithm for Solving Large Linear Systems

In this paper, an adaptive algorithm based on the normal equations for solving large nonsymmetric linear systems is presented. The new algorithm is a hybrid method combining polynomial preconditioning with the CGNR method. Residual polynomial is used in the preconditioning to estimate the eigenvalues of the s.p.d. matrix A ^T A, and the residual polynomial is generated from several steps of CGNR by recurrence. The algorithm is adaptive during its implementation. The robustness is maintained, and the iteration convergence is speeded up. A numerical test result is also reported.     

Direct and inverse polynomial perturbations of hermitian linear functionals

This paper is devoted to the study of direct and inverse (Laurent) polynomial modifications of moment functionals on the unit circle, i.e., associated with hermitian Toeplitz matrices. We present a new approach which allows us to study polynomial modifications of arbitrary degree.The main objective is the characterization of the quasi-definiteness of the functionals involved in the problem in terms of a difference equation relating the corresponding Schur parameters. The results are presented in the general framework of (non-necessarily quasi-definite) hermitian functionals, so that the maximum number of orthogonal polynomials is characterized by the number of consistent steps of an algorithm based on the referred recurrence for the Schur parameters.The non-uniqueness of the inverse problem makes it more interesting than the direct one. Due to this reason, special attention is paid to the inverse modification, showing that different approaches are possible depending on the data about the polynomial modification at hand. These different approaches are translated as different kinds of initial conditions for the related inverse algorithm.Some concrete applications to the study of orthogonal polynomials on the unit circle show the effectiveness of this new approach: an exhaustive and instructive analysis of the functionals coming from a general inverse polynomial perturbation of degree one for the Lebesgue measure; the classification of those pairs of orthogonal polynomials connected by a certain type of linear relation with constant polynomial coefficients; and the determination of those orthogonal polynomials whose associated ones are related to a degree one polynomial modification of the original orthogonality functional.     

Computing lower bounds on basket option prices by discretizing semi-infinite linear programming

The problem of finding static-arbitrage bounds on basket option prices has received a growing attention in the literature. In this paper, we focus on the lower bound case and propose a novel efficient solution procedure that is based on the separation problem. The computational burden of the proposed method is polynomial in the input data size. We also discuss the case of possibly negative weight vectors which can be applied to spread options.     

An approximating polynomial algorithm for a sequence partitioning problem

We consider a strongly NP-hard problem of partitioning a finite sequence of vectors in Euclidean space into two clusters using the criterion of minimum sum-of-squares of distances from the elements of clusters to their centers. We assume that the cardinalities of the clusters are fixed. The center of one cluster has to be optimized and is defined as the average value over all vectors in this cluster. The center of the other cluster lies at the origin. The partition satisfies the condition: the difference of the indices of the next and previous vectors in the first cluster is bounded above and below by two given constants. We propose a 2-approximation polynomial algorithm to solve this problem.     

Exponential irreducible neighborhoods for combinatorial optimization problems

This paper deals with irreducible augmentation vectors associated with three combinatorial optimization problems: the TSP, the ATSP, and the SOP. We study families of irreducible vectors of exponential size, derived from alternating cycles, where optimizing a linear function over each of these families can be done in polynomial time. A family of irreducible vectors induces an irreducible neighborhood; an algorithm for optimizing over this family is known as a local search heuristic. Irreducible neighborhoods do not only serve as a tool to improve feasible solutions, but do play an important role in an exact primal algorithm; such families are the primal counterpart of a families of facet inducing inequalities.     

A simple randomised algorithm for convex optimisation

We consider maximising a concave function over a convex set by a simple randomised algorithm. The strength of the algorithm is that it requires only approximate function evaluations for the concave function and a weak membership oracle for the convex set. Under smoothness conditions on the function and the feasible set, we show that our algorithm computes a near-optimal point in a number of operations which is bounded by a polynomial function of all relevant input parameters and the reciprocal of the desired precision, with high probability. As an application to which the features of our algorithm are particularly useful we study two-stage stochastic programming problems. These problems have the property that evaluation of the objective function is #P-hard under appropriate assumptions on the models. Therefore, as a tool within our randomised algorithm, we devise a fully polynomial randomised approximation scheme for these function evaluations, under appropriate assumptions on the models. Moreover, we deal with smoothing the feasible set, which in two-stage stochastic programming is a polyhedron.     

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.     

Analysis of the symmetric Lanczos algorithm with reorthogonalization methods

We present an error analysis of the symmetric Lanczos algorithm in finite precision arithmetic. The loss of orthogonality among the computed Lanczos vectors is explained with the help of a recurrence formula. A backward error analysis shows that semiorthogonality among the Lanczos vectors is enough to guarantee the accuracy of the computed quantities up to machine precision. The results of this analysis are then extended to the more general case of the Lanczos algorithm with a semiorthogonalization strategy. Based on the recurrence formula, a new reorthogonalization method called partial reorthogonalization is introduced. We show that both partial reorthogonalization and selective orthogonalization as introduced by Parlett and Scott [15] are semiorthogonalization strategies. Finally we discuss the application of our results to the solution of linear systems of equations and to the eigenvalue problem.     

A Method of computing a fundamental row of solutions and jordan chains for a singular linear pencil of matrices

An algorithm is suggested for constructing a fundamental row of polynomial solutions for a singular linear pencil of matrices. The algorithm is a modification of the algorithm for constructing polynomial solutions of a pencil that was suggested earlier by the author. For a computed eigenvalue of the regular kernel of the singular pencil, corresponding chains of Jordan vectors are found. In the process, essential use is made of the subspace generated by a fundamental row of polynomial solutions for the eigenvalue under consideration.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 124, pp. 101–113, 1983.