Search

Abstract: We study a family of orthogonal polynomials which generalizes a sequence of polynomials considered by L. Carlitz. We show that they are a special case of the Sheffer polynomials and point out some interesting connections with certain Sobolev orthogonal polynomials. [Copyright &y& Elsevier]

Abstract: We recall some bibliography on fast polynomial multiplication related to the recent progress in the paper by Cenk and Ozbudak of 2011. [Copyright &y& Elsevier]

Abstract: This work presents critics'' arguments about the recently defined physical parameter Amlouk-Boubaker Optothermal Expansivity. The detailed definition proposed by Zhang et al. in Materials Letters (No. 64-2009-pp. 778–780) has been based on the minimization of a pondered quadratic function. In the actual study, the uniqueness of the proposed solution is contested on the bases of mathematical evidence, linked to polynomials expansion properties. The authors of the discussed study used a non-weighted evaluation function which involved indifferently two relevant parameters. The suggested corrections along with basic criticism were based on the foundation of optimality rather than those of the optimizing stoichiometry-related protocol itself. [Copyright &y& Elsevier]

A graph G is said to be determined by its generalized spectrum (DGS for short) if whenever Γ is a graph such that Γ and G are cospectral with cospectral complements, then Γ is isomorphic to G . Let G ∪ H be the disjoint union of graphs G and H . In this paper, we give a simple sufficient condition, under which we show that G ∪ H is DGS if and only if both G and H are DGS. In particular, let H = { x } be a singleton graph, we show that if gcd ⁡ ( a n , det ⁡ ( W ( G ) ) ) = 1 and a n is square-free, then G ∪ { x } is DGS if and only if G is DGS, where a n is the constant term of the characteristic polynomial of G and W ( G ) is the walk-matrix of G . It is noticed that in Wang and Xu [9] , the authors gave a sufficient condition for G ∪ { x } to be DGS if G is DGS. However, they missed the condition that a n is square-free in their theorem, and the result obtained is incorrect. We found a counterexample to their result without this condition and give a correct version of the result accordingly in this paper. [ABSTRACT FROM AUTHOR]

Eisenstein polynomials, which were defined by Oura, are analogues of the concept of an Eisenstein series. Oura conjectured that there exist some analogous properties between Eisenstein series and Eisenstein polynomials. In this paper, we provide new analogous properties of Eisenstein polynomials and zeta polynomials. These properties are finite analogies of certain properties of Eisenstein series. [ABSTRACT FROM AUTHOR]

Abstract We establish the universal properties of the bicategory of polynomials, considering both cartesian and general morphisms between these polynomials. A direct proof of these universal properties would be impractical due to the complicated coherence conditions arising from polynomial composition; however, in this paper we avoid most of these coherence conditions using the properties of generic bicategories. In addition, we give a new proof of the universal properties of the bicategory of spans, and also establish the universal properties of the bicategory of spans with invertible 2-cells; showing how these properties may be used to describe the universal properties of polynomials. [ABSTRACT FROM AUTHOR]

Abstract: In our previous paper (Allendes et al., 2013 [10]), we showed that multi-fold Mellin–Barnes (MB) transforms of Usyukina–Davydychev (UD) functions may be reduced to two-fold MB transforms. The MB transforms were written there as polynomials of logarithms of ratios of squares of the external momenta with certain coefficients. We also showed that these coefficients have a combinatoric origin. In this paper, we present an explicit formula for these coefficients. The procedure of recovering the coefficients is based on taking the double-uniform limit in certain series of smooth functions of two variables which is constructed according to a pre-determined iterative way. The result is obtained by using basic methods of mathematical analysis. We observe that the finiteness of the limit of this iterative chain of smooth functions should reflect itself in other mathematical constructions, too, since it is not related in any way to the explicit form of the MB transforms. This finite double-uniform limit is represented in terms of a differential operator with respect to an auxiliary parameter which acts on the integrand of a certain two-fold MB integral. To demonstrate that our result is compatible with original representations of UD functions, we reproduce the integrands of these original integral representations by applying this differential operator to the integrand of the simple integral representation of the scalar triangle four-dimensional integral . [Copyright &y& Elsevier]

