An empirical study of cache-oblivious polygon indecomposability testing

We implement and undertake an empirical study of the cache-oblivious variant of the polygon indecomposability testing algorithm of Gao and Lauder, based on a depth-first search (DFS) traversal of the computation tree. According to Abu Salem, the cache-oblivious variant exhibits improved spatial and temporal locality over the original one, and its spatial locality is optimal. Our implementation revolves around eight different variants of the DFS-based algorithm, tailored to assess the trade-offs between computation and memory performance as originally proposed by Abu Salem. We analyse performance sensitively to manipulations of the several parameters comprising the input size. We describe how to construct suitably random families of input that solicit such variations, and how to handle redundancies in vector computations at no asymptotic increase in the work and cache complexities. We report extensively on our experimental results. In all eight variants, the DFS-based variant achieves excellent performance in terms of L1 and L2 cache misses as well as total run time, when compared to the original variant of Gao and Lauder. We also benchmark the DFS variant against the powerful computer algebra system MAGMA, in the context of bivariate polynomial irreducibility testing using polygons. For sufficiently high degree polynomials, MAGMA either runs out of memory or fails to terminate after about 4 h of execution. In contrast, the DFS-based version processes such input using a couple of seconds. Particularly, we report on absolute irreducibility testing of bivariate polynomials of total degree reaching 19,000 in about 2 s for the DFS variant, using a single processor.     

Polytope-based computation of polynomial ranges

Polynomial ranges are commonly used for numerically solving polynomial systems with interval Newton solvers. Often ranges are computed using the convex hull property of the tensorial Bernstein basis, which is exponential size in the number n of variables. In this paper, we consider methods to compute tight bounds for polynomials in n variables by solving two linear programming problems over a polytope. We formulate a polytope defined as the convex hull of the coefficients with respect to the tensorial Bernstein basis, and we formulate several polytopes based on the Bernstein polynomials of the domain. These Bernstein polytopes can be defined by a polynomial number of halfspaces. We give the number of vertices, the number of hyperfaces, and the volume of each polytope for n=1,2,3,4, and we compare the computed range widths for random n-variate polynomials for n?10. The Bernstein polytope of polynomial size gives only marginally worse range bounds compared to the range bounds obtained with the tensorial Bernstein basis of exponential size.     

多元多项式函数的三层前向神经网络逼近方法

该文首先用构造性方法证明:对任意r阶多元多项式,存在确定权值和确定隐元个数的三层前向神经网络.它能以任意精度逼近该多项式.其中权值由所给多元多项式的系数和激活函数确定,而隐元个数由r与输入变量维数确定.作者给出算法和算例,说明基于文中所构造的神经网络可非常高效地逼近多元多项式函数.具体化到一元多项式的情形,文中结果比曹飞龙等所提出的网络和算法更为简单、高效;所获结果对前向神经网络逼近多元多项式函数类的网络构造以及逼近等具有重要的理论与应用意义,为神经网络逼近任意函数的网络构造的理论与方法提供了一条途径.     

Parallel computation of determinants of matrices with multivariate polynomial entries

In this paper we present an extension to the work of Björck et al. for computing the determinants of matrices with univariate or bivariate polynomials as entries to multivariate case. The algorithm supports parallel computation and has been implemented on a multi-core cluster computer system. We show how to use our approach to calculate two unsolved problems, which arise from computational geometry optimization and electric power engineering, and analyze the time complexity as well as bits complexity.     

Single-lifting Macaulay-type formulae of generalized unmixed sparse resultants

Resultants are defined in the sparse (or toric) context in order to exploit the structure of the polynomials as expressed by their Newton polytopes. Since determinantal formulae are not always possible, the most efficient general method for computing resultants is rational formulae. This is made possible by Macaulay’s famous determinantal formula in the dense homogeneous case, extended by D’Andrea to the sparse case. However, the latter requires a lifting of the Newton polytopes, defined recursively on the dimension. Our main contribution is a single-lifting function of the Newton polytopes, which avoids recursion, and yields a simpler method for computing Macaulay-type formulae of sparse resultants. We focus on the case of generalized unmixed systems, where all Newton polytopes are scaled copies of each other, and sketch how our approach may extend to mixed systems of up to four polynomials, as well as those whose Newton polytopes have a sufficiently different face structure. In the mixed subdivision used to construct the matrices, our algorithm defines significantly fewer cells than D’Andrea’s, though the matrix formulae are same. We discuss asymptotic complexity bounds and illustrate our results by fully studying a bivariate example.     

Semi-numerical absolute factorization of polynomials with integer coefficients

In this paper, we propose a semi-numerical algorithm for computing absolute factorization of multivariate polynomials. It is based on some properties appearing after a generic change of coordinate. Using numerical computation, Galois group action and rational approximation, this method provides an efficient probabilistic algorithm for medium degrees. Two implementations are presented and compared to other algorithms.     

