布尔函数和伪布尔函数多项式表示的快速实现算法

布尔函数和伪布尔函数在不同的领域有着广泛的应用,利用多项式表示有利于刻划它们的一些特征属性。论文首先在已知输入都能得到输出的条件下给出了布尔函数多项式表示的快速实现算法,该算法仅用到模2加运算,运算次数少,具有简洁、易于编程实现、准确而快速的特点,而且该算法很易推广为伪布尔函数多项式表示的快速实现算法,只需把模2加运算换成实数加运算即可。接着通过比较说明了伪布尔函数多项式表示的快速实现算法,同时指出任何伪布尔函数都能通过多项式形式表示出来。最后通过实例进一步验证了算法的正确性。     

Root isolation of zero-dimensional polynomial systems with linear univariate representation

In this paper, a linear univariate representation for the roots of a zero-dimensional polynomial equation system is presented, where the complex roots of the polynomial system are represented as linear combinations of the roots of several univariate polynomial equations. An algorithm is proposed to compute such a representation for a given zero-dimensional polynomial equation system based on Gröbner basis computation. The main advantage of this representation is that the precision of the roots of the system can be easily controlled. In fact, based on the linear univariate representation, we can give the exact precisions needed for isolating the roots of the univariate equations in order to obtain roots of the polynomial system with a given precision. As a consequence, a root isolating algorithm for a zero-dimensional polynomial equation system can be easily derived from its linear univariate representation.     

Solving systems of polynomial equations

Geometric and solid modelling deal with the representation and manipulation of physical objects. Currently most geometric objects are formulated in terms of polynomial equations, thereby reducing many application problems to manipulating polynomial systems. Solving systems of polynomial equations is a fundamental problem in these geometric computations. The author presents an algorithm for solving polynomial equations. The combination of multipolynomial resultants and matrix computations underlies this efficient, robust and accurate algorithm     

Declarative Representation of Algorithms of Completion by Critical Pairs

A declarative representation of critical pairs for completion algorithms is described. The representation can be considered as a generic program that, after parametrization of some of its functions, realizes the Knuth-Bendix algorithm for solving the word problem in universal algebras or Buchberger algorithm for constructing Grobner bases of polynomial ideals. The properties of termination and correction are considered. A realization of the representation in the APS algebraic system is described.     

Polynomial Factorization of Spectral Bases

Polynomial factorization of spectral bases is studied, expressing polynomial factorization as the representation of a system of spectral functions defined by an integral discrete transformation matrix in the form of the Kronecker product of matrices of reduced dimension. Such a representation is helpful in expressing an ordered system of functions by a unified formula in a base of binary operations. An algorithm for polynomial factorization of matrices, its theoretical principles, and results of an experiment are presented.     

A symbolic matrix decomposition algorithm for reduced order linear fractional transformation modelling

In this paper an algorithm that provides an equivalent, but of reduced order, representation for multivariate polynomial matrices is given. It combines ideas from computational symbolic algebra, polynomial/matrix algebraic manipulations and information logic. The algorithm is applied to the problem of finding minimal linear fractional transformation models. Statistical performance analysis of the algorithm reveals that it consistently outperforms currently available algorithms.     

Solving nonlinear polynomial systems in the barycentric Bernstein basis

We present a method for solving arbitrary systems of N nonlinear polynomials in n variables over an n-dimensional simplicial domain based on polynomial representation in the barycentric Bernstein basis and subdivision. The roots are approximated to arbitrary precision by iteratively constructing a series of smaller bounding simplices. We use geometric subdivision to isolate multiple roots within a simplex. An algorithm implementing this method in rounded interval arithmetic is described and analyzed. We find that when the total order of polynomials is close to the maximum order of each variable, an iteration of this solver algorithm is asymptotically more efficient than the corresponding step in a similar algorithm which relies on polynomial representation in the tensor product Bernstein basis. We also discuss various implementation issues and identify topics for further study.     

Extracting rules from trained neural networks