Abstract: This paper studies Symmetric Determinantal Representations (SDR) in characteristic 2, that is the representation of a multivariate polynomial P by a symmetric matrix M such that , and where each entry of M is either a constant or a variable. We first give some sufficient conditions for a polynomial to have an SDR. We then give a non-trivial necessary condition, which implies that some polynomials have no SDR, answering a question of Grenet et al. A large part of the paper is then devoted to the case of multilinear polynomials. We prove that the existence of an SDR for a multilinear polynomial is equivalent to the existence of a factorization of the polynomial in certain quotient rings. We develop some algorithms to test the factorizability in these rings and use them to find SDRs when they exist. Altogether, this gives us polynomial-time algorithms to factorize the polynomials in the quotient rings and to build SDRs. We conclude by describing the case of Alternating Determinantal Representations in any characteristic. [Copyright &y& Elsevier]

A classical result due to Eneström and Kakeya gives some bounds for the moduli of the zeros of polynomials having a monotone sequence of non-negative (real) coefficients. The main subject of the present paper is a study of this fact with a view to the recurrence relations fulfilled by systems of orthogonal polynomials on the unit circle. In particular, we will be interested in the special case, where the zeros of the polynomials in question are not located on the boundary of the estimate which occurs in the Eneström–Kakeya theorem. Among other things, we will give characterizations of this case in terms of orthogonal polynomials and present an alternative approach to a well-known characterization due to Hurwitz. Furthermore, we will give some insight how one can apply the main results of this paper in the context of positive Hermitian Toeplitz matrices. [ABSTRACT FROM AUTHOR]

Abstract: An identity by Chaundy and Bullard writes () as a sum of two truncated binomial series. In a paper which appeared in 2008 in Indag. Math. the authors surveyed many aspects of this identity. In the present paper we discuss much earlier occurrences of this identity in works by Hering (1868), de Moivre (1738) and de Montmort (1713). A relationship with Krawtchouk polynomials in work by Greville (1966) is also discussed. [Copyright &y& Elsevier]

Abstract: In a recent paper, Srivastava et al. (2012) [23] introduced and studied some fundamental properties and characteristics of a family of potentially useful incomplete hypergeometric functions. The main object of this paper is to investigate several generating functions for a certain class of incomplete hypergeometric polynomials associated with them. Various (known or new) special cases and consequences of the results presented in this paper are also considered. [Copyright &y& Elsevier]

Abstract: This paper introduces a stochastic scheduling problem. In this problem a directed acyclic graphs (DAG) represents the precedence relations among tasks that workers are scheduled to execute. The question is to find a schedule such that if tasks are assigned to workers according to , the expected time needed to execute all the tasks is minimized. The time needed to execute task by worker is a random variable expressed by a negative exponential distribution with parameter and each task can be executed by more than one worker at a time. In this paper, we will prove that the problem in its general form is NP-hard, but when the DAG width is constant, we will show that the optimum schedules can be found in polynomial time. [Copyright &y& Elsevier]

Abstract: In their paper on the “chasm at depth four”, Agrawal and Vinay have shown that polynomials in variables of degree which admit arithmetic circuits of size also admit arithmetic circuits of depth four and size . This theorem shows that for problems such as arithmetic circuit lower bounds or black-box derandomization of identity testing, the case of depth four circuits is in a certain sense the general case. In this paper we show that smaller depth four circuits can be obtained if we start from polynomial size arithmetic circuits. For instance, we show that if the permanent of matrices has circuits of size polynomial in , then it also has depth 4 circuits of size . If the original circuit uses only integer constants of polynomial size, then the same is true for the resulting depth four circuit. These results have potential applications to lower bounds and deterministic identity testing, in particular for sums of products of sparse univariate polynomials. We also use our techniques to reprove two results on: [–] the existence of nontrivial boolean circuits of constant depth for languages in ; [–] reduction to polylogarithmic depth for arithmetic circuits of polynomial size and polynomially bounded degree. [Copyright &y& Elsevier]