An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography

In this paper, we present an efficient and general algorithm for decomposing multivariate polynomials of the same arbitrary degree. This problem, also known as the Functional Decomposition Problem (FDP), is classical in computer algebra. It is the first general method addressing the decomposition of multivariate polynomials (any degree, any number of polynomials). As a byproduct, our approach can be also used to recover an ideal I from its kth power I^k. The complexity of the algorithm depends on the ratio between the number of variables (n) and the number of polynomials (u). For example, polynomials of degree four can be decomposed in , when this ratio is smaller than . This work was initially motivated by a cryptographic application, namely the cryptanalysis of 2R⁻ schemes. From a cryptographic point of view, the new algorithm is so efficient that the principle of two-round schemes, including 2R⁻ schemes, becomes useless. Besides, we believe that our algorithm is of independent interest.     

Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth

We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobás, and Sorkin (J. Comb. Theory Ser. B 92(2):199–233, 2004) and by Aigner and van der Holst (Linear Algebra Appl., 2004). We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k. The best previously known result (Courcelle, Electron. J. Comb. 15(1), 2008) employs a general logical framework and leads to an algorithm with running time f(k)⋅n, where f(k) is doubly exponential in k. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm uses 2^3k2+O(k)·n2^{3k^{2}+O(k)}\cdot n arithmetic operations and can be efficiently implemented in parallel.     

Hurwitz testing sets for parallel polytopes of polynomials

In considering robustness of linear systems with uncertain paramenters, one is lead to consider simultaneous stability of families of polynomials. Efficient Hurwitz stability tests for polytopes of polynomials have earlier been developed using evaluations on the imaginary axis. This paper gives a stability criterion for parallel polytopes in terms of Hurwitz stability of a number of corners and edges. The ‘testing set’ of edges and corners depends entirely on the edge directions of the polytope, hence the results are particularly applicable in simultaneous analysis of several polytopes with equal edge directions.It follows as a consequence, that Kharitonov's four polynomial test for independent coefficient uncertainties is replaced by a test of 2q polynomials, when the stability region is a sector Ω = { e^iv | > 0, rπ/q < | v | ≤ π } and r/q is a rational number.     

Parallel algorithm for computing fixpoints of Galois connections

This paper presents a parallel algorithm for computing fixpoints of Galois connections induced by object-attribute relational data. The algorithm results as a parallelization of CbO (Kuznetsov 1999) in which we process disjoint sets of fixpoints simultaneously. One of the distinctive features of the algorithm compared to other parallel algorithms is that it avoids synchronization which has positive impacts on its speed and implementation. We describe the parallel algorithm, prove its correctness, and analyze its asymptotic complexity. Furthermore, we focus on implementation issues, scalability of the algorithm, and provide an evaluation of its efficiency on various data sets.     

Algebraic manipulation in the Bernstein form made simple via convolutions

Traditional methods for algebraic manipulation of polynomials in Bernstein form try to obtain an explicit formula for each coefficient of the result of a given procedure, such us multiplication, arbitrarily high degree elevation, composition, or differentiation of rational functions. Whereas this strategy often furnishes involved expressions, these operations become trivial in terms of convolutions between coefficient lists if we employ the scaled Bernstein basis, which does not include binomial coefficients. We also carry over this scheme from the univariate case to multivariate polynomials, Bézier simplexes of any dimension and B-bases of other functional spaces. Examples of applications in geometry processing are provided, such as conversions between the triangular and tensor-product Bézier forms.     

On the complete instability of interval polynomials

In this paper, we study “complete instability” of interval polynomials, which is the counterpart of classical robust stability. That is, the objective is to check if all polynomials in the family are unstable. If not, a subsequent goal is to find a stable polynomial. To this end, we first propose a randomized algorithm which is based on a (recursive) necessary condition for Hurwitz stability. The second contribution of this paper is to provide a probability-one estimate of the volume of stable polynomials. These results are based on a combination of deterministic and randomized methods. Finally, we present two numerical examples and simulations showing the efficiency of the proposed methodology for small and medium-size problems.     

Necessary conditions for Hadamard factorizations of Hurwitz polynomials

A property of Hurwitz polynomials is related with the Hadamard product. Garloff and Wagner proved that Hadamard products of Hurwitz polynomials are Hurwitz polynomials, and Garloff and Shrinivasan shown that there are Hurwitz polynomials of degree 4 which do not have a Hadamard factorization into two Hurwitz polynomials of the same degree 4. In this paper, we give necessary conditions for an even-degree Hurwitz polynomial to have a Hadamard factorization into two even-degree Hurwitz polynomials; such conditions are given in terms of the coefficients of the given polynomial alone. Furthermore, we show that if an odd-degree Hurwitz polynomial has a Hadamard factorization then a system of nonlinear inequalities has at least one solution.     

