Search

Considering a multivariate polynomial ideal over a given field as a vector space, we investigate for such an ideal a particular linear basis, a so-called staggered linear basis, which contains a Gröbner basis as well. In this paper, we present a simple and efficient algorithm to compute a staggered linear basis. The new framework is equipped with some novel criteria (including both Buchberger's criteria) to detect superfluous reductions. The proposed algorithm has been implemented in Maple, and we provide an illustrative example to show how it works. Finally, the efficiency of this algorithm compared to the existing methods is discussed via a set of benchmark polynomials. [ABSTRACT FROM AUTHOR]

Holonomic sequences are widely studied as many objects interesting to mathematicians and computer scientists are in this class. In the univariate case, these are the sequences satisfying linear recurrences with polynomial coefficients and also referred to as D -finite sequences. A subclass are C -finite sequences satisfying a linear recurrence with constant coefficients. We investigate the set of sequences which satisfy linear recurrence equations with coefficients that are C -finite sequences and call them C 2 -finite sequences. These sequences are a natural generalization of holonomic sequences. In this paper, we show that C 2 -finite sequences form a difference ring and provide methods to compute in this ring. Furthermore, we provide an analogous construction for D 2 -finite sequences, i.e., sequences satisfying a linear recurrence with holonomic coefficients. We show that these constructions can be iterated and obtain an increasing chain of difference rings. [ABSTRACT FROM AUTHOR]

Approximate polynomial GCD (greatest common divisor) of polynomials with a priori errors on their coefficients, is one of interesting problems in Symbolic-Numeric Computations. In fact, there are many known algorithms: QRGCD, UVGCD, STLN based methods, Fastgcd and so on. The fundamental question of this paper is "which is the best?" from the practical point of view, and subsequently "is there any better way?" by any small extension, any effect by pivoting, and any combination of sub-routines along the algorithms. In this paper, we consider a framework that covers those algorithms and their sub-routines, and makes their sub-routines being interchangeable between the algorithms (i.e. disassembling the algorithms and reassembling their parts). By this framework along with/without small new extensions and a newly adapted refinement sub-routine, we have done many performance tests and found the current answer. In summary, 1) UVGCD is the best way to get smaller tolerance, 2) modified Fastgcd is better for GCD that has one or more clusters of zeros with large multiplicity, and 3) modified ExQRGCD is better for GCD that has no cluster of zeros. [ABSTRACT FROM AUTHOR]

In the companion paper (Adler et al., 2017), we presented a characterization of the linear rank-width of distance-hereditary graphs, from which we derived an algorithm to compute it in polynomial time. In this paper, we investigate structural properties of distance-hereditary graphs based on this characterization. First, we prove that for a fixed tree T , every distance-hereditary graph of sufficiently large linear rank-width contains a vertex-minor isomorphic to T . We extend this property to bigger graph classes, namely, classes of graphs whose prime induced subgraphs have bounded linear rank-width. Here, prime graphs are graphs containing no splits. We conjecture that for every tree T , every graph of sufficiently large linear rank-width contains a vertex-minor isomorphic to T . Our result implies that it is sufficient to prove this conjecture for prime graphs. For a class Φ of graphs closed under taking vertex-minors, a graph G is called a vertex-minor obstruction for Φ if G ∉ Φ but all of its proper vertex-minors are contained in Φ . Secondly, we provide, for each k ⩾ 2 , a set of distance-hereditary graphs that contains all distance-hereditary vertex-minor obstructions for graphs of linear rank-width at most k . Also, we give a simpler way to obtain the known vertex-minor obstructions for graphs of linear rank-width at most 1. [ABSTRACT FROM AUTHOR]

We develop the first algorithm for computing rational solutions of scalar integro-differential equations with polynomial coefficients. It starts by finding the possible poles of a rational solution. Then, bounding the order of each pole and solving an algebraic linear system, we compute the singular part of rational solutions at each possible pole. Finally, using partial fraction decomposition, the polynomial part of rational solutions is obtained by computing polynomial solutions of a non-homogeneous scalar integro-differential equation with a polynomial right-hand side. The paper is illustrated by examples where the computations are done with our Maple implementation. [ABSTRACT FROM AUTHOR]