Abstract: Propositions 24 and 25 of Book I of Euclid’s Elements state the fairly obvious fact that if an angle in a triangle is increased without changing the lengths of its arms, then the length of the opposite side increases, and conversely. A satisfactory analogue that holds for orthocentric tetrahedra is established by S. Abu-Saymeh, M. Hajja, M. Hayajneh in a yet unpublished paper, where it is also shown that no reasonable analogue holds for general tetrahedra. In this paper, the result is shown to hold for orthocentric d-simplices for all . The ingredients of the proof consist in finding a suitable parametrization (by a single real number) of the family of orthocentric d-simplices whose edges emanating from a certain vertex have fixed lengths, and in making use of properties of certain polynomials and of Gram and positive definite matrices and their determinants. [Copyright &y& Elsevier]

Abstract: Let be a solvable Lie subalgebra of the Lie algebra ( as a vector space). Let be polynomials in the commuting variables with coefficients in . For matrices , let and letIn this paper, we prove that, for , if one value of the matrix-valued function (the value depends on the product order of the variables) is nilpotent, then, (a) all values of are nilpotent; (b) all values of (again depends on the product order of the variables) are nilpotent, and one value is 0. This generalizes the recent result in and makes his result accurate. The main tool we use in this paper is the representation theory of solvable Lie algebras. [Copyright &y& Elsevier]

Abstract: In the previous paper, the author gave linear inequalities on the coefficients of the Alexander polynomials of alternating knots of genus two, which are best possible as linear inequalities on the coefficients of them. In this paper, we give infinitely many Alexander polynomials which satisfy the linear inequalities, but they are not realized by alternating knots. [Copyright &y& Elsevier]

Abstract This paper is devoted to the mathematical and numerical analysis of a mixed-mixed PDE system describing the stress-assisted diffusion of a solute into an elastic material. The equations of elastostatics are written in mixed form using stress, rotation and displacements, whereas the diffusion equation is also set in a mixed three-field form, solving for the solute concentration, for its gradient, and for the diffusive flux. This setting simplifies the treatment of the nonlinearity in the stress-assisted diffusion term. The analysis of existence and uniqueness of weak solutions to the coupled problem follows as combination of Schauder and Banach fixed-point theorems together with the Babuška–Brezzi and Lax–Milgram theories. Concerning numerical discretization, we propose two families of finite element methods, based on either PEERS or Arnold–Falk–Winther elements for elasticity, and a Raviart–Thomas and piecewise polynomial triplet approximating the mixed diffusion equation. We prove the well-posedness of the discrete problems, and derive optimal error bounds using a Strang inequality. We further confirm the accuracy and performance of our methods through computational tests. [ABSTRACT FROM AUTHOR]

Abstract: The purpose of this paper is to provide new insights on the connections that exist between the discontinuous Galerkin method (DG), the flux reconstruction method (FR) and the recently identified energy stable flux reconstruction method (ESFR) when solving time dependent conservation laws. All these schemes appear to be quite similar and it is important to understand how they are related. In this paper, we first review results on the stability of the discontinuous Galerkin method and extend it to the filtered discontinuous Galerkin method. We then consider the flux reconstruction approach and show its connections with DG. In particular, we show how the Energy Stable Flux Reconstruction method introduced by Vincent et al. is equivalent to a filtered DG method, hence giving a new proof of its stability. Also, it allows the use of the method without having to know the special form of the flux correction polynomials. Finally, we underline some fundamental differences that exist between FR and DG. [Copyright &y& Elsevier]

Abstract: The main object of this paper is to investigate several general families of hypergeometric polynomials and their associated multiple integral representations. By suitably specializing our main results, the corresponding integral representations are deduced for such familiar classes of hypergeometric polynomials as (for example) the generalized Bedient polynomials and the generalized Cesàro polynomials. Each of the integral representations, which are derived in this paper, may be viewed also as a linearization relationship for the product of two different members of the associated family of hypergeometric polynomials. [Copyright &y& Elsevier]

Abstract: Let G be a simple undirected graph with the characteristic polynomial of its Laplacian matrix , . Aleksandar Ilić [A. Ilić, Trees with minimal Laplacian coefficients, Comput. Math. Appl. 59 (2010) 2776–2783] identified n-vertex trees with given matching number q which simultaneously minimize all Laplacian coefficients. In this paper, we give another proof of this result. Generalizing the approach in the above paper, we determine n-vertex trees with given matching number q which have the second minimal Laplacian coefficients. We also identify the n-vertex trees with a perfect matching having the largest and the second largest Laplacian coefficients, respectively. Extremal values on some indices, such as Wiener index, modified hyper-Wiener index, Laplacian-like energy, incidence energy, of n-vertex trees with matching number q are obtained in this paper. [Copyright &y& Elsevier]

