Search

In this paper, we present a new method for isolating real roots of a bivariate nonlinear system. It is a subdivision method based on analyzing the local geometrical properties of the given system. We propose the concept of opposite monotone system in a box and use it to determine the existence and the uniqueness of a simple real zero of the system in the box. We have implemented our method and the experiments show the effectivity and efficiency of our approach, especially for high degree sparse polynomial systems. This paper is an extended version of the ISSAC'19 conference paper (Cheng and Wen (2019)). [ABSTRACT FROM AUTHOR]

In this paper we introduce methods and algorithms that will help us solve connectivity queries of parameterized semi-algebraic sets. Answering these connectivity queries is applied in the design of robotic structures having similar kinematic properties (e.g. topology of the kinematic-singularity-free space). From these algorithms one also obtain solutions to connectivity queries of a specific parameter which is in turn related to kinematic-singularity free path-planning of a specific manipulator belonging to the family of robots with these properties; i.e. we obtain paths joining two given singularity free configurations lying in the same connected component of the singularity-free space. We prove in the paper how one reduces the problems related to connectivity queries of parameterized semi-algebraic sets to closed and bounded semi-algebraic sets. We then design an algorithm using computer-algebra methods for "solving" positive dimensional polynomial system depending on parameters. The meaning of solving here means partitioning the parameter space into semi-algebraic components over which the number of connected components of the semi-algebraic set defined by the input system is invariant. The complexity of this algorithm is singly exponential in the dimension of the ambient space. The algorithm scales enough to analyze automatically the family of UR-series robots. Finally we provide manual analysis of the family of UR-series robots, proving that the number of connected components of the complementary of kinematic singularity set of a generic UR-robot is eight. [ABSTRACT FROM AUTHOR]

With this paper we present an extension of our recent ISSAC paper about computations of Gröbner(-Shirshov) bases over free associative algebras Z 〈 X 〉. We present all the needed proofs in details, add a part on the direct treatment of the ring Z / m Z as well as new examples and applications to e.g. Iwahori-Hecke algebras. The extension of Gröbner bases concept from polynomial algebras over fields to polynomial rings over rings allows to tackle numerous applications, both of theoretical and of practical importance. Gröbner and Gröbner-Shirshov bases can be defined for various non-commutative and even non-associative algebraic structures. We study the case of associative rings and aim at free algebras over principal ideal rings. We concentrate on the case of commutative coefficient rings without zero divisors (i.e. a domain). Even working over Z allows one to do computations, which can be treated as universal for fields of arbitrary characteristic. By using the systematic approach, we revisit the theory and present the algorithms in the implementable form. We show drastic differences in the behaviour of Gröbner bases between free algebras and algebras, which are close to commutative. Even the process of the formation of critical pairs has to be reengineered, together with implementing the criteria for their quick discarding. We present an implementation of algorithms in the Singular subsystem called Letterplace , which internally uses Letterplace techniques (and Letterplace Gröbner bases), due to La Scala and Levandovskyy. Interesting examples and applications accompany our presentation. [ABSTRACT FROM AUTHOR]

This paper introduces an algorithmic approach to the analysis of bifurcation of limit cycles from the centers of nonlinear continuous differential systems via the averaging method. We develop three algorithms to implement the averaging method. The first algorithm allows one to transform the considered differential systems to the normal form of averaging. Here, we restricted the unperturbed term of the normal form of averaging to be identically zero. The second algorithm is used to derive the computational formulae of the averaged functions at any order. The third algorithm is based on the first two algorithms and determines the exact expressions of the averaged functions for the considered differential systems. The proposed approach is implemented in Maple and its effectiveness is shown by several examples. Moreover, we report some incorrect results in published papers on the averaging method. [ABSTRACT FROM AUTHOR]