Mixed trigonometric-polynomials (MTPs) are functions of the form f (x , sin ⁡ x , cos ⁡ x) where f is a trivariate polynomial with rational coefficients, and the argument x ranges over the reals. In this paper, an algorithm "isolating" all the real roots of an MTP is provided and implemented. It automatically divides the real roots into two parts: one consists of finitely many roots in an interval [ μ − , μ + ] while the other consists of countably many roots in R ﹨ [ μ − , μ + ]. For the roots in [ μ − , μ + ] , the algorithm returns isolating intervals and corresponding multiplicities while for those greater than μ + , it returns finitely many mutually disjoint small intervals I i ⊂ [ − π , π ] , integers c i > 0 and multisets of root multiplicity { m j , i } j = 1 c i such that any root > μ + is in the set (∪ i ∪ k ∈ N (I i + 2 k π)) and any interval I i + 2 k π ⊂ (μ + , ∞) contains exactly c i distinct roots with multiplicities m 1 , i ,... , m c i , i , respectively. The efficiency of the algorithm is shown by experiments. The method used to isolate the roots in [ μ − , μ + ] is applicable to any other bounded interval as well. The algorithm takes advantages of the weak Fourier sequence technique and deals with the intervals period-by-period without scaling the coordinate so to keep the length of the sequence short. The new approaches can easily be modified to decide whether there is any root, or whether there are infinitely many roots in unbounded intervals of the form (− ∞ , a) or (a , ∞) with a ∈ Q. [ABSTRACT FROM AUTHOR]

Square-free decomposition is one of fundamental computations for polynomials. However, any conventional algorithm may not work for polynomials with a priori errors on their coefficients. There are mainly two approaches to overcome this empirical situation: approximate polynomial GCD (greatest common divisor) and the nearest singular polynomial. In this paper, we show that these known approaches are not enough for detecting the nearest square-free part (which has no multiple roots) within the given upper bound of perturbations (a priori errors), and we propose a new definition and a new method to detect a square-free part and its decomposition numerically by following a recent framework of approximate polynomial GCD. [ABSTRACT FROM AUTHOR]

The W-characteristic set of a polynomial ideal is the minimal triangular set contained in the reduced lexicographical Gröbner basis of the ideal. A pair (G , C) of polynomial sets is a strong regular characteristic pair if G is a reduced lexicographical Gröbner basis, C is the W-characteristic set of the ideal 〈 G 〉 , the saturated ideal sat (C) of C is equal to 〈 G 〉 , and C is regular. In this paper, we show that for any polynomial ideal I with given generators one can either detect that I is unit, or construct a strong regular characteristic pair (G , C) by computing Gröbner bases such that I ⊆ sat (C) = 〈 G 〉 and sat (C) divides I , so the ideal I can be split into the saturated ideal sat (C) and the quotient ideal I : sat (C). Based on this strategy of splitting by means of quotient and with Gröbner basis and ideal computations, we devise a simple algorithm to decompose an arbitrary polynomial set F into finitely many strong regular characteristic pairs, from which two representations for the zeros of F are obtained: one in terms of strong regular Gröbner bases and the other in terms of regular triangular sets. We present some properties about strong regular characteristic pairs and characteristic decomposition and illustrate the proposed algorithm and its performance by examples and experimental results. [ABSTRACT FROM AUTHOR]

Multiplicative relations between the roots of a polynomial in Q [ x ] have drawn much attention in the field of arithmetic and algebra, while the problem of computing these relations is interesting to researchers in many other fields. In this paper, a sufficient condition is given for a polynomial f ∈ Q [ x ] to have only trivial multiplicative relations between its roots, which is a generalization of those sufficient conditions proposed in Smyth (1986) , Baron et al. (1995) and Dixon (1997). Based on the new condition, a subset E ⊂ Q [ x ] is defined and proved to be generic (i.e. , the set Q [ x ] \ E is very small). We develop an algorithm deciding whether a given polynomial f ∈ Q [ x ] is in E and returning a basis of the lattice consisting of the multiplicative relations between the roots of f whenever f ∈ E. The numerical experiments show that the new algorithm is very efficient for the polynomials in E. A large number of polynomials with much higher degrees, which were intractable before, can be handled successfully with the algorithm. [ABSTRACT FROM AUTHOR]

Powers of (monomial) ideals is a subject that still calls attraction in various ways. In this paper we present a nice presentation of high powers of ideals in a certain class in K [ x 1 , ... , x n ] and K [ [ x 1 , ... , x n ] ]. As an interesting application it leads to an algorithm for computation of the Ratliff–Rush operation on ideals in that class. The Ratliff–Rush operation itself has several applications, for instance, if I is a regular m -primary ideal in a local ring (R , m) , then the Ratliff–Rush associated ideal I ˜ is the unique largest ideal containing I with the same Hilbert polynomial as I. [ABSTRACT FROM AUTHOR]