Abstract: Eliasi and Taeri [Extension of the Wiener index and Wiener polynomial, Appl. Math. Lett. 21 (2008) 916–921] introduced the notion of -Wiener index of graphs as a generalization of the classical Wiener index and hyper Wiener index of graphs. They obtained some mathematical properties of this new defined topological index. In this paper, the join, Cartesian product, composition, disjunction and symmetric difference of graphs under -Wiener index are computed. By these results most parts of a paper by Sagan et al. [The Wiener polynomial of a graph, Int. J. Quant. Chem. 60 (1996) 959–969] and another paper by Khalifeh et al. [The hyper-Wiener index of graph operations, Comput. Math. Appl. 56 (2008) 1402–1407] are generalized. [Copyright &y& Elsevier]

Abstract: Došlić and Måløy (2010) obtained the extremal 6-cactus chains with respect to the number of matchings and of independent sets. Motivated by the prior paper, in this paper we give recurrences for matching polynomials of ortho-chains and meta-chains, and show that they are the -cactus chains with the most matchings. [Copyright &y& Elsevier]

Abstract: Complex financial instruments with multiple state variables often have no analytical formulas and therefore must be priced by numerical methods, like lattice ones. For pricing convertible bonds and many other interest rate-sensitive products, research has focused on bivariate lattices for models with two state variables: stock price and interest rate. This paper shows that, unfortunately, when the interest rate component allows rates to grow in magnitude without bounds, those lattices generate invalid transition probabilities. As the overwhelming majority of stochastic interest rate models share this property, a solution to the problem becomes important. This paper presents the first bivariate lattice that guarantees valid probabilities. The proposed bivariate lattice grows (super)polynomially in size if the interest rate model allows rates to grow (super)polynomially. Furthermore, we show that any valid constant-degree bivariate lattice must grow superpolynomially in size with log-normal interest rate models, which form a very popular class of interest rate models. Therefore, our bivariate lattice can be said to be optimal. [Copyright &y& Elsevier]

Abstract: This article deals with the equivalence of representations of behaviors of linear differential systems. In general, the behavior of a given linear differential system has many different representations. In this paper we restrict ourselves to kernel and image representations. Two kernel representations are called equivalent if they represent one and the same behavior. For kernel representations defined by polynomial matrices, necessary and sufficient conditions for equivalence are well known. In this paper, we deal with the equivalence of rational representations, i. e. kernel and image representations that are defined in terms of rational matrices. As the first main result of this paper, we will derive a new condition for the equivalence of rational kernel representations of possibly noncontrollable behaviors. Secondly we will derive conditions for the equivalence of rational representations of a given behavior in terms of the polynomial modules generated by the rows of the rational matrices. We will also establish conditions for the equivalence of rational image representations. Finally, we will derive conditions under which a given rational kernel representation is equivalent to a given rational image representation. [ABSTRACT FROM AUTHOR]

Abstract A 2-partition of a digraph D is a partition (V 1 , V 2) of V (D) into two disjoint non-empty sets V 1 and V 2 such that V 1 ∪ V 2 = V (D). A semicomplete digraph is a digraph with no pair of non-adjacent vertices. We consider the complexity of deciding whether a given semicomplete digraph has a 2-partition such that each part of the partition induces a (semicomplete) digraph with some specified property. In [4] and [5] Bang-Jensen, Cohen and Havet determined the complexity of 120 such 2-partition problems for general digraphs. Several of these problems are NP-complete for general digraphs and thus it is natural to ask whether this is still the case for well-structured classes of digraphs, such as semicomplete digraphs. This is the main topic of the paper. More specifically, we consider 2-partition problems where the set of properties are minimum out-, minimum in- or minimum semi-degree. Among other results we prove the following: • For all integers k 1 , k 2 ≥ 1 and k 1 + k 2 ≥ 3 it is NP-complete to decide whether a given digraph D has a 2-partition (V 1 , V 2) such that D 〈 V i 〉 has out-degree at least k i for i = 1 , 2. • For every fixed choice of integers α , k 1 , k 2 ≥ 1 there exists a polynomial algorithm for deciding whether a given digraph of independence number at most α has a 2-partition (V 1 , V 2) such that D 〈 V i 〉 has out-degree at least k i for i = 1 , 2. • For every fixed integer k ≥ 1 there exists a polynomial algorithm for deciding whether a given semicomplete digraph has a 2-partition (V 1 , V 2) such that D 〈 V 1 〉 has out-degree at least one and D 〈 V 2 〉 has in-degree at least k. • It is NP-complete to decide whether a given semicomplete digraph D has a 2-partition (V 1 , V 2) such that D 〈 V i 〉 is a strong tournament. [ABSTRACT FROM AUTHOR]