Finite dynamical systems are used to model problems from different branches of sciences such as biological networks, computer process, physics, and engineered control systems. An important combinatorial tool for studying limit cycles of a finite dynamical system is dependency graph. In Veliz-Cuba and Laubenbacher (2019) , cycle structure of semilattice networks has completely been characterized when the dependency graph is strongly connected. This characterization is in terms of the loop number of the dependency graph. In this paper, we use the methods developed in Jarrah et al. (2010) ; Veliz-Cuba and Laubenbacher (2019) and we study cycle structure of a semilattice network with an arbitrary dependency graph. We show that the period of any limit cycle divides the loop number. Next, we prove that all periodic points of a semilattice network are fixed points if and only if the loop number of dependency graph is 1. We also find some sufficient conditions under which system has periodic points of any period that divides the loop number. Then, using the same idea as Chen et al. (2020) , we give a reduction process in studying cycle structure of a semilattice networks. Finally, we completely characterized the set of fixed points of a semilattice networks in terms of the set of isotone maps between two certain partially ordered sets. Using this characterization, we give a sharp lower bound for the number of fixed points. The results in this paper apply to certain types of Boolean networks and diffusion models, and in particular extends and recovers some of the results of Chen et al. (2020) ; Jarrah et al. (2010). [ABSTRACT FROM AUTHOR]

Reynolds algebras originated from the celebrated work of Reynolds in 1895 on turbulence theory in fluid mechanics. The subject has attracted broad interests in recent years. This paper constructs free commutative Reynolds algebras, responding to a problem posed by G. Birkhoff in 1961, by applying the method of Gröbner-Shirshov bases. First presenting a free commutative Reynolds algebra as a quotient of the free commutative operated algebra, we then provide a linear basis of the quotient by establishing the composition-diamond lemma for commutative operated algebra and showing that the operated ideal generated by the Reynolds identity possesses a Gröbner-Shirshov basis. [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm that, given a differential operator of order 2, detects if this operator comes from a simpler operator under a non-trivial change of variables. [ABSTRACT FROM AUTHOR]

In this paper, we compute an algebraic decomposition of black-box rings in the generic ring model. More precisely, we explicitly decompose a black-box ring as a direct product of a nilpotent black-box ring and unital local black-box rings, by computing all its primitive idempotents. The algorithm presented in this paper uses quantum subroutines for the computation of the p -power parts of a black-box ring and then classical algorithms for the computation of the corresponding primitive idempotents. As a by-product, we get that the reduction of a black-box ring is also a black-box ring. The first application of this decomposition is an extension of the work of Maurer and Raub (2007) on representation problem in black-box finite fields to the case of reduced p -power black-box rings. Another important application is an IND-CCA 1 attack for any ring homomorphic encryption scheme in the generic ring model. Moreover, when the plaintext space is a finite reduced black-box ring, we present a plaintext-recovery attack based on representation problem in black-box prime fields. In particular, if the ciphertext space has smooth characteristic, the plaintext-recovery attack is effectively computable in the generic ring model. [ABSTRACT FROM AUTHOR]

We lower bound the rank of a tensor by a linear combination of the ranks of three of its unfoldings, using Sylvester's rank inequality. In a similar way, we lower bound the symmetric rank by a linear combination of the symmetric ranks of three unfoldings. Lower bounds on the rank and symmetric rank of tensors are important for finding counterexamples to Comon's conjecture. A real counterexample to Comon's conjecture is a tensor whose real rank and real symmetric rank differ. Previously, only one real counterexample was known, constructed in a paper of Shitov. We divide the construction into three steps. The first step involves linear spaces of binary tensors. The second step considers a linear space of larger decomposable tensors. The third step is to verify a conjecture that lower bounds the symmetric rank, on a tensor of interest. We use the construction to build an order six real tensor whose real rank and real symmetric rank differ. [ABSTRACT FROM AUTHOR]

This paper is concerned with Smith forms of bivariate polynomial matrices. For a bivariate polynomial square matrix with the determinant being the product of two distinct and irreducible univariate polynomials, we prove that it is equivalent to its Smith form. We design an algorithm to reduce this class of bivariate polynomial matrices to their Smith forms, and an example is given to illustrate the algorithm. Furthermore, we extend the above class of matrices to a more general case, and derive a necessary and sufficient condition for the equivalence of a matrix and one of its all possible existing Smith forms. [ABSTRACT FROM AUTHOR]

In 1884 the German mathematician Karl Rohn published a substantial paper (Rohn, 1884) on the properties of quartic surfaces with triple points, proving (among many other things) that the maximum number of lines contained in a quartic monoid surface is 31. In this paper we study in details this class of surfaces. We prove that there exists an open subset A ⊆ P K 1 (K is a characteristic zero field) that parametrizes (up to a projectivity) all the quartic monoid surfaces with 31 lines; then we study the action of PGL (4 , K) on these surfaces, we show that the stabiliser of each of them is a group isomorphic to S 3 except for one surface of the family, whose stabiliser is a group isomorphic to S 3 × C 3. Finally, given two quartic surfaces Q (a) and Q (b) , with a , b ∈ A , we show that Q (a) and Q (b) are projectively equivalent if and only if j (a) = j (b) , where j is the j -function. To get our results, several computational tools, available in computer algebra systems, are used. [ABSTRACT FROM AUTHOR]

In this paper we analyze the computational costs of various operations and algorithms in algebraic number fields using exact arithmetic. Let K be an algebraic number field. In the first half of the paper, we calculate the running time and the size of the output of many operations in K in terms of the size of the input and the parameters of K. We include some earlier results about these, but we go further than them, e.g. we also analyze some R -specific operations in K like less-than comparison. In the second half of the paper, we analyze two algorithms: the Bareiss algorithm, which is an integer-preserving version of the Gaussian elimination, and the LLL algorithm, which is for lattice basis reduction. In both cases, we extend the algorithm from Z n to K n , and give a polynomial upper bound on the running time when the computations in K are performed exactly (as opposed to floating-point approximations). [ABSTRACT FROM AUTHOR]

The groups whose orders factorise into at most four primes have been described (up to isomorphism) in various papers. Given such an order n , this paper exhibits a new explicit and compact determination of the isomorphism types of the groups of order n together with effective algorithms to enumerate, construct, and identify these groups. The algorithms are implemented for the computer algebra system GAP. [ABSTRACT FROM AUTHOR]

Let I = 〈 f 1 , ... , f m 〉 ⊂ Q [ x 1 , ... , x n ] be a zero dimensional radical ideal defined by polynomials given with exact rational coefficients. Assume that we are given approximations { z 1 , ... , z k } ⊂ C n for the common roots { ξ 1 , ... , ξ k } = V (I) ⊆ C n. In this paper we show how to construct and certify the rational entries of Hermite matrices for I from the approximate roots { z 1 , ... , z k }. When I is non-radical, we give methods to construct and certify Hermite matrices for I from the approximate roots. Furthermore, we use signatures of these Hermite matrices to give rational certificates of non-negativity of a given polynomial over a (possibly positive dimensional) real variety, as well as certificates that there is a real root within an ε distance from a given point z ∈ Q n. [ABSTRACT FROM AUTHOR]

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]