The XL algorithm is an algorithm for solving overdetermined systems of multivariate polynomial equations, which was initially introduced for quadratic equations. However, the algorithm works for polynomials of any degree, and in this paper we will focus on the performance of XL for polynomials of degree ≥3, where the optimal termination value of the parameter D is still unknown. We prove that the XL algorithm terminates at a certain value of D in the case that the number of equations exceeds the number of variables by 1 or 2. We also give strong evidence that this value is best possible, and we show that this value is smaller than the degree of regularity. Part of our analysis requires proving that ordinary multinomials are strongly unimodal, and this result may be of independent interest. [ABSTRACT FROM AUTHOR]

The ring of covariants of binary form is isomorphic to the ring of regular symmetric bracket polynomials in homogenized roots, which are obtained by symmetrization of regular bracket polynomials. In this paper, we give an algorithm for computing all cyclically standard bracket monomials of arbitrary degree. These monomials form a basis of the vector space of the regular bracket polynomials of a given degree. We also characterize the elemental bracket monomial of degree 2 in terms of graph theory. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm which, given a point and a set of polynomials, constructs a single cylindrical cell containing the point, such that the given polynomials are sign-invariant in the computed cell. To represent a single cylindrical cell, a novel data structure is introduced. The algorithm works with this representation and proceeds incrementally, i.e., first constructing a cell representing the whole real space, and then iterating over the input polynomials, refining the cell at each step to ensure the sign-invariance of the current input polynomial. A merge procedure realizing this refinement is described, and its correctness is proven. The merge procedure is based on McCallum's projection operator, but uses geometric information relative to the input point to reduce the number of projection polynomials computed. The use of McCallum's operator implies the incompleteness of the algorithm in general. However, the algorithm is complete for well-oriented sets of polynomials. Moreover, the incremental approach described in this paper can be easily adapted to a different projection operator. The cell construction algorithm presented in this paper is an alternative to the “model-based” method described by Jovanović and de Moura in a 2012 paper. It generalizes the algorithm described by the first author in a 2013 paper, which could only produce full-dimensional cells, to allow for the construction of cells of arbitrary dimension. While a thorough comparison, whether analytical or empirical, of the new algorithm and the “model-based” approach will be the subject of future work, this paper provides preliminary justification for asserting the superiority of the new method. [ABSTRACT FROM AUTHOR]

In this paper, we first prove that when the associated graph of a polynomial set is chordal, a particular triangular set computed by a general algorithm in top-down style for computing the triangular decomposition of this polynomial set has an associated graph as a subgraph of this chordal graph. Then for Wang's method and a subresultant-based algorithm for triangular decomposition in top-down style and for a subresultant-based algorithm for regular decomposition in top-down style, we prove that all the polynomial sets appearing in the process of triangular decomposition with any of these algorithms have associated graphs as subgraphs of this chordal graph. These theoretical results can be viewed as non-trivial polynomial generalization of existing ones for sparse Gaussian elimination, inspired by which we further propose an algorithm for sparse triangular decomposition in top-down style by making use of the chordal structure of the polynomial set. The effectiveness of the proposed algorithm for triangular decomposition, when the polynomial set is chordal and sparse with respect to the variables, is demonstrated by preliminary experimental results. [ABSTRACT FROM AUTHOR]

We consider the problem of finding the isolated common roots of a set of polynomial functions defining a zero-dimensional ideal I in a ring R of polynomials over C. Normal form algorithms provide an algebraic approach to solve this problem. The framework presented in Telen et al. (2018) uses truncated normal forms (TNFs) to compute the algebra structure of R / I and the solutions of I. This framework allows for the use of much more general bases than the standard monomials for R / I. This is exploited in this paper to introduce the use of two special (non-monomial) types of basis functions with nice properties. This allows us, for instance, to adapt the basis functions to the expected location of the roots of I. We also propose algorithms for efficient computation of TNFs and a generalization of the construction of TNFs in the case of non-generic zero-dimensional systems. The potential of the TNF method and usefulness of the new results are exposed by many experiments. [ABSTRACT FROM AUTHOR]

