A new algorithm for sparse interpolation of multivariate polynomials

To reconstruct a black box multivariate sparse polynomial from its floating point evaluations, the existing algorithms need to know upper bounds for both the number of terms in the polynomial and the partial degree in each of the variables. Here we present a new technique, based on Rutishauser’s qd$qd$-algorithm, in which we overcome both drawbacks.     

On the decomposition of rational functions

Let f:=p/q∈K(x)$f:=p/q\in \mathbb{K}\left(x\right)$ be a rational function in one variable. By Lüroth’s theorem, the collection of intermediate fields K(f)?L?K(x)$\mathbb{K}\left(f\right)?\mathbb{L}?\mathbb{K}\left(x\right)$ is in bijection with inequivalent proper decompositions f=g°h$f=g°h$, with g,h∈K(x)$g,h\in \mathbb{K}\left(x\right)$ of degrees ≥2$\ge 2$. In [Alonso, Cesar, Gutierrez, Jaime, Recio, Tomas, 1995. A rational function decomposition algorithm by near-separated polynomials. J. Symbolic Comput. 19, 527–544] an algorithm is presented to calculate such a function decomposition. In this paper we describe a simplification of this algorithm, avoiding expensive solutions of linear equations. A MAGMA implementation shows the efficiency of our method. We also prove some indecomposability criteria for rational functions, which were motivated by computational experiments.     

Modeling orientation fields of fingerprints with rational complex functions

In this paper, a novel model is proposed for the orientation field of fingerprints, which can be expressed as the argument of a rational complex function. It is suitable for all types of fingerprints. Experimental results show that it performs much better than the previous works.     

An algorithm for interpolation with positive rational functions on the imaginary axis

A procedure is shown to construct a rational transfer function that is real-valued and positive on the imaginary axis. The degree of the solution is lowered with respect to solutions based on existing algorithms. The results can be applied to problems such as the robust strictly positive real problem.     

Using multivariate resultants to find the implicit equation of a rational surface

Given a parametrization of a rational surface, the absence of base points is shown to be a necessary and sufficient condition for the auxiliary resultant to be a power of the implicit polynomial. The method of resultants also reveals other important properties of rational surface representations, including the coefficients of the implicit equation, the relationship between the implicit and parametric degrees, the degree of each coordinate variable of the implicit equation, and the number of correspondence of the parametrization.     

Pattern discrimination using ellipsoidally symmetric multivariate density functions

A brief review of ellipsoidally symmetric density functions is done. For the case of monotonic functional forms and distributions with common covariance matrices, a lower bound on the probability of correct classification is calculated in terms of either an incomplete beta or gamma integral, for a class of common functional forms. The lower bound is a monotonically increasing function of the Mahalanobis distance for all monotonic ellipsoidally symmetric forms.     

Geometric Hermite interpolation with circular precision

We present several Hermite-type interpolation methods for rational cubics. In case the input data come from a circular arc, the rational cubic will reproduce it.     

The class of HDT0L sequences is closed with respect to rational functions

We show that the class of HDT0L sequences is closed with respect to total rational functions.     

On the scalar rational interpolation problem

A new technique is derived for determining a parametrization of all minimal complexity rational functionsa(x)/b(x) interpolating an arbitrary sequence of points. Complexity is measured in terms of max{deg(a), deg(b) +r } wherer is an arbitrary integer (so thatr=0 corresponds to the McMillan degree). Our construction uses Gröbner bases of submodules of the free module of rank 2 over the polynomial ring in one variable and extends previous work on the key equation of error control coding theory.     

一种含参数的双线性有理插值的图像缩放方法

通过一种基于函数值的分母与分子均为一次的线性有理插值函数构造出带参数的叹线性有理插值函数,该函数形式简单,灵活度高。利用该函数提出了一种新的图像插值算法,实验表明,该方法控制灵活,能有效实现图像的缩放。     

Conchoid surfaces of rational ruled surfaces

The conchoid surface G of a given surface F with respect to a point O is roughly speaking the surface obtained by increasing the radius function of F with respect to O by a constant d. This paper studies real rational ruled surfaces in this context and proves that their conchoid surfaces possess real rational parameterizations, independently of the position of O. Thus any rational ruled surface F admits a rational radius function r(u,v) with respect to any point in space. Besides the general skew ruled surfaces and examples of low algebraic degree we study ruled surfaces generated by rational motions.     

Regional stabilisation of polynomial non-linear systems using rational Lyapunov functions

In this article, we propose a new non-linear stabilisation approach based on the popular linear parameter-varying control techniques. The regional state-feedback control problem of polynomial non-linear systems will be studied using rational Lyapunov functions of states. By bounding the variation rates of each state, the domain of attraction will be embedded in the region specified by the non-linear vector field. As a result, the state-feedback stabilisation conditions will be formulated as a set of polynomial matrix inequalities and can be solved efficiently by sum-of-squares programming. The resulting Lyapunov matrix and state-feedback gains are typically state-dependent rational matrix functions. This approach is also extended to a class of output-dependent non-linear systems where the stabilising output-feedback controller can be synthesised using rational Lyapunov functions of outputs. Finally, several examples will be used to demonstrate the proposed stabilisation approach and clarify the effect of various choices of Lyapunov function forms and state constraints.     