This paper addresses the problem of computing valuations of the Dieudonné determinants of matrices over discrete valuation skew fields (DVSFs). Under a reasonable computational model, we propose two algorithms for a class of DVSFs, called split. Our algorithms are extensions of the combinatorial relaxation of Murota (1995) and the matrix expansion by Moriyama and Murota (2013) , both of which are based on combinatorial optimization. While our algorithms require an upper bound on the output, we give an estimation of the bound for skew polynomial matrices and show that the estimation is valid only for skew polynomial matrices. We consider two applications of this problem. The first one is the noncommutative weighted Edmonds' problem (nc-WEP), which is to compute the degree of the Dieudonné determinants of matrices having noncommutative symbols. We show that the presented algorithms reduce the nc-WEP to the unweighted problem in polynomial time. In particular, we show that the nc-WEP over the rational field is solvable in time polynomial in the input bit-length. We also present an application to analyses of degrees of freedom of linear time-varying systems by establishing formulas on the solution spaces of linear differential/difference equations. [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]

In this paper, we focus on extensions of methods for interpolating rational functions from their evaluations, in the context of erroneous evaluations. This problem can be seen both from a computer algebra and a coding theory point of view. In computer algebra, this is a generalization of Simultaneous Rational Function Reconstruction with errors and multiprecision evaluations. From an error correcting codes point of view, this problem is related to the decoding of some algebraic codes such as Reed-Solomon, Derivatives or Multiplicity codes. We give conditions on the inputs of the problem which guarantee the uniqueness of the interpolant. Since we deal with rational functions, some evaluation points may be poles: a first contribution of this work is to correct any error in a scenario with poles and multiplicities that extends (Kaltofen et al., 2020). Our second contribution is to adapt rational function reconstruction for random errors , and provide better conditions for uniqueness using interleaving techniques as in (Guerrini et al., 2021). [ABSTRACT FROM AUTHOR]