Two new efficient algorithms for computing greatest common divisors (gcds) of parametric multivariate polynomials over k [ U ] [ X ] are presented. The key idea of the first algorithm is that the gcd of two non-parametric multivariate polynomials can be obtained by dividing their product by the generator of the intersection of two principal ideals generated by the polynomials. The second algorithm is based on another simple insight that the gcd can be extracted using the generator of the ideal quotient of a polynomial with respect to the second polynomial. Since the ideal intersection and ideal quotient in these cases are also principal ideals, their generators can be obtained by computing minimal Gröbner bases of the ideal intersection and ideal quotient, respectively. To avoid introducing new variables which can adversely affect the efficiency, minimal Gröbner bases computations are performed on modules. Both of these constructions generalize to the parametric case as shown in the paper. Comprehensive Gröbner system constructions are used for the parametric ideal intersection and ideal quotient using the Kapur-Sun-Wang's algorithm. It is proved that whether in a minimal comprehensive Gröbner system of a parametric ideal intersection or in that of a parametric ideal quotient, each branch of the specializations corresponds to a principal parametric ideal with a single generator. Using this generator, the parametric gcd of that branch is obtained by division. For the case of more than two parametric polynomials, we can use the above two algorithms to compute gcds recursively, and get an extended algorithm by generalizing the idea of the second algorithm. Algorithms do not suffer from having to apply expensive steps such as ensuring whether parametric polynomials are primitive w.r.t. the main variable as used in both the algorithms proposed by Nagasaka (ISSAC, 2017). The resulting algorithms are not only conceptually simple to understand but are more efficient in practice. The proposed algorithms and both of Nagasaka's algorithms have been implemented in Singular, and their performance is compared on a number of examples. [ABSTRACT FROM AUTHOR]

In an earlier article (Bostan et al., 2017), with Carlos D'Andrea, we described explicit expressions for the coefficients of the order- d polynomial subresultant of (x − α) m and (x − β) n with respect to Bernstein's set of polynomials { (x − α) j (x − β) d − j , 0 ≤ j ≤ d } , for 0 ≤ d < min ⁡ { m , n }. The current paper further develops the study of these structured polynomials and shows that the coefficients of the subresultants of (x − α) m and (x − β) n with respect to the monomial basis can be computed in linear arithmetic complexity, which is faster than for arbitrary polynomials. The result is obtained as a consequence of the amazing though seemingly unnoticed fact that these subresultants are scalar multiples of Jacobi polynomials up to an affine change of variables. [ABSTRACT FROM AUTHOR]

Martin-Löf defined algorithmic randomness, the use of martingales in this definition and several variants were explored by Schnorr, and Lutz introduced resource-bounded randomness. Ambos-Spies et al. have studied resource-bounded randomness under time-bounds and have shown that resource-bounded randomness implies resource-bounded genericity. While the genericity of Ambos-Spies is based on time-bound on finite-extension strategy, the genericity of Dowd, the main topic of this paper, is based on an analogy of the forcing theorem. For a positive integer r , an oracle D is r -generic in the sense of Dowd ( r -Dowd) if the following holds: If a certain formula F on an exponential-sized portion of D is a tautology then a polynomial-sized subfunction of D forces F to be a tautology. Here, r is the number of occurrences of query symbols in F . The relationship between resource-bounded randomness and Dowd-type genericity has been not clear so far. We show that there exists a primitive recursive function t ( n ) with the following property: Every t ( n ) -random set is r -Dowd for each positive integer r . A proof is done by means of constructing resource-bounded martingales. In our former paper, we left an open problem whether there exists a primitive recursive set which is r -Dowd for every positive integer r . In our recent work, we give an affirmative answer to the problem. The main theorem of the present paper gives an alternative proof of the affirmative answer. [ABSTRACT FROM AUTHOR]

In this paper, we develop a novel and effective Euclidean algorithm for Laurent polynomial matrix extension (LPME), which is the key of the construction of perfect reconstruction filter banks (PRFBs). The algorithm gives an approach to the construction of PRFBs other than the dual-chain approach in the paper [5] . The developed algorithm can also be used in the applications where LPME plays a role. [ABSTRACT FROM AUTHOR]

In this paper, a new algorithm is presented for deciding the semi-definiteness of multivariate polynomials with coefficients in a computable ordered field, which admits an effective method of finding an isolating set for every non-zero univariate polynomial. This algorithm is an improvement of the method presented in Ref. [24]. The technique in this paper is to compute triangular decompositions of polynomial systems into regular chains. [ABSTRACT FROM AUTHOR]

In this paper, a symbolic, algorithmic procedure to compute an immersion that recasts a polynomial system into a linear one up to an output injection is proposed. Such a technique is based on computing, through algebraic geometry methods, the set of all the embeddings of the system and on matching the coefficients of these polynomials with the ones of the embeddings of a linear system up to an output injection. The given algorithm is then relaxed to compute an immersion that recasts a polynomial system into a form that is linear up to a finite order and an output injection and to compute an approximation of the immersion. [ABSTRACT FROM AUTHOR]

