基于区块链的具有隐私保护的多项式外包计算方案

随着区块链的快速发展,基于区块链的外包计算得到了广泛应用.外包计算允许资源受限的用户将复杂的计算以付费的方式外包给资源强大的外包计算者来计算,从而可以便捷地获得计算结果.然而外包计算过程中可能会泄露用户的隐私数据,因此,在外包计算过程中需要考虑用户数据的隐私性、安全性以及计算结果的可验证性。本文针对高阶多项式的外包计算进行研究,提出了基于区块链的可验证外包多项式计算方案,通过区块链智能合约完成外包计算。首先,提出了一种混淆方法,能够将原始多项式系数进行盲化,从而保证多项式的安全性和隐私性。外包计算者将盲化后的两个多项式进行计算,计算结果上传至星际文件系统(IPFS),同时挖矿节点仅需计算一个盲化后的多项式;其次,设计了一种可快速、简单的验证方法,智能合约通过用户给出的参数能快速的对外包计算者及挖矿节点返回的计算结果进行验证,根据验证结果给予相应的报酬。整个方案不需要任何密码学假设,通过外包计算者和挖矿节点的双重计算,保证了方案的安全性且效率较高。     

Exact algorithms for polynomial real root approximation using continued fractions

This paper discusses a set of algorithms which, given a polynomial equation with integer coefficients and without any multiple roots, uses exact (infinite precision) integer arithmetic, an idea by Lagrange (1767), and Vincent's theorem of 1836, to approximate the real roots of the polynomial equation to any degree of accuracy using continued fractions. Theoretical computing time bounds are developed for these algorithms and some empirical results are presented.     

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.     

The root-locus method of synthesis of stable polynomials by adjustment of all coefficients

The problem of synthesis of an asymptotically stable polynomial on the basis of the initial unstable polynomial is solved. For the purpose of its solution, the notion of the extended (complete) root locus of a polynomial is introduced, which enables one to observe the dynamics of all its coefficients simultaneously, to isolate the root-locus trajectories, along which values of each coefficient change, to establish their interrelation, which provides a way of using these trajectories as “conductors” for the movement of roots in the desired domains. Values of the coefficients that ensure the stability of a polynomial are chosen from the stability intervals found on the stated trajectories as the nearest values to the values of appropriate coefficients of the unstable polynomial or by any other criterion, for example, the criterion of provision of the required stability reserve. The sphere of application of the root locus, which is conventionally used for synthesis of characteristic polynomials through the variation of only one parameter (coefficient) of the polynomial, is extended for the synthesis of polynomials by way of changing all coefficients and with many changing coefficients. Examples of application of the developed algorithm are considered for the synthesis of stable polynomials with constant and interval coefficients.     

Approximate polynomial GCD over integers

Symbolic numeric algorithms for polynomials are very important, especially for practical computations since we have to operate with empirical polynomials having numerical errors on their coefficients. Recently, for those polynomials, a number of algorithms have been introduced, such as approximate univariate GCD and approximate multivariate factorization for example. However, for polynomials over integers having coefficients rounded from empirical data, changing their coefficients over reals does not remain them in the polynomial ring over integers; hence we need several approximate operations over integers. In this paper, we discuss computing a polynomial GCD of univariate or multivariate polynomials over integers approximately. Here, “approximately” means that we compute a polynomial GCD over integers by changing their coefficients slightly over integers so that the input polynomials still remain over integers.     

Bounds for an interval polynomial

We discuss the evaluation of the range of values of an interval polynomial over an interval. Several algorithms are proposed and tested on numerical examples. The algorithms are based on ideas by Cargo and Shiska [2] and Rivlin [4]. The one basic algorithm uses Bernstein polynomials. It is shown to converge to the exact bounds and it has furthermore the property that if the maximum respectively the minimum of the polynomials occurs at an endpoint of the interval then the bound is exact. This is a useful property in routines for polynomials zeros. The other basic method is based on the meanvalue theorem and it has the advantage that the degree of approximation required for a certain apriori tolerance is smaller than the degree required in the Bernstein polynomial case. The mean value method is shown to be at least quadratically convergent and the Bernstein polynomial method is shown to be at least linearly convergent.     

Approximate GCDs of polynomials and sparse SOS relaxations