Presents an algorithm for extracting rules from trained neural networks. The algorithm is a decompositional approach which can be applied to any neural network whose output function is monotone such as a sigmoid function. Therefore, the algorithm can be applied to multilayer neural networks, recurrent neural networks and so on. It does not depend on training algorithms, and its computational complexity is polynomial. The basic idea is that the units of neural networks are approximated by Boolean functions. But the computational complexity of the approximation is exponential, and so a polynomial algorithm is presented. The author has applied the algorithm to several problems to extract understandable and accurate rules. The paper shows the results for the votes data, mushroom data, and others. The algorithm is extended to the continuous domain, where extracted rules are continuous Boolean functions. Roughly speaking, the representation by continuous Boolean functions means the representation using conjunction, disjunction, direct proportion, and reverse proportion. This paper shows the results for iris data.     

Learning Read-Constant Polynomials of Constant Degree Modulo Composites

Boolean functions that have constant degree polynomial representation over a fixed finite ring form a natural and strict subclass of the complexity class ACC⁰. They are also precisely the functions computable efficiently by programs over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model. In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by polynomials of constant degree over arbitrary finite rings from membership queries, with the additional constraint that each variable in the target polynomial appears in a constant number of monomials. Our algorithm extends to superconstant but low degree polynomials and still runs in quasipolynomial time.     

Recognition is not parsing — SPPF-style parsing from cubic recognisers

In their recogniser forms, the Earley and RIGLR algorithms for testing whether a string can be derived from a grammar are worst-case cubic on general context free grammars (CFG). Earley gave an outline of a method for turning his recognisers into parsers, but it turns out that this method is incorrect. Tomita’s GLR parser returns a shared packed parse forest (SPPF) representation of all derivations of a given string from a given CFG but is worst-case unbounded polynomial order. The parser version of the RIGLR algorithm constructs Tomita-style SPPFs and thus is also worst-case unbounded polynomial order. We have given a modified worst-case cubic GLR algorithm, that, for any string and any CFG, returns a binarised SPPF representation of all possible derivations of a given string. In this paper we apply similar techniques to develop worst-case cubic Earley and RIGLR parsing algorithms.     

SPPF-Style Parsing From Earley Recognisers

In its recogniser form, Earley's algorithm for testing whether a string can be derived from a grammar is worst case cubic on general context free grammars (CFG). Earley gave an outline of a method for turning his recognisers into parsers, but it turns out that this method is incorrect. Tomita's GLR parser returns a shared packed parse forest (SPPF) representation of all derivations of a given string from a given CFG but is worst case unbounded polynomial order. We have given a modified worst-case cubic version, the BRNGLR algorithm, that, for any string and any CFG, returns a binarised SPPF representation of all possible derivations of a given string. In this paper we apply similar techniques to develop two versions of an Earley parsing algorithm that, in worst-case cubic time, return an SPPF representation of all derivations of a given string from a given CFG.     

Piecewise Polynomial Model Reduction Method for Nonlinear Systems in Time Domain

Model order reduction (MOR) of nonlinear systems draws great attention in the past several decades. This paper presents a new MOR method in time domain for nonlinear dynamical systems. The new algorithm is based on the combination of the Taylor series expansion for the state variable x(t) and the trajectory piecewise polynomial technique. Firstly, the nonlinear system is approximated by a piecewise polynomial representation. Then, based on the Taylor series coefficients of x(t), we formulate the projection matrix V for the piecewise polynomial system and the compact model of the piecewise polynomial system is obtained in the following. Besides, error estimation and stability analysis are also presented in this paper. Finally, two nonlinear systems are tested to verify the effectiveness of the algorithm.     

Sparse representation for coarse and fine object recognition

This paper offers a sparse, multiscale representation of objects. It captures the object appearance by selection from a very large dictionary of Gaussian differential basis functions. The learning procedure results from the matching pursuit algorithm, while the recognition is based on polynomial approximation to the bases, turning image matching into a problem of polynomial evaluation. The method is suited for coarse recognition between objects and, by adding more bases, also for fine recognition of the object pose. The advantages over the common representation using PCA include storing sampled points for recognition is not required, adding new objects to an existing data set is trivial because retraining other object models is not needed, and significantly in the important case where one has to scan an image over multiple locations in search for an object, the new representation is readily available as opposed to PCA projection at each location. The experimental result on the COIL-100 data set demonstrates high recognition accuracy with real-time performance.     