In this paper we construct HNN-extensions of diassociative algebras and Leibniz algebras and prove that every Leibniz algebra embeds into any of its HNN-extensions. We also prove that every Leibniz algebra with at most countable dimension embeds into a two-generator Leibniz algebra. [ABSTRACT FROM AUTHOR]

Abstract: The oblique extension principle introduced in Chui et al. (2002), Daubechies et al. (2003) [3,5] is a general procedure to construct tight wavelet frames and their associated filter banks. Symmetric tight framelet filter banks with two high-pass filters have been studied in Han and Mo (2004), Mo and Zhuang (in press), Petukhov (2003) [13,16,17]. Tight framelet filter banks with or without symmetry have been constructed in many papers in the literature. This paper is largely motivated by several results in Han (2010), Han and Mo (2004), Petukhov (2003) [11,13,17] to further study tight wavelet frames and their associated filter banks with symmetry and two high-pass filters. Our study not only leads to a simpler algorithm for the construction of tight framelet filter banks with symmetry and two high-pass filters, but also allows us to obtain a wider class of tight wavelet frames with symmetry which are not available in the current literature. The key ingredient in our investigation is a complete characterization of splitting positive semi-definite matrices of Laurent polynomials with symmetry. Several examples are provided to illustrate the results and algorithms in this paper. [Copyright &y& Elsevier]

Abstract: In an earlier paper with Whittle, we showed that there is a tree that displays, up to a natural equivalence, all non-trivial 3-separations of a 3-connected matroid M. The purpose of this paper is to give a polynomial-time algorithm for constructing such a tree for M. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the biorthogonal matrix extension problem with symmetry and its application to construction of biorthogonal multiwavelets. Given a pair of biorthogonal matrices , the biorthogonal matrix extension problem is to find a pair of extension matrices of Laurent polynomials with symmetry such that the submatrix of the first r rows of is the given matrix , respectively; and are biorthogonal satisfying ; and and have the same compatible symmetry. We satisfactorily solve the biorthogonal matrix extension problem with symmetry and provide a step-by-step algorithm for constructing the desired pair of extension matrices from the given pair of matrices . Moreover, our results cover the case for paraunitary matrix extension with symmetry (i.e., the given pair satisfies ). Matrix extension plays an important role in many areas such as wavelet analysis, electronic engineering, system sciences, and so on. As an application of our general results on biorthogonal matrix extension with symmetry, we obtain a satisfactory algorithm for constructing univariate biorthogonal multiwavelets with symmetry for any dilation factor from a given pair of biorthogonal -refinable function vectors with symmetry. Correspondingly, pairs of -dual filter banks with the perfect reconstruction property and with symmetry can be derived by applying our algorithm to a given pair of -dual low-pass filters with symmetry. Several examples of symmetric biorthogonal multiwavelets are provided to illustrate our results in this paper. [Copyright &y& Elsevier]

Abstract: In this paper, we summarize our recent work on establishing, for the first time, an algorithm for the symbolic solution of linear boundary problems. We put our work in the frame of Wen-Tsun Wu’s approach to algorithmic problem solving in analysis, geometry, and logic by mapping the significant aspects of the underlying domains into algebra. We briefly compare this with the lines of thought of Wolfgang Groebner. For building up the necessary tower of domains in a generic and flexible way, we use the machinery of algorithmic functors introduced in our Theorema project. The essence of this concept is explained in the first section of the paper. The main part of the paper then describes our symbolic analysis approach to linear boundary problems, which hinges on three basic principles: (1) Differentiation as well as integration is treated axiomatically, setting up an algebraic data structure that can encode the problem statement (differential equation and boundary conditions) and suitable symbolic expressions for their solution (Green’s operators qua integral operators). (2) Abstract boundary problems are introduced as pairs consisting of an epimorphism on a vector space (abstract differential operator) and a subspace of its dual (abstract boundary conditions). (3) Operator algebras are treated by noncommutative polynomials, modulo Groebner bases for certain relation ideals. [Copyright &y& Elsevier]