It is known that the pass move is not an unknotting operation in classical knot theory. In this paper, we prove that the pass move is an unknotting operation in welded knot theory. [ABSTRACT FROM AUTHOR]

Let k , n denote two positive integers and consider the family of the polytopes defined as the convex hull of pairs of the form ( Y , h ) where Y is a 0/1-matrix with k rows, n columns, containing exactly one nonzero coefficient per column, and where h stands for the smallest index of a nonzero row of Y . These polytopes and some variants naturally emerge in formulations of different classical combinatorial optimization problems such as minimum makespan scheduling and minimum span frequency assignment. In this paper, we provide complete formulations for these polytopes and show the associated separation problem can be solved in polynomial time. The complete formulations in the original space of variables generally contain an exponential number of inequalities. Alternative extended compact formulations are also presented. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a novel method for defining a Loop subdivision surface interpolating a set of popularly-used cubic -spline curves. Although any curve on a Loop surface corresponding to a regular edge path is usually a piecewise quartic polynomial curve, it is found that the curve can be reduced to a single cubic -spline curve under certain constraints of the local control vertices. Given a set of cubic -spline curves, it is therefore possible to define a Loop surface interpolating the input curves by enforcing the interpolation constraints. In order to produce a surface of local or global fair effect, an energy-based optimization scheme is used to update the control vertices of the Loop surface subjecting to curve interpolation constraints, and the resulting surface will exactly interpolate the given curves. In addition to curve interpolation, other linear constraints can also be conveniently incorporated. Because both Loop subdivision surfaces and cubic -spline curves are popularly used in engineering applications, the curve interpolation method proposed in this paper offers an attractive and essential modeling tool for computer-aided design. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the evacuation problem in a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36–62] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus, it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a network with a sink such that (i) for each vertex the sum of the transit times of arcs on any path from to takes the same value, and (ii) for each vertex the minimum - cut is determined by the arcs incident to whose tails are reachable from . This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372–2379]. We propose an efficient algorithm for this network problem. [Copyright &y& Elsevier]

Abstract: In the paper [J. Ritt, Prime and composite polynomials, Trans. Amer. Math. Soc. 23 (1922) 51–66] Ritt constructed the theory of functional decompositions of polynomials with complex coefficients. In particular, he described explicitly polynomial solutions of the functional equation . In this paper we study the equation above in the case where are holomorphic functions on compact Riemann surfaces. We also construct a self-contained theory of functional decompositions of rational functions with at most two poles generalizing the Ritt theory. In particular, we give new proofs of the theorems of Ritt and of the theorem of Bilu and Tichy. [Copyright &y& Elsevier]

Abstract: In this paper, we deeply research Lagrange interpolation by polynomial in several variables and give an application of Cayley–Bacharach theorem for it. Particularly on the sufficiently intersected algebraic manifold (or SIAM, for short), we introduce a general method of constructing properly posed set of nodes (or PPSN, for short) for Lagrange interpolation, namely the superposition interpolation process. Then we give an equivalent condition about a PPSN along a SIAM. Further we introduce a relation between the sufficiently intersected algebraic hypersurfaces and H-basis. At the end of this paper, we use the extended Cayley–Bacharach theorem to resolve some problems of Lagrange interpolation along the zero-dimensional and one-dimensional algebraic manifolds. [Copyright &y& Elsevier]