The problem of computing approximate GCDs of several polynomials with real or complex coefficients can be formulated as computing the minimal perturbation such that the perturbed polynomials have an exact GCD of given degree. We present algorithms based on SOS (Sums Of Squares) relaxations for solving the involved polynomial or rational function optimization problems with or without constraints.     

多项式泛函网络运算模型及应用

提出了一种多项式泛函网络运算新模型,来求解任意数域或环上多项式运算问题。同时给出了基于泛函网络求任意一元多项式倍式的学习算法,而网络的参数利用解线性方程组方法来完成。实验结果表明,这种神经计算方法,相对传统方法,不但能够获得问题的精确解,而且可获得问题的近似解。这给工程计算软件的二次开发提供了有效方法。     

基于多生成树和子网-节点度联合权重的MCDS构造算法

提出了一种基于多生成树和子网-节点度联合权重的静态无线网络极小连通支配集MCDS构造算法SWNMCDS。算法首先设定一个概率p,每个节点随机生成一个概率并与p对比后决定是否成为候选根节点。两跳范围内的候选根节点相互交换信息,确定最终的根节点。每个根节点基于节点权重的连通树生成算法生成多棵连通树。最后基于子网-节点度联合权重选择连通节点,将多棵连通树连成极小连通支配集。经分析,SWNMCDS算法近似比上限为2β(2+H(Δ)),时间复杂度为O(Δ2),消息复杂度为O(Δ2)(Δ为最大一跳邻居节点集合的大小,β为生成树数目)。仿真实验表明,与经典MCDS算法比较,SWNMCDS所构造的连通支配集具有较小的规模。     

Extending Kharitonov's theorem to eigenvalues clustering in subregions of the complex plane

Sufficient conditions are developed for root clustering of a polynomial in a transformable region when each of the polynomial coefficients takes an arbitrary but fixed value within a specified closed interval. The conditions are in terms of the Kronecker products or the bialternate products. The sufficient conditions are then applied to different subregions in the complex plane. The work of Barmish (1984) on the invariance of the strict Hurwitz property for interval polynomials with perturbed coefficients is extended to root clustering in a region.     

Cayley–Dixon projection operator for multi-univariate composed polynomials

The Cayley–Dixon formulation for multivariate projection operators (multiples of resultants of multivariate polynomials) has been shown to be efficient (both experimentally and theoretically) for simultaneously eliminating many variables from a polynomial system. In this paper, the behavior of the Cayley–Dixon projection operator and the structure of Dixon matrices are analyzed for composed polynomial systems constructed from a multivariate system in which each variable is substituted by a univariate polynomial in a distinct variable. Under some conditions, it is shown that a Dixon projection operator of the composed system can be expressed as a power of the resultant of the outer polynomial system multiplied by powers of the leading coefficients of the univariate polynomials substituted for variables in the outer system. A new resultant formula is derived for systems where it is known that the Cayley–Dixon construction does not contain any extraneous factor. The complexity of constructing Dixon matrices and roots at toric infinity of composed polynomials is analyzed.     

Interpolation type problems in the class of positive trigonometric polynomials of fixed order

This paper is devoted to a family of interpolation type problems for positive trigonometric polynomials of a given ordern. Via the Riesz-Fejér factorization theorem, they can be viewed as natural generalizations of the partial autocorrelation problem for discrete time signals of lengthn+1. The relevant variables for a specific problem are well-defined linear combinations of the coefficients of the underlying trigonometric polynomial. An efficient method is obtained to characterize the feasibility region of the problem, defined as the set of points having these variables as coordinates. It allows us to determine the boundary of that region by computing the extreme eigen values and the corresponding eigenvectors of certain well-defined Hermitian Toeplitz matrices of ordern+1. The method is an extension of one proposed by Steinhardt to solve the coefficient problem for positive cosine polynomials (which belongs to the family). Other interesting applications are the Nevanlinna-Pick interpolation problem for polynomial functions, and the simple interpolation problem for positive trigonometric polynomials. The close connection between the generalized Steinhardt method and classical techniques based on the polarity theorem for convex cones and on the Hahn-Banach extension theorem are established.     

Polynomial collocation using a domain decomposition solution to parabolic PDE's via the penalty method and explicit/implicit time marching