A new algorithm for a recursive construction of the minimal interpolation space

In this work, we introduce a new interpolation algorithm, based on a recursive method for computing Lagrange interpolants. This algorithm allows to construct recursively the minimal interpolation space (see [1]) with respect to a finite set of points. We also extend this recursive method to the osculatory interpolation problem.     

On the decidability of sparse univariate polynomial interpolation

We consider the problem of determining whether or not there exists a sparse univariate polynomial that interpolates a given setS={(x _i ,y _i )} of points. Several important cases are resolved, e.g., the case when thex _i's are all positive rational numbers. But the general problem remains open.     

Error analysis of the derivative of rational interpolation with a linear denominator

This paper deals with the approximation properties of the derivatives of rational cubic interpolation with a linear denominator. Error expressions of the derivatives of interpolating functions are derived, convergence is established and the optimal error coefficient c _i is proved to be symmetric about the parameters of the rational interpolation. The unified integral form of the error of the second derivative in all subintervals is obtained. A simple expression of the jump of the second derivative at the knots and the conditions for the interpolating function to be C ² in the interpolating interval are given.     

Counting with rational generating functions

We examine two different ways of encoding a counting function: as a rational generating function and explicitly as a function (defined piecewise using the greatest integer function). We prove that, if the degree and number of input variables of the (quasi-polynomial) function are fixed, there is a polynomial time algorithm which converts between the two representations. Examples of such counting functions include Ehrhart quasi-polynomials, vector partition functions, integer points in parametric polytopes, and projections of the integer points in parametric polytopes. For this last example, this algorithm provides the first known way to compute the explicit function in polynomial time. We rely heavily on results by Barvinok and Pommersheim [Barvinok, A., Pommersheim, J., 1999. An algorithmic theory of lattice points in polyhedra. In: New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996–97). In: Math. Sci. Res. Inst. Publ., vol. 38. Cambridge Univ. Press, Cambridge, pp. 91–147], and also by Verdoolaege et al. [Verdoolaege, S., Seghir, R., Beyls, K., Loechner, V., Bruynooghe, M., 2007. Counting integer points in parametric polytopes using Barvinok’s rational functions, Algorithmica 48 (1), 37–66].     

Efficient Parallel Computation of the Characteristic Polynomial of a Sparse, Separable Matrix

{This paper is concerned with the problem of computing the characteristic polynomial of a matrix. In a large number of applications, the matrices are symmetric and sparse : with O(n) non-zero entries. The problem has an efficient sequential solution in this case, requiring O(n ² ) work by use of the sparse Lanczos method. A major remaining open question is: to find a polylog time parallel algorithm with matching work bounds. Unfortunately, the sparse Lanczos method cannot be parallelized to faster than time Ω (n) using n processors. Let M(n) be the processor bound to multiply two n \times n matrices in O(log n) parallel time. Giesbrecht [G2] gave the best previous polylog time parallel algorithms for the characteristic polynomial of a dense matrix with O (M(n)) processors. There is no known improvement to this processor bound in the case where the matrix is sparse. Often, in addition to being symmetric and sparse, the matrix has a sparsity graph (which has edges between indices of the matrix with non-zero entries) that has small separators. This paper gives a new algorithm for computing the characteristic polynomial of a sparse symmetric matrix, assuming that the sparsity graph is s(n) -separable and has a separator of size s(n)=O(n ^γ ) , for some γ , 0 < γ < 1 , that when deleted results in connected components of ≤α n vertices, for some 0 < α < 1 , with the same property. We derive an interesting algebraic version of Nested Dissection, which constructs a sparse factorization of the matrix A-λ I _n where A is the input matrix and I _n is the n \times n identity matrix. While Nested Dissection is commonly used to minimize the fill-in in the solution of sparse linear systems, our innovation is to use the separator structure to bound also the work for manipulation of rational functions in the recursively factored matrices. The matrix elements are assumed to be over an arbitrary field. We compute the characteristic polynomial of a sparse symmetric matrix in polylog time using P(n)(n+M(s(n))) ≤ P(n)(n+ s(n) ^2.376 ) processors, where P(n) is the processor bound to multiply two degree n polynomials in O(log n) parallel time using a PRAM (P(n) = O(n) if the field supports an FFT of size n but is otherwise O(nlog log n) [CK]. Our method requires only that a matrix be symmetric and non-singular (it need not be positive definite as usual for Nested Dissection techniques). For the frequently occurring case where the matrix has small separator size, our polylog parallel algorithm has work bounds competitive with the best known sequential algorithms (i.e., the Ω(n ² ) work of sparse Lanczos methods), for example, when the sparsity graph is a planar graph, s(n) ≤ O( \sqrt n ) , and we require polylog time with only P(n)n ^1.188 processors. } Received September 26, 1997; revised June 5, 1999.