Abstract: In this paper, the qualitative behavior and exact travelling wave solutions of the Zhiber–Shabat equation are studied by using qualitative theory of polynomial differential system. The phase portraits of system are given under different parametric conditions. Some exact travelling wave solutions of the Zhiber–Shabat equation are obtained. The results presented in this paper improve the previous results. [Copyright &y& Elsevier]

Abstract: Multivariate Birkhoff interpolation is the most complex polynomial interpolation problem and people know little about it so far. In this paper, we introduce a special new type of multivariate Birkhoff interpolation and present a Newton paradigm for it. Using the algorithms proposed in this paper, we can construct a Hermite system for any interpolation problem of this type and then obtain a Newton basis for the problem w.r.t. the Hermite system. [Copyright &y& Elsevier]

Abstract: In this paper, we obtain a generalized Lucas polynomial sequence from the lattice paths for the Delannoy numbers by allowing weights on the steps and . These weighted lattice paths lead us to a combinatorial interpretation for such a Lucas polynomial sequence. The concept of Riordan arrays is extensively used throughout this paper. [Copyright &y& Elsevier]

Abstract: This paper provides finite-dimensional convex conditions to construct homogeneous polynomially parameter-dependent Lur’e functions which ensure the stability of nonlinear systems with state-dependent nonlinearities lying in general sectors and which are affected by uncertain parameters belonging to the unit simplex. The proposed conditions are written as linear matrix inequalities parametrized in terms of the degree of the parameter-dependent solution and in terms of the relaxation level of the inequality constraints, based on the algebraic properties of positive matrix polynomials with parameters in the unit simplex. As and increase, progressively less conservative solutions are obtained. The results in the paper include as special cases existing conditions for robust stability and for absolute stability analysis. A convex solution suitable for the design of robust nonlinear state feedback stabilizing controllers is also provided. Numerical examples illustrate the efficiency of the proposed conditions. [Copyright &y& Elsevier]

Abstract: Let be a non-trivial, loopless graph and for each non-trivial subgraph of , let . The graph is 1-balanced if , the maximum among , taken over all non-trivial subgraphs of , is attained when . This quantity is called the fractional arboricity of the graph . The value appears in a paper by Picard and Queyranne and has been studied extensively by Catlin, Grossman, Hobbs and Lai. The quantity measures how much a given graph differs from being 1-balanced. In this paper, we describe a systematic method of modifying a given graph to obtain a 1-balanced graph on the same number of vertices and edges. We obtain this by a sequence of iterations; each iteration re-defining one end-vertex of an edge in the given graph. After each iteration, either the value of the new graph formed is less than that of the graph from the previous iteration or the size of the maximal -achieving subgraph of the new graph is smaller than that of the graph in the previous iteration. We show that our algorithm is polynomial in time complexity. Further ways to decrease the number of iterations are also discussed. [Copyright &y& Elsevier]

Abstract: The paper describes and analyzes a method for computing border bases of a zero-dimensional ideal . The criterion used in the computation involves specific commutation polynomials, and leads to an algorithm and an implementation extending the ones in [B. Mourrain, Ph. Trébuchet, Generalised normal forms and polynomial system solving, in: M. Kauers (Ed.), Proc. Intern. Symp. on Symbolic and Algebraic Computation, ACM Press, New-York, 2005, pp. 253–260]. This general border basis algorithm weakens the monomial ordering requirement for Gröbner bases computations. It is currently the most general setting for representing quotient algebras, embedding into a single formalism Gröbner bases, Macaulay bases and a new representation that does not fit into the previous categories. With this formalism, we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This feature has a huge impact on practical efficiency, as illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper. [Copyright &y& Elsevier]