Resultants of partially composed polynomials

We study the structure of resultants of two homogeneous partially composed polynomials. By two homogeneous partially composed polynomials we mean a pair of polynomials of which one does not have any given composition structure and the other is obtained by composing a bivariate homogeneous polynomial with two bivariate homogeneous polynomials. The main contributions are two equivalent formulas, each representing the resultant of two partially composed polynomials as a certain iterated resultant of the component polynomials. Furthermore, in many cases, this iterated resultant can be computed with dramatically increased efficiency, as demonstrated by experiments.     

A novel algorithm for explicit optimal multi-degree reduction of triangular surfaces

This paper introduces the algebraic property of bivariate orthonormal Jacobi polynomials into geometric approximation. Based on the latest results on the transformation formulae between bivariate Bernstein polynomials and Jacobi polynomials, we naturally deduce a novel algorithm for multi-degree reduction of triangular B~zier surfaces. This algorithm possesses four characteristics： ability of error forecast, explicit expression, less time consumption, and best precision. That is, firstly, whether there exists a multi-degree reduced surface within a prescribed tolerance is judged beforehand; secondly, all the operations of multi-degree reduction are just to multiply the column vector generated by sorting the series of the control points of the original surface in lexicographic order by a matrix; thirdly, this matrix can be computed at one time and stored in an array before processing degree reduction; fourthly, the multi-degree reduced surface achieves an optimal approximation in the norm L2. Some numerical experiments are presented to validate the effectiveness of this algorithm, and to show that the algorithm is applicable to information processing of products in CAD system.     

The Pythagoras number of real sum of squares polynomials and sum of square magnitudes of polynomials

In this paper, we conjecture a formula for the value of the Pythagoras number for real multivariate sum of squares polynomials as a function of the (total or coordinate) degree and the number of variables. The conjecture is based on the comparison between the number of parameters and the number of conditions for a corresponding low-rank representation. This is then numerically verified for a number of examples. Additionally, we discuss the Pythagoras number of (complex) multivariate Laurent polynomials that are sum of square magnitudes of polynomials on the $n$ -torus. For both types of polynomials, we also propose an algorithm to numerically compute the Pythagoras number and give some numerical illustrations.     

Finding nondegenerate Hopf bifurcation points for four-dimensional two-parametric systems

We establish a numerically feasible algorithm to find a simplicial approximation A to a certain part of the boundary of the set of stable (or Hurwitz) polynomials of degree 4. Moreover, we have that . Using this, we build an algorithm to find a piecewise-linear approximation to the intersection curve of a given surface contained in ⁴ with . We have also devised an efficient computer program to perform all these operations. The main motivation is to find the curve of nondegenerate bifurcation points in parameter space for a given 2-parametric Hopf bifurcation problem of dimension 4.     

Elimination and resultants. 1. Elimination and bivariate resultants

We discuss the relevance of elimination theory and resultants in computing, especially in computer graphics and CAGD. We list resultant properties to enhance overall understanding of resultants. For bivariate resultants, we present two explicit expressions: the Sylvester and the Bezout determinants. The Sylvester matrix is easier to construct, but the symmetrical Bezout matrix is structurally richer and thus sometimes more revealing. It let Kajiya (1982) observe directly that a line and a bicubic patch could intersect in at most 18 points, not 36 points, as a naive analysis would presume. For Bezier curves, there is an interesting algebraic and geometric relationship between the implicit equation in Bezout determinant form and the properties of end point interpolation and de Casteljau subdivision. When the two polynomials are of different degrees, the Bezout resultant suffers from extraneous factors. Fortunately, we can easily discard these factors. For problems related to surfaces, we need multivariate resultants: in particular, multivariate resultants for three homogeneous polynomials in three variables     

预测型切比雪夫多项式

预测型切比雪夫多项式,是切比雪夫多项式及最佳逼近理论在预测中的一个推广应用,可以解决一般预测中预测的可知、可控性问题。文中通过讨论后指出,在预测中,当预测误差不超过已知最大绝对误差时,预测将成为可知;当预测区间不超过已知最大范围时,预测将成为可控。基于这个原理,建立了一种具有预测功能的预测型切比雪夫多项式,[Gn(x)]多项式。论证了该多项式依据的微分方程、相关定义、有关性质、数学表式;阐述了该多项式的存在性;给出了[Gn(x)]多项式在[y(x)≠0]条件下构成的预测型最佳逼近[g(x)]多项式;提供了[g(x)]多项式得以实现的具体算法;介绍了一种使预测结果更接近实际值的误差补偿法;并给出了若干应用实例。