Abstract: The Bernstein–Sato polynomial of a hypersurface is an important object with many applications. However, its computation is hard, as a number of open questions and challenges indicate. In this paper we propose a family of algorithms called checkRoot for optimized checking whether a given rational number is a root of Bernstein–Sato polynomial and in the affirmative case, computing its multiplicity. These algorithms are used in the new approach to compute the global or local Bernstein–Sato polynomial and b-function of a holonomic ideal with respect to a weight vector. They can be applied in numerous situations, where a multiple of the Bernstein–Sato polynomial can be established. Namely, a multiple can be obtained by means of embedded resolution, for topologically equivalent singularities or using the formula of AʼCampo and spectral numbers. We also present approaches to the logarithmic comparison problem and the intersection homology D-module. Several applications are presented as well as solutions to some challenges which were intractable with the classical methods. One of the main applications is the computation of a stratification of affine space with the local b-function being constant on each stratum. Notably, the algorithm we propose does not employ primary decomposition. Our results can be also applied for the computation of Bernstein–Sato polynomials for varieties. The examples in the paper have been computed with our implementation of the methods described in Singular:Plural. [Copyright &y& Elsevier]

Abstract: This paper presents a pattern language based on regular expressions that allows the introduction of variables that can be instantiated to portions of the path that matches the expression. The paper will define a simple syntax for the language and its formal semantics. It will also study a modification of finite state automata that, through the introduction of actions on transitions, allows the variables to be instantiated while matching the expression. Finally, the paper will show that the problem of answering queries with variables is inherently harder than simple matching, essentially because, even for fairly simple expressions, the size of the results can be exponential in the size of the graph. The class of expressions and a class of graphs for which query answering is polynomial will be identified, and a processing algorithm for these expressions based on the intersection graph will be provided and analyzed. [Copyright &y& Elsevier]

Abstract: In a recent paper (Cucker et al., 2008 ) we analyzed a numerical algorithm for computing the number of real zeros of a polynomial system. The analysis relied on a condition number for the input system f. In this paper we look at as a random variable derived from imposing a probability measure on the space of polynomial systems and give bounds for both the tail and the expected value . [Copyright &y& Elsevier]

Abstract The growth of tropical geometry has generated significant interest in the tropical semiring in the past decade. However, there are other semirings in tropical algebra that provide more information, such as the symmetrized (max ⁡ , +) , Izhakian's extended and Izhakian–Rowen's supertropical semirings. In this paper we identify in which of these upper-bound semirings we can express symmetric polynomials in terms of elementary ones. We show that in the case of idempotent semirings we can do this precisely when the Frobenius property is satisfied, that in the case of supertropical semirings this is always possible, and that in non-trivial symmetrized semirings this is never possible. Our results allow us to determine the tropical algebra semirings where an analogue of the Fundamental Theorem of Symmetric Polynomials holds and to what extent. [ABSTRACT FROM AUTHOR]

Abstract Triangular decomposition is one of the standard ways to represent the radical of a polynomial ideal. A general algorithm for computing such a decomposition was proposed by A. Szántó. In this paper, we give the first complete bounds for the degrees of the polynomials and the number of components in the output of the algorithm, providing explicit formulas for these bounds. [ABSTRACT FROM AUTHOR]

Abstract: This is a follow-up paper of “Liberating the dimension for function approximation”, where we studied approximation of infinitely variate functions by algorithms that use linear information consisting of finitely many linear functionals. In this paper, we study similar approximation problems, however, now the algorithms can only use standard information consisting of finitely many function values. We assume that the cost of one function value depends on the number of active variables. We focus on polynomial tractability, and occasionally also study weak tractability. We present non-constructive and constructive results. Non-constructive results are based on known relations between linear and standard information for finitely variate functions, whereas constructive results are based on Smolyak’s construction generalized to the case of infinitely variate functions. Surprisingly, for many cases, the results for standard information are roughly the same as for linear information. [Copyright &y& Elsevier]

Abstract: “Clarithmetic” is a generic name for formal number theories similar to Peano arithmetic, but based on computability logic instead of the more traditional classical or intuitionistic logics. Formulas of clarithmetical theories represent interactive computational problems, and their “truth” is understood as existence of an algorithmic solution. Imposing various complexity constraints on such solutions yields various versions of clarithmetic. The present paper introduces a system of clarithmetic for polynomial time computability, which is shown to be sound and complete. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a polynomial time solution and, furthermore, such a solution can be efficiently extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a polynomial time solution is represented by some theorem T of the system. The paper is written in a semitutorial style and targets readers with no prior familiarity with computability logic. [Copyright &y& Elsevier]

Abstract: Bisimulation equivalence is decidable in polynomial time for both sequential and commutative normed context-free processes, known as BPA and BPP, respectively. Despite apparent similarity between the two classes, different algorithmic techniques were used in each case. We provide one polynomial-time algorithm that works in a superclass of both normed BPA and BPP. It is derived in the setting of partially-commutative context-free processes, a new process class introduced in the paper. It subsumes both BPA and BPP and seems to be of independent interest. Expressibility issue of the new class, in comparison with the normed PA class, is also tackled in the paper. [Copyright &y& Elsevier]