Abstract: Numerous industrial and research databases include missing values. It is not uncommon to encounter databases that have up to a half of the entries missing, making it very difficult to mine them using data analysis methods that can work only with complete data. A common way of dealing with this problem is to impute (fill-in) the missing values. This paper evaluates how the choice of different imputation methods affects the performance of classifiers that are subsequently used with the imputed data. The experiments here focus on discrete data. This paper studies the effect of missing data imputation using five single imputation methods (a mean method, a Hot deck method, a Naı¨ve-Bayes method, and the latter two methods with a recently proposed imputation framework) and one multiple imputation method (a polytomous regression based method) on classification accuracy for six popular classifiers (RIPPER, C4.5, K-nearest-neighbor, support vector machine with polynomial and RBF kernels, and Naı¨ve-Bayes) on 15 datasets. This experimental study shows that imputation with the tested methods on average improves classification accuracy when compared to classification without imputation. Although the results show that there is no universally best imputation method, Naı¨ve-Bayes imputation is shown to give the best results for the RIPPER classifier for datasets with high amount (i.e., 40% and 50%) of missing data, polytomous regression imputation is shown to be the best for support vector machine classifier with polynomial kernel, and the application of the imputation framework is shown to be superior for the support vector machine with RBF kernel and K-nearest-neighbor. The analysis of the quality of the imputation with respect to varying amounts of missing data (i.e., between 5% and 50%) shows that all imputation methods, except for the mean imputation, improve classification error for data with more than 10% of missing data. Finally, some classifiers such as C4.5 and Naı¨ve-Bayes were found to be missing data resistant, i.e., they can produce accurate classification in the presence of missing data, while other classifiers such as K-nearest-neighbor, SVMs and RIPPER benefit from the imputation. [Copyright &y& Elsevier]

Abstract: In this paper, robust semi-definite programs are considered with the goal of verifying whether a particular LMI relaxation is exact. A procedure is presented showing that verifying exactness amounts to solving a polynomial system. The main contribution of the paper is a new algorithm to compute all isolated solutions of a system of polynomials. Standard techniques in computational algebra, often referred to as Stetter’s method [H.J. Stetter, Numerical Polynomial Algebra, SIAM, 2004], involve the computation of a Gröbner basis of the ideal generated by the polynomials and further require joint eigenvector computations in order to arrive at the zeros of the polynomial system. Our algorithm does neither require structural knowledge on the polynomial system, nor does it rely on the computation of joint eigenvectors. [Copyright &y& Elsevier]

Abstract: For r = (r 1,…, r d ) ∈ ℝ d the mapping τ r :ℤ d →ℤ d given by τ r (a 1,…,a d ) = (a 2, …, a d ,−⌊r 1 a 1+…+ r d a d ⌋) where ⌊·⌋ denotes the floor function, is called a shift radix system if for each a ∈ ℤ d there exists an integer k > 0 with τ r (a) = 0. As shown in Part I of this series of papers, shift radix systems are intimately related to certain well-known notions of number systems like β-expansibns and canonical number systems. After characterization results on shift radix systems in Part II of this series of papers and the thorough investigation of the relations between shift radix systems and canonical number systems in Part III, the present part is devoted to further structural relationships between shift radix systems and β-expansions. In particular we establish the distribution of Pisot polynomials with and without the finiteness property (F). [Copyright &y& Elsevier] k (a) = 0. As shown in Part I of this series of papers, shift radix systems are intimately related to certain well-known notions of number systems like β-expansibns and canonical number systems. After characterization results on shift radix systems in Part II of this series of papers and the thorough investigation of the relations between shift radix systems and canonical number systems in Part III, the present part is devoted to further structural relationships between shift radix systems and β-expansions. In particular we establish the distribution of Pisot polynomials with and without the finiteness property (F). [Copyright &y& Elsevier]

Abstract: In this paper, we present a simple and elegant procedure for the construction of iterative methods for the simultaneous determination of (simple or multiple) zeros of an algebraic polynomial. This procedure is based on the application of a special type of functions, called Weierstrass’ functions, to suitable zero-finding methods for a single zero. For demonstration, using this approach we derive many known iterative methods in a simpler way compared with original derivations, as well as some new methods. Aside from the presented methodology in developing zero-finding methods, the paper offers a short review of simultaneous methods including some historical notes. [Copyright &y& Elsevier]