Pole assignment by state transition graph

The pole assignment problem is considered, using the graph representation of a matrix. The parametrization of controllers which have a specified characteristic polynomial is given. A simple algorithm based on graphs is presented and two examples are given     

Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients

We present a hybrid symbolic-numeric algorithm for certifying a polynomial or rational function with rational coefficients to be non-negative for all real values of the variables by computing a representation for it as a fraction of two polynomial sum-of-squares (SOS) with rational coefficients. Our new approach turns the earlier methods by Peyrl and Parrilo at SNC’07 and ours at ISSAC’08 both based on polynomial SOS, which do not always exist, into a universal algorithm for all inputs via Artin’s theorem.Furthermore, we scrutinize the all-important process of converting the numerical SOS numerators and denominators produced by block semidefinite programming into an exact rational identity. We improve on our own Newton iteration-based high precision refinement algorithm by compressing the initial Gram matrices and by deploying rational vector recovery aside from orthogonal projection. We successfully demonstrate our algorithm on (1) various exceptional SOS problems with necessary polynomial denominators from the literature and on (2) very large (thousands of variables) SOS lower bound certificates for Rump’s model problem (up to n=18, factor degree=17).     

Equivalence of Polynomial Identity Testing and Polynomial Factorization

In this paper, we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a multivariate polynomial f, the task of computing arithmetic circuits for the factors of f can be solved deterministically, given a deterministic algorithm for the polynomial identity testing problem (we require either a white-box or a black-box algorithm, depending on the representation of f).Together with the easy observation that deterministic factoring implies a deterministic algorithm for polynomial identity testing, this establishes an equivalence between these two central derandomization problems of arithmetic complexity.Previously, such an equivalence was known only for multilinear circuits (Shpilka & Volkovich, 2010).     

Ridge polynomial networks.

This paper presents a polynomial connectionist network called ridge polynomial network (RPN) that can uniformly approximate any continuous function on a compact set in multidimensional input space R (d), with arbitrary degree of accuracy. This network provides a more efficient and regular architecture compared to ordinary higher-order feedforward networks while maintaining their fast learning property. The ridge polynomial network is a generalization of the pi-sigma network and uses a special form of ridge polynomials. It is shown that any multivariate polynomial can be represented in this form, and realized by an RPN. Approximation capability of the RPN's is shown by this representation theorem and the Weierstrass polynomial approximation theorem. The RPN provides a natural mechanism for incremental network growth. Simulation results on a surface fitting problem, the classification of high-dimensional data and the realization of a multivariate polynomial function are given to highlight the capability of the network. In particular, a constructive learning algorithm developed for the network is shown to yield smooth generalization and steady learning.     

Knot placement for piecewise polynomial approximation of curves

For piecewise polynomial representation of curves, an algorithm to create knots is presented. The aim is to minimize the interpolation error for a given number of knots or, conversely, the number of knots needed to interpolate within a tolerance. The method used is a modification of de Boor's knot placement scheme. The algorithm described in this paper has been realized in the CADCAM system SYRKO, a Daimler-Benz development for car body design and manufacturing.     

动态调整步长的参数曲线生成算法

本文提出一种在图形显示设备上生成参数曲线的通用算法 ,使生成的曲线精确到象素级 (即以象素逼近曲线上的点 ) .本算法采用在曲线生成过程中动态调整步长的方法 ,调整步长的方法简便 ,无需增加太多的计算量 .应用算法的结果表明 ,生成的曲线既可达到所要求的精确度又可大大地避免点的重复计算 .除了精确到象素级外 ,该算法也适用于其它精确度要求 ,如用折线逼近曲线时 ,相邻两点之间的距离小于给定值等 .而且该算法适用于一切多项式的、有理的或其它形式的参数曲线 ,不受曲线表示形式和曲线次数的限制 .