A domain decomposition method is examined to solve a time-dependent parabolic equation. The method employs an orthogonal polynomial collocation technique on multiple subdomains. The subdomain interfaces are approximated with the aid of a penalty method. The time discretization is implemented in an explicit/implicit finite difference method. The subdomain interface is approximated using an explicit Dufort-Frankel method, while the interior of each subdomain is approximated using an implicit backwards Euler's method. The principal advantage to the method is the direct implementation on a distributed computing system with a minimum of interprocessor communication. Theoretical results are given for Legendre polynomials, while computational results are given for Chebyshev polynomials. Results are given for both a single processor computer and a distributed computing system.     

Identification of linear systems using polynomial kernels in the frequency domain

In prior work we presented an identification algorithm using polynomials in the time domain. In this article, we extend this algorithm to include polynomials in the frequency domain. A polynomial is used to represent the imaginary part of the Fourier transform of the impulse response. The Hilbert transform relationship is used to compute the real part of the frequency response and hence the complete process model. The polynomial parameters are computed based on the computationally efficient linear least square method. The order of the polynomial is estimated based on residue decrement. Simulated and experimental results show the effectiveness of this method, particularly for short input/output data sequence with high signal to noise ratio. The frequency domain polynomial model complements the time domain methods since it can provide a good estimate of the time to steady state for time domain FIR (finite impulse response) models. Confidence limits in time or frequency domain can be computed using this approach. Noise rejection properties of the algorithm are illustrated using data from both simulated and real processes.     

Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic

Algebraic function fields of positive characteristic are non-perfect fields, and many standard algorithms for solving some fundamental problems in commutative algebra simply do not work over these fields. This paper presents practical algorithms for the first time for (1) computing the primary decomposition of ideals of polynomial rings defined over such fields and (2) factoring arbitrary multivariate polynomials over such fields. Difficulties involving inseparability and the situation where the transcendence degree is greater than one are completely overcome, while the algorithms avoid explicit construction of any extension of the input base field. As a corollary, the problem of computing the primary decomposition of a positive-dimensional ideal over a finite field is also solved. The algorithms perform very effectively in an implementation within the Magma Computer Algebra System, and an analysis of their practical performance is given.     

A new result on the p-irreducibility of binding polynomials

Binding polynomials and p-irreducibility are important concepts in biochemistry. In this paper, we study the p-irreducibility of binding polynomials with degree four and present, for the first time, an explicit criterion for p-irreducibility, which is expressed by polynomials in the coefficients of a given binding polynomial.     

Computation of the Bernstein Coefficients on Subdivided Triangles

We present a procedure for computing the coefficients of the expansion of a bivariate polynomial into Bernstein polynomials over subtriangles. These triangles are generated by partitioning the unit triangle. The coefficients are computed directly from the coefficients on the subdivided triangle from the preceding subdivision level. This allows a recursive computation of the coefficients and facilitates the economical computation of bounds for the range of a bivariate polynomial over a given triangle.     

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

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

Solution of a scaled system via generalized orthogonal polynomials

Generalized orthogonal polynomials which include all types of orthogonal polynomial are introduced first. Using the idea of orthogonal polynomials that can be expressed by a Taylor power series and vice versa, the operational matrix for the integration of the generalized orthogonal polynomials is first derived. A stretched operational matrix of diagonal form is also derived. Both the operational matrix for the integration and the stretched operational matrix of generalized orthogonal polynomials are applied to solve functional differential equations. The characteristics of each kind of orthogonal polynomial in solving the scaled system is demonstrated. The computational strategy for finding the expansion coefficients of the state variables is very simple, straightforward and easy. The inversion of only one matrix, which has the same dimension as the state variables, is required. The expansion coefficients of the state variables are obtained by the proposed recursive formula. Much computer time is thus saved and computational results are obtained that are very accurate compared with previous methods.     

Approximating Tree Edit Distance through String Edit Distance

We present an algorithm to approximate edit distance between two ordered and rooted trees of bounded degree. In this algorithm, each input tree is transformed into a string by computing the Euler string, where labels of some edges in the input trees are modified so that structures of small subtrees are reflected to the labels. We show that the edit distance between trees is at least 1/6 and at most O(n ^3/4) of the edit distance between the transformed strings, where n is the maximum size of two input trees and we assume unit cost edit operations for both trees and strings. The algorithm works in O(n ²) time since computation of edit distance and reconstruction of tree mapping from string alignment takes O(n ²) time though transformation itself can be done in O(n) time.