Abstract: Multistep quasi-Newton methods were introduced by Ford and Moghrabi [1]. They address the problem of the unconstrained minimisation of a function whose gradient and Hessian are denoted by g and G, respectively. These methods generalised the standard construction of quasi-Newton methods and were based on employing interpolatory polynomials to utilise information from more than one previous step. In a series of papers, Ford and Moghrabi [2–5] have developed various techniques for determining the parametrisation of the interpolating curves. In [2], they introduced two-step metric-based methods which determine the set of parameter values required through measuring distances between various pairs of the iterates employed in the current interpolation. One of the most successful methods in [2] was found to be in the “fixed-point” class, in which the parametrisation of the interpolating curve is determined, at each iteration, by reference to distances measured from a fixed iterate. As suggested in [1], multistep quasi-Newton methods can be constructed for any number of steps.In this paper, we therefore extend the previous work by describing the development of some three-step methods which use the “fixed-point” approach and data derived from the latest four iterates. The experimental results provide evidence that the new methods offer a significant improvement in performance when compared with the standard BFGS method and the unit-spaced three-step method, particularly as the dimension of the test problems grows. [Copyright &y& Elsevier]

Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as σ -LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive σ -LFSRs. The search algorithm first constructs the σ -polynomial and then checks the primitiveness of the σ -polynomial, whereas the construction algorithm for the σ -LFSR, first finds a primitive polynomial f ( x ) and then constructs the primitive σ -LFSR from f ( x ) . In this paper, we present some novel results pertaining to the search algorithm for primitive σ -LFSR along with the exhaustive search space complexity of the search algorithm for σ -LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive σ -LFSR. Finally, the number of σ -LFSRs similar to the σ -LFSRs generated by the construction algorithm is provided. [ABSTRACT FROM AUTHOR]

This paper investigates the Bogoyavlenskii–Kadomtsev– Petviashvili equation by using the binary Bell polynomials method and differential constraint technique. Several kinds of more general bilinear representations and Bäklund transformations are presented. At the same time, multiple wave solutions including the kink periodic solitary wave and bright–dark lump wave solutions are constructed. The resonant interactions between two kink solitary waves are investigated and exhibited mathematically and graphically. Lump wave solutions, a kind of rational function localized in all directions of the space, are obtained by the Taylor expansion of the kink periodic solitary wave. Also, we discuss the dynamical behavior of the lump wave solutions and their structures. [ABSTRACT FROM AUTHOR]

For ordinary differential equations of the form P ( y , v , v ′ , … , v ( n ) ) = 0 which are polynomial in the variables v , v ′ , … , v ( n ) two new reduction methods to first-order equations are considered. The reduced equations are of the forms v ′ = Q 1 ( y , v 1 ∕ q ) and v ′ = ( Q 2 ( y , v ) ) 1 ∕ q , where Q 1 and Q 2 are two polynomials of degree p in v 1 ∕ q and v , respectively, whose coefficients depend on y . In contrast to most of the known reduction methods of these types, which use either q = 1 or q = 2 , in this paper the values of the positive integers p , q are not predetermined. A procedure to obtain the possible values of the integers for which a reduction of any of these types may exist is provided. As a consequence, new reductions that cannot be obtained by other known methods may be found. The new methods have been applied to obtain some reductions and, consequently, new solutions for three polynomial ordinary differential equations related to well-known equations in mathematical physics: the Kuramoto–Sivashinsky equation, a generalized Benney equation and a 5 th-order KdV equation. Some pieces of computer algebra code, written in Maple and implementing the underlying algorithms to derive the reductions, are also included. [ABSTRACT FROM AUTHOR]

A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O ( 3 k n k O ( 1 ) ) time: given a graph G and an integer k , can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. (2015) who gave a (nonlinear) 7 . 5 6 k n O ( 1 ) -time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n . [ABSTRACT FROM AUTHOR]

In this paper, we define the generalized ( p, q )-Fibonacci polynomials u n, m ( x ) and generalized ( p, q )-Lucas polynomials v n, m ( x ), and further introduce the generalized Humbert polynomials u n , m ( r ) ( x ) as the convolutions of u n, m ( x ). We give many expressions, expansions, recurrence relations and differential recurrence relations of u n , m ( r ) ( x ) , and study the matrices and determinants related to the polynomials u n, m ( x ), v n, m ( x ) and u n , m ( r ) ( x ) . Finally, we present an algebraic interpretation for the generalized Humbert polynomials u n , m ( r ) ( x ) . It can be found that various well-known polynomials are special cases of u n, m ( x ), v n, m ( x ) or u n , m ( r ) ( x ) . Therefore, by introducing the general polynomials u n, m ( x ), v n, m ( x ) and u n , m ( r ) ( x ) , we have a unified approach to dealing with many special polynomials in the literature. [ABSTRACT FROM AUTHOR]