As is well-known, the choice of variable ordering while computing cylindrical algebraic decomposition (CAD) has a great effect on the time and memory use of the computation as well as the number of sample points computed. In this paper, we indicate that typical CAD algorithms, if executed with respect to a special kind of variable orderings (called "the perfect elimination orderings", PEO), naturally preserve chordality, which is well compatible with an important (variable) sparsity pattern called "the correlative sparsity". If the associated graph of the polynomial system in question is chordal (resp. , is nearly chordal), then a PEO of the associated graph (resp. , of a minimal chordal completion of the associated graph) can be a better variable ordering for the CAD computation than other naive variable orderings in the sense that it results in a much smaller full set of projection polynomials and thus more efficient computation. A new (m , d) -property of the full set of CAD projection polynomials obtained via a PEO is given, which indicates that when the corresponding perfect elimination tree has a lower height, the full set of projection polynomials also tends to have a smaller "size". Furthermore, combining the lower-tree-height rule with Brown's heuristics, a new procedure is proposed to choose better PEOs for CAD computation. [ABSTRACT FROM AUTHOR]

Many algorithms for determining properties of real algebraic or semi-algebraic sets rely upon the ability to compute smooth points. In this paper, we present a procedure based on computing the critical points of some well-chosen function that guarantees the computation of smooth points in each bounded connected component of a (real) atomic semi-algebraic set. Our technique is intuitive in principal, performs well on previously difficult examples, and is straightforward to implement using existing numerical algebraic geometry software. The practical efficiency of our approach is demonstrated by solving a conjecture on the number of equilibria of the Kuramoto model for the n = 4 case. We also apply our method to design an algorithm to compute the real dimension of algebraic sets, the original motivation for this research. We compare the efficiency of our method to existing methods to compute the real dimension on a benchmark family. [ABSTRACT FROM AUTHOR]