In this paper an implicit characterization of the complexity classes k - EXP and k - FEXP , for k ≥ 0 , is given, by a type assignment system for a stratified λ -calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic ( ELL ), and the hierarchy of complexity classes k - EXP is characterized by a hierarchy of types. [ABSTRACT FROM AUTHOR]

Abstract: This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires time and space, where is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires time and space, and the presented approximation scheme requires time and space, where ϵ is the given approximation parameter and M is the length of the longest path in an optimal solution. [ABSTRACT FROM AUTHOR]

Abstract: This is the continuation of Montes’ paper “On the canonical discussion of polynomial systems with parameters”. In this paper, we define the Minimal Canonical Comprehensive Gröbner System of a parametric ideal and fix under which hypothesis it exists and is computable. An algorithm to obtain a canonical description of the segments of the Minimal Canonical CGS is given, thus completing the whole MCCGS algorithm (implemented in Maple and Singular). We show its high utility for applications, such as automatic theorem proving and discovering, and compare it with other existing methods. A way to detect a counterexample to deny its existence is outlined, although the high number of tests done give evidence of the existence of the Minimal Canonical CGS. [Copyright &y& Elsevier]

Abstract: In this paper we describe software for an efficient factorization of polynomials over global fields . The algorithm for function fields was recently incorporated into our system KANT. The method is based on a generic algorithm developed by the second author in an earlier paper in this journal. Besides algorithmic aspects not contained in that paper we give details about the current implementation and about some complexity issues as well as a few illustrative examples. Also, a generalization of the application of LLL reduction for factoring polynomials over arbitrary global fields is developed. [Copyright &y& Elsevier]

In this paper, we study the desingularization problem in the first q -Weyl algebra. We give an order bound for desingularized operators, and thus derive an algorithm for computing desingularized operators in the first q -Weyl algebra. Moreover, an algorithm is presented for computing a generating set of the first q -Weyl closure of a given q -difference operator. As an application, we certify that several instances of the colored Jones polynomial are Laurent polynomial sequences by computing the corresponding desingularized operator. [ABSTRACT FROM AUTHOR]

The goal of the present paper is to extend the mitosis algorithm, originally developed by Ezra Miller and Allen Knutson for the case of Schubert polynomials, to the case of Grothendieck polynomials. In addition we will also use this algorithm to construct a short combinatorial proof of Fomin–Kirillov's formula for the coefficients of Grothendieck polynomials. [ABSTRACT FROM AUTHOR]

The generalised colouring numbers col r ( G ) and wcol r ( G ) were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have since then found important theoretical and algorithmic applications. In this paper, we dramatically improve upon the known upper bounds for generalised colouring numbers for graphs excluding a fixed minor, from the exponential bounds of Grohe et al. to a linear bound for the r -colouring number col r and a polynomial bound for the weak r -colouring number wcol r . In particular, we show that if G excludes K t as a minor, for some fixed t ≥ 4 , then col r ( G ) ≤ t − 1 2 ( 2 r + 1 ) and wcol r ( G ) ≤ r + t − 2 t − 2 ( t − 3 ) ( 2 r + 1 ) ∈ O ( r t − 1 ) . In the case of graphs G of bounded genus g , we improve the bounds to col r ( G ) ≤ ( 2 g + 3 ) ( 2 r + 1 ) (and even col r ( G ) ≤ 5 r + 1 if g = 0 , i.e. if G is planar) and wcol r ( G ) ≤ ( 2 g + r + 2 2 ) ( 2 r + 1 ) . [ABSTRACT FROM AUTHOR]

The main objective of this paper is to find algorithms accompanied by explicit error bounds for phase retrieval from noisy magnitudes of frame coefficients when the underlying frame has a low redundancy. We achieve these goals with frames consisting of N = 6 d − 3 vectors spanning a d -dimensional complex Hilbert space. The two algorithms we use, phase propagation or the kernel method, are polynomial time in the dimension d . To ensure a successful approximate recovery, we assume that the noise is sufficiently small compared to the squared norm of the vector to be recovered. In this regime, we derive an explicit error bound that is inverse proportional to the signal-to-noise ratio, with a constant of proportionality that depends only on the dimension d . Properties of the reproducing kernel space of complex polynomials and of trigonometric polynomials are central in our error estimates. [ABSTRACT FROM AUTHOR]