In this paper, we present a q -analogue of the polynomial reduction which was originally developed for hypergeometric terms. Using the q -Gosper representation, we describe the structure of rational functions that are summable when multiplied with a given q -hypergeometric term. The structure theorem enables us to generalize the q -polynomial reduction to the rational case, which can be used in the automatic proof and discovery of q -identities. As applications, several q -analogues of series for π are presented. [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm on vanishing coefficients with arithmetic progressions in the sum of two generalized eta-quotients by using the theory of modular forms, and utilize our algorithm to prove five conjectures on matching coefficients in series expansions of certain q -products and their reciprocals. One of which was provided by Baruah and Das, and the others were found by Schlosser. For instance, we prove that for any n ≥ 0 , λ 12 (10 n + r) = λ 12 ′ (10 n + r − 6) , r ∈ { 7 , 9 } , where the sequences { λ 12 (n) } n ≥ 0 and { λ 12 ′ (n) } n ≥ 0 are defined by ∑ n = 0 ∞ λ 12 (n) q n = 1 R (q) R (q 2) R (q 4) R (q 8) = (∑ n = 0 ∞ λ 12 ′ (n) q n) − 1 , and where R (q) is the Rogers–Ramanujan continued fraction, which has the following celebrated product representation: R (q) = ∏ n = 0 ∞ (1 − q 5 n + 1) (1 − q 5 n + 4) (1 − q 5 n + 2) (1 − q 5 n + 3). Finally, we find that this phenomenon also exists in other infinite q -series expansions. [ABSTRACT FROM AUTHOR]

Suppose that a finite solvable group G acts faithfully, irreducibly and quasi-primitively on a finite vector space V , and G is not metacyclic. Then G always has a regular orbit on V except for a few "small" cases. We completely classify these cases in this paper. [ABSTRACT FROM AUTHOR]

This paper concerns fractional powers of monomial ideals. Rational powers of a monomial ideal generalize the integral closure operation as well as recover the family of symbolic powers. They also highlight many interesting connections to the theory of convex polytopes. We provide multiple algorithms for computing the rational powers of a monomial ideal. We also introduce a mild generalization allowing real powers of monomial ideals. An important result is that given any monomial ideal I , the function taking a real number to the corresponding real power of I is a step function which is left continuous and has rational discontinuity points. [ABSTRACT FROM AUTHOR]

We analyze the bit complexity of an algorithm for the computation of at least one point in each connected component of a smooth real algebraic set. This work is a continuation of our analysis of the hypersurface case (On the bit complexity of finding points in connected components of a smooth real hypersurface , ISSAC'20). In this paper, we extend the analysis to more general cases. Let F = (f 1 , ... , f p) in Z [ X 1 , ... , X n ] p be a sequence of polynomials with V = V (F) ⊂ C n a smooth and equidimensional variety and 〈 F 〉 ⊂ C [ X 1 , ... , X n ] a radical ideal. To compute at least one point in each connected component of V ∩ R n , our starting point is an algorithm by Safey El Din and Schost (Polar varieties and computation of one point in each connected component of a smooth real algebraic set , ISSAC'03). This algorithm uses random changes of variables that are proven to generically ensure certain desirable geometric properties. The cost of the algorithm was given in an algebraic complexity model; here, we analyze the bit complexity and the error probability, and we provide a quantitative analysis of the genericity statements. In particular, we are led to use Lagrange systems to describe polar varieties, as they make it simpler to rely on techniques such as weak transversality and an effective Nullstellensatz. [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]

Modelling the substitution of nucleotides along a phylogenetic tree is usually done by a hidden Markov process. This allows to define a distribution of characters at the leaves of the trees and one might be able to obtain polynomial relationships among the probabilities of different characters. The study of these polynomials and the geometry of the algebraic varieties defined by them can be used to reconstruct phylogenetic trees. However, not all points in these algebraic varieties have biological sense. In this paper, we explore the extent to which adding semi-algebraic conditions arising from the restriction to parameters with statistical meaning can improve existing methods of phylogenetic reconstruction. To this end, our aim is to compute the distance of data points to algebraic varieties and to the stochastic part of these varieties. Computing these distances involves optimization by nonlinear programming algorithms. We use analytical methods to find some of these distances for quartet trees evolving under the Kimura 3-parameter or the Jukes-Cantor models. Numerical algebraic geometry and computational algebra play also a fundamental role in this paper. [ABSTRACT FROM AUTHOR]

Zeilberger's method of creative telescoping is crucial for the computer-generated proofs of combinatorial and special-function identities. Telescopers are linear differential or (q -)recurrence operators computed by algorithms for creative telescoping. Two fundamental problems related to creative telescoping are whether telescopers exist, and how to construct them efficiently when they do. In this paper, we solve the existence problem of telescopers for rational functions in three variables including 18 cases. We reduce the existence problem from the trivariate case to the bivariate case and some related problems. The existence criteria given in this paper enable us to determine the termination of algorithms for creative telescoping with trivariate rational inputs. [ABSTRACT FROM AUTHOR]

This article develops new techniques to classify critical configurations for 3D scene reconstruction from images taken by unknown cameras. Generally, all information can be uniquely recovered if enough images and image points are provided, but there are certain cases where unique recovery is impossible; these are called critical configurations. In this paper, we use an algebraic approach to study the critical configurations for two projective cameras. We show that all critical configurations lie on quadric surfaces, and classify exactly which quadrics constitute a critical configuration. The paper also describes the relation between the different reconstructions when unique reconstruction is impossible. [ABSTRACT FROM AUTHOR]

In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root and we compute its multiplicity structure. More precisely, given a polynomial system f = (f 1 , ... , f N) ∈ C [ x 1 , ... , x n ] N , we present a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of f such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so-called inverse system that describes the multiplicity structure at the root. We use α -theory test to certify the quadratic convergence, and to give bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria. [ABSTRACT FROM AUTHOR]

This paper is concerned with the factorization and equivalence problems of multivariate polynomial matrices. We present some new criteria for the existence of matrix factorizations for a class of multivariate polynomial matrices, and obtain a necessary and sufficient condition for the equivalence of a square polynomial matrix and a diagonal matrix. Based on the constructive proof of the new criteria, we give a factorization algorithm and prove the uniqueness of the factorization. We implement the algorithm on Maple, and two illustrative examples are given to show the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

The second-order cone (SOC) is a class of simple convex cones and optimizing over them can be done more efficiently than with semidefinite programming. It is interesting both in theory and in practice to investigate which convex cones admit a representation using SOCs, given that they have a strong expressive ability. In this paper, we prove constructively that the cone of sums of nonnegative circuits (SONC) admits a SOC representation. Based on this, we give a new algorithm for unconstrained polynomial optimization via SOC programming. We also provide a hybrid numeric-symbolic scheme which combines the numerical procedure with a rounding-projection algorithm to obtain exact nonnegativity certificates. Numerical experiments demonstrate the efficiency of our algorithm for polynomials with fairly large degree and number of variables. [ABSTRACT FROM AUTHOR]

It is well known that every non-degenerate quadratic form admits a decomposition into an orthogonal sum of its anisotropic part and a hyperbolic form. This decomposition is unique up to isometry. In this paper we present an algorithm for constructing an anisotropic part of a given form with coefficients in an arbitrary number field. [ABSTRACT FROM AUTHOR]

Arbitrary-precision integer libraries such as GMP are a critical building block of computer algebra systems. GMP provides state-of-the-art algorithms that are intricate enough to justify formal verification. In this paper, we present a C library that has been formally verified using the Why3 verification platform in about four person-years. This verification deals not only with safety, but with full functional correctness. It has been performed using a mixture of mechanically checked handwritten proofs and automated theorem proving. We have implemented and verified a nontrivial subset of GMP's algorithms, including their optimizations and intricacies. Our library provides the same interface as GMP and is almost as efficient for smaller inputs. We detail our verification methodology and the algorithms we have implemented, and include some benchmarks to compare our library with GMP. [ABSTRACT FROM AUTHOR]

This paper continues a research program on constructive investigations of non-commutative Ore localizations, initiated in our previous papers, and particularly touches the constructiveness of arithmetics within such localizations. Earlier we have introduced monoidal, geometric and rational types of localizations of domains as objects of our studies. Here we extend this classification to rings with zero divisors and consider Ore sets of the mentioned types which are commutative enough: such a set either belongs to a commutative algebra or it is central or its elements commute pairwise. By using the systematic approach we have developed before, we prove that arithmetic within the localization of a commutative polynomial algebra is constructive and give the necessary algorithms. We also address the important question of computing the local closure of ideals which is also known as the desingularization, and present an algorithm for the computation of the symbolic power of a given ideal in a commutative ring. We also provide algorithms to compute local closures for certain non-commutative rings with respect to Ore sets with enough commutativity. [ABSTRACT FROM AUTHOR]

Computing with non-linear polynomial constraints over the real numbers has been an important area within Computer Algebra since the field's inception. More recently, satisfiability for this theory has become an important problem in the SMT-solving community. Inspired by the S C 2 project, this paper combines ideas from both communities to produce a fast "partial solver" for the theory — i.e. a solver that can sometimes decide the satisfiability of formulas, but sometimes fails to make a determination. The partial solver is based on existing "black-box/white-box" simplification algorithms, which this paper extends to allow for the production of UNSAT cores (and stronger simplifications). The production of UNSAT cores is required if the partial solver is to be used in SMT-solving, which is one of the primary motivations for this work. The authors have implemented the partial solver in the Image 1 system, and this paper also reports on experiments based on that implementation. [ABSTRACT FROM AUTHOR]

We show that the product of an n × 3 matrix and a 3 × 3 matrix over a commutative ring can be computed using 6 n + 3 multiplications. For two 3 × 3 matrices this gives us an algorithm using 21 multiplications. This is an improvement with respect to Makarov's algorithm using 22 multiplications (Makarov, 1986). We generalize our result for n × 3 and 3 × 3 matrices and present an algorithm for computing the product of an l × n matrix and an n × m matrix over a commutative ring for odd n using n (l m + l + m − 1) / 2 multiplications if m is odd and using (n (l m + l + m − 1) + l − 1) / 2 multiplications if m is even. Waksman's algorithm (Waksman, 1970) and its generalization to rectangular matrices by Islam (2009) for odd n needs (n − 1) (n 2 + 2 n − 1) / 2 + n 2 multiplications and (n − 1) (l m + l + m − 1) / 2 + l m multiplications respectively, thus for even and odd m less multiplications are required by our algorithm. We also give an algorithm for even n using n (l m + l + m − 1) / 2 multiplications without making use of divisions. Although Waksman's algorithm (Waksman, 1970) and its generalization to rectangular matrices by Islam (2009) use the same number of multiplications our algorithm is an improvement over these algorithms since they make use of some divisions by 2 and we are able to avoid them. Furthermore we present a novelty for matrix multiplication: In this paper we show that some algorithms with special properties that we refer to as weakly bilinear can be used as recursive algorithms. In comparison to bilinear algorithms for small n × n matrices say n < 20 we obtain some better results. From these weakly bilinear algorithms we finally obtain approximate weakly bilinear algorithms. For instance we obtain an approximate weakly bilinear algorithm for 5 × 5 matrices that uses only 87 multiplications. If at all it is possible to compare this algorithm with a bilinear algorithm we obtain a better result with respect to the algorithm in Sedoglavic and Smirnov (2021). [ABSTRACT FROM AUTHOR]

In this paper we study and relate several invariants connected to the solving degree of a polynomial system. This provides a rigorous framework for estimating the complexity of solving a system of polynomial equations via Gröbner bases methods. Our main results include a connection between the solving degree and the last fall degree and one between the degree of regularity and the Castelnuovo–Mumford regularity. [ABSTRACT FROM AUTHOR]

The category XSq of crossed squares is equivalent to the category Cat2 of cat2-groups. Functions for computing with these structures have been developed in the package XMod written using the GAP computational discrete algebra programming language. This paper contains a table listing the numbers ι G 2 of isomorphism classes of cat2-groups on groups G of order at most 30 – a total of 1007 cat2-groups. Secondly, it contains general formulae for ι G 2 in a number of special cases. [ABSTRACT FROM AUTHOR]

A system of n planar point vortices with prescribed real circulations Γ i ≠ 0 may be arranged so that the interaction between vortices causes them all to move with a common velocity. Such solutions are called vortex equilibria , where the required configurations are referred to as stationary or translating depending on whether the velocity is zero or not. The necessary condition, ∑ i < j Γ i Γ j = 0 , for stationary configurations is not sufficient, for general n. The necessary condition, ∑ i Γ i = 0 , for translating configurations is also not sufficient in general. For example, for n ≥ 5 , the set of circulations (2 4 − n , ⋯ , 2 4 − n , 2 (2 − n) n (4 − n) , 1) yields no stationary configurations. For n ≥ 4 , the set of circulations (− 1 , ⋯ , − 1 , n − 3 , 1) yields no translating configurations. In this paper, we generalize such results and find new classes of sets of circulations satisfying the respective necessary conditions, but yielding no vortex equilibria. Let α and m be two independent parameters of natural numbers. The sets of circulations we consider are of the form (x , ... , x , y , 1 , ... , 1) with α 1's, no less than three x = − 2 m , and one y such that ∑ i < j Γ i Γ j = 0 or ∑ i Γ i = 0 holds. Using the minimal polynomial systems defined by O'Neil, we obtain new systems involving only part of the variables in the minimal polynomial systems. Sufficient conditions for no vortex equilibria are derived from them. We explore α and m such that the n -vortex system has no vortex equilibria for general n with the help of a computer algebra system. As a byproduct of the derived systems, they also help to find vortex equilibria for some exceptional n 's where no information is obtained from our sufficient conditions. [ABSTRACT FROM AUTHOR]

Inspired by the classic apolarity theory of symmetric tensors, the aim of this paper is to introduce the Schur apolarity theory, i.e. an apolarity for any irreducible representation of the special linear group S L (V). This allows to describe decompositions of structured tensors whose elementary elements are tensors that represent flags of the vector space V. The main result is the Schur apolarity lemma which is the analogous of the apolarity lemma of symmetric apolarity theory. Eventually we study the rank tensors of low border rank related to specific varieties giving rise also to simple algorithms. [ABSTRACT FROM AUTHOR]

In this paper we present a simple technique to derive certificates of non-realizability for a combinatorial polytope. Our approach uses a variant of the classical algebraic certificates introduced by Bokowski and Sturmfels (1989) , the final polynomials. More specifically we reduce the problem of finding a realization to that of finding a positive point in a variety and try to find a polynomial with positive coefficients in the generating ideal (a positive polynomial), showing that such point does not exist. Many, if not most, of the techniques for proving non-realizability developed in the last three decades can be seen as following this framework, using more or less elaborate ways of constructing such positive polynomials. Our proposal is more straightforward as we simply use linear programming to exhaustively search for such positive polynomials in the ideal restricted to some linear subspace. Somewhat surprisingly, this elementary strategy yields results that are competitive with more elaborate alternatives, and allows us to derive new examples of non-realizable combinatorial polytopes. [ABSTRACT FROM AUTHOR]

In this paper we study systems of autonomous algebraic ODEs in several differential indeterminates. We develop a notion of algebraic dimension of such systems by considering them as algebraic systems. Afterwards we apply differential elimination and analyze the behavior of the dimension in the resulting Thomas decomposition. For such systems of algebraic dimension one, we show that all formal Puiseux series solutions can be approximated up to an arbitrary order by convergent solutions. We show that the existence of Puiseux series and algebraic solutions can be decided algorithmically. Moreover, we present a symbolic algorithm to compute all algebraic solutions. The output can either be represented by triangular systems or by their minimal polynomials. [ABSTRACT FROM AUTHOR]

Signature-based algorithms have become a standard approach for computing Gröbner bases in commutative polynomial rings. However, so far, it was not clear how to extend this concept to the setting of noncommutative polynomials in the free algebra. In this paper, we present a signature-based algorithm for computing Gröbner bases in precisely this setting. The algorithm is an adaptation of Buchberger's algorithm including signatures. We prove that our algorithm correctly enumerates a signature Gröbner basis as well as a Gröbner basis of the module generated by the leading terms of the generators' syzygies, and that it terminates whenever the ideal admits a finite signature Gröbner basis. Additionally, we adapt well-known signature-based criteria eliminating redundant reductions, such as the syzygy criterion, the F5 criterion and the singular criterion, to the case of noncommutative polynomials. We also generalise reconstruction methods from the commutative setting that allow to recover, from partial information about signatures, the coordinates of elements of a Gröbner basis in terms of the input polynomials, as well as a basis of the syzygy module of the generators. We have written a toy implementation of all the algorithms in the Mathematica package OperatorGB and we compare our signature-based algorithm to the classical Buchberger algorithm for noncommutative polynomials. [ABSTRACT FROM AUTHOR]

A staged tree model is a discrete statistical model encoding relationships between events. These models are realised by directed trees with coloured vertices. In algebro-geometric terms, the model consists of points inside a toric variety. For certain trees, called balanced, the model is in fact the intersection of the toric variety and the probability simplex. This gives the model a straightforward description, and has computational advantages. In this paper we show that the class of staged tree models with a toric structure extends far outside of the balanced case, if we allow a change of coordinates. It is an open problem whether all staged tree models have toric structure. [ABSTRACT FROM AUTHOR]

Given an input matrix polynomial whose coefficients are floating point numbers, we consider the problem of finding the nearest matrix polynomial which has rank at most a specified value. This generalizes the problem of finding a nearest matrix polynomial that is algebraically singular with a prescribed lower bound on the dimension given in a previous paper by the authors. In this paper we prove that such lower rank matrices at minimal distance always exist, satisfy regularity conditions, and are all isolated and surrounded by a basin of attraction of non-minimal solutions. In addition, we present an iterative algorithm which, on given input sufficiently close to a rank-at-most matrix, produces that matrix. The algorithm is efficient and is proven to converge quadratically given a sufficiently good starting point. An implementation demonstrates the effectiveness and numerical robustness of our algorithm in practice. [ABSTRACT FROM AUTHOR]