This paper studies exact algorithms for the Maximum Induced Matching problem, in which an n -vertex graph is given and we are asked to find a set of maximum number of edges in the graph such that no pair of edges in the set have a common endpoint or are adjacent by another edge. This problem has applications in many different areas. We give several structural properties of the problem and show that the problem can be solved in O ⁎ ( 1.4231 n ) time and polynomial space or O ⁎ ( 1.3752 n ) time and exponential space. [ABSTRACT FROM AUTHOR]

We study a decision problem, that emerges from the area of spatial reasoning. This decision problem concerns the description of polylines in the plane by means of their double-cross matrix . In such a matrix, the relative position of each pair of line segments in a polyline is expressed by means of a 4-tuple over { − , 0 , + } . However, not any such matrix of 4-tuples is the double-cross matrix of a polyline. This gives rise to the decision problem: given a matrix of such 4-tuples, decide whether it is the double-cross matrix of a polyline. This problem is decidable, but it is NP -hard. In this paper, we give polynomial-time algorithms for the cases where consecutive line segments in a polyline make angles that are multiples of 90° or 45° and for the case where, apart from an input matrix, the successive angles of a polyline are also given as input. [ABSTRACT FROM AUTHOR]

The GVW algorithm provides a new framework for computing Gröbner bases efficiently. If the input system is not homogeneous, some J-pairs with larger signatures but lower degrees may be rejected by GVW's criteria, and instead, GVW has to compute some J-pairs with smaller signatures but higher degrees. Consequently, degrees of polynomials appearing during the computations may unnecessarily grow up higher, and hence, the total computations become more expensive. This phenomenon happens more frequently when the coefficient field is a finite field and the field polynomials are involved in the computations. In this paper, a variant of the GVW algorithm, called M-GVW, is proposed. The concept of mutant pairs is introduced to overcome the inconveniences brought by inhomogeneous inputs. In aspects of implementations, to obtain efficient implementations of GVW/M-GVW over boolean polynomial rings, we take advantages of the famous library M4RI. We propose a new rotating swap method of adapting efficient routines in M4RI to deal with the one-direction reductions in GVW/M-GVW. Our implementations are tested with many examples from Boolean polynomial rings, and the timings show M-GVW usually performs much better than the original GVW algorithm if mutant pairs are found. [ABSTRACT FROM AUTHOR]

In this paper, we present a new method for computing bounded-degree factors of lacunary multivariate polynomials. In particular for polynomials over number fields, we give a new algorithm that takes as input a multivariate polynomial f in lacunary representation and a degree bound d and computes the irreducible factors of degree at most d of f in time polynomial in the lacunary size of f and in d . Our algorithm, which is valid for any field of zero characteristic, is based on a new gap theorem that enables reducing the problem to several instances of (a) the univariate case and (b) low-degree multivariate factorization. The reduction algorithms we propose are elementary in that they only manipulate the exponent vectors of the input polynomial. The proof of correctness and the complexity bounds rely on the Newton polytope of the polynomial, where the underlying valued field consists of Puiseux series in a single variable. [ABSTRACT FROM AUTHOR]

In this paper, we present a new algorithm and an experimental implementation for factoring elements in the polynomial n th Weyl algebra, the polynomial n th shift algebra, and Z n -graded polynomials in the n th q _ -Weyl algebra. The most unexpected result is that this noncommutative problem of factoring partial differential operators can be approached effectively by reducing it to the problem of solving systems of polynomial equations over a commutative ring. In the case where a given polynomial is Z n -graded, we can reduce the problem completely to factoring an element in a commutative multivariate polynomial ring. The implementation in Singular is effective on a broad range of polynomials and increases the ability of computer algebra systems to address this important problem. We compare the performance and output of our algorithm with other implementations in major computer algebra systems on nontrivial examples. [ABSTRACT FROM AUTHOR]

Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schönhage in 1982. The main drawbacks of Pan's method are that it is quite involved 2 2 In Victor Pan's own words: “Our algorithms are quite involved, and their implementation would require a non-trivial work, incorporating numerous known implementation techniques and tricks”. In fact, we are not aware of any implementation of Pan's method. and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. In this paper, we resolve this discrepancy by introducing a hybrid of the Descartes method and Newton iteration, denoted A New Dsc , which is simpler than Pan's method, but achieves a run-time comparable to it. Our algorithm computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. A New Dsc can also be used to only isolate the roots in a given interval and to refine the isolating intervals to an arbitrary small size; it achieves near optimal complexity for the latter task. [ABSTRACT FROM AUTHOR]