Solving a polynomial system, or computing an associated Gröbner basis, has been a fundamental task in computational algebra. However, it is also known for its notorious doubly exponential time complexity in the number of variables in the worst case. This paper is the first to address the learning of Gröbner basis computation with Transformers. The training requires many pairs of a polynomial system and the associated Gröbner basis, raising two novel algebraic problems: random generation of Gröbner bases and transforming them into non-Gröbner ones, termed as backward Gröbner problem. We resolve these problems with 0-dimensional radical ideals, the ideals appearing in various applications. Further, we propose a hybrid input embedding to handle coefficient tokens with continuity bias and avoid the growth of the vocabulary set. The experiments show that our dataset generation method is a few orders of magnitude faster than a naive approach, overcoming a crucial challenge in learning to compute Gröbner bases, and Gröbner computation is learnable in a particular class.

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K. Because of the use of the valuation, the theory of tropical Gröbner bases has proved to provide settings for computations over polynomial rings over a p-adic field that are more stable than that of classical Gröbner bases. In this article, we investigate how the FGLM change of ordering algorithm can be adapted to the tropical setting.

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K . Because of the use of the valuation, the theory of tropical Gröbner bases has proved to provide settings for computations over polynomial rings over a p -adic field that are more stable than that of classical Gröbner bases. Beforehand, these strategies were only available for homogeneous polynomials. In this article, we extend the F5 strategy to a new definition of tropical Gröbner bases in an affine setting. We provide numerical examples to illustrate time-complexity and p -adic stability of this tropical F5 algorithm. We also illustrate its merits as a first step before an FGLM algorithm to compute (classical) lex bases over p -adics.

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K. While generalizing the classical theory of Gröbner bases, it is not clear how modern algorithms for computing Gröbner bases can be adapted to the tropical case. Among them, one of the most efficient is the celebrated F5 Algorithm of Faugère.

Somewhat homomorphic encryption is public key encryption supporting a limited number of additions and multiplications on encrypted data. This encryption gives a powerful tool in performing meaningful computations with protecting data confidentiality, whose property is suitable mainly in cloud computing. In this paper, we focus on the scheme proposed by Brakerski and Vaikuntanathan, and present two types of packed ciphertexts in order to improve performance and reduce size of the encrypted data. One type of our packed ciphertexts is based on the message encoding technique proposed by Lauter, Naehrig and Vaikuntanathan. While their technique empowers efficient secure computation of sums and products over the integers, our second type of packed ciphertexts enables efficient secure computation of more complex functionalities such as multiple inner products and multiple Hamming distances. We apply our packing method to construct several protocols for secure biometric authentication and secure pattern matching computations. Our implementation shows that our method gives faster performance than the state-of-the-art work in such applications. Copyright © 2015 John Wiley & Sons, Ltd.

This paper constructs an algebraic solution approach to the algebraic Riccati equation, an important equation in signal processing and control system design. Key features of the proposed approach are the exploitation of useful structures inherent in the problem and the avoidance of Gröbner basis computation by generic algorithms. The approach extends the algebraic approach to polynomial spectral factorization by means of the Sum of Roots. The approach further finds an effective symbolic expression of the eigenvector of the associated Hamiltonian matrix in a simple way. An example is presented to demonstrate the proposed algorithm.

In this article, we present new results about the computation of a general shape of a triangular basis generating the splitting ideal of an irreducible polynomial given with the permutation representation of its Galois group G. We provide some theoretical results and a new general algorithm based on the study of the non redundant bases of permutation groups. These new results deeply increase the efficiency of the computation of the splitting field of a polynomial.

This paper attempts to establish a new framework of symbolic optimization of algebraic functions that is relevant to possibly a wide variety of practical application areas. The crucial aspects of the framework are (i) the suitable use of algebraic methods coupled with the discovery and exploitation of structural properties of the problem in the conversion process into the framework, and (ii) the feasibility of algebraic methods when performing the optimization. As an example an algebraic approach is developed for the discrete-time polynomial spectral factorization problem that illustrates the significance and relevance of the proposed framework. A numerical example of a particular control problem is also included to demonstrate the development.

Let f be a univariate monic integral polynomial of degree n and let (α1, ..., αn) be an n-tuple of its roots in an algebraic closure Q of Q. Obtaining an algebraic representation of the splitting field Q(α1, ..., αn) of f is a question of first importance in effective Galois theory. For instance, it allows us to manipulate symbolically the roots of f. In this paper, we propose a new method based on multi-modular strategy. Actually, we provide algorithms for this task which return a triangular set encoding the splitting ideal of f. We examine the ability/practicality of the method by experiments on a real computer and study its complexity.

This paper proposes an algebraic approach for parametric optimization which can be utilized for various problems in signal processing and control.The approach exploits the relationship between the sum of roots and polynomial spectral factorization and solves parametric polynomial spectral factorization by means of the sum of roots and the theory of Gröbner basis. This enables us to express quantities such as the optimal cost in terms of parameters and the sum of roots.Furthermore an optimization method over parameters is suggested that makes use of the results from parametric polynomial spectral factorization and also employs quantifier elimination.The proposed approach is demonstrated on a numerical example of a particular control problem.

In this paper we present a method to compute or estimate the sum of roots with positive real parts (SORPRP) of a polynomial, which is related to a certain index of "average" stability in optimal control, without computing explicit numerical values of the roots. The method is based on symbolic and algebraic computations and enables us to deal with polynomials with parametric coefficients for their SORPRP. This leads to provide a novel systematic method to achieve optimal regulator design in control by combining the method with quantifier elimination. We also report some experimental result for a typical class of plants and confirm the effectiveness of the proposed method.

We deal with systems of algebraic equations with parametric exponents. As the first step for solving such systems,we consider the most simple cases, univariate case and 0-dimensional case, and give a concrete method for computing Gröbner bases. From studies on such cases, we derive a simple formulation and basic notions which will be helpful to deal with more complicated cases.

Polynomial factorization plays a significant role in computational mathematics and its application to engineering, since it forms a fundamental part of algorithms for higher algebraic computations. Multivariate polynomial factorization over finite fields is very important for computations of mathematical object over positive characteristic fields, which will help mathematical studies in various area. For example, primary ideal decomposition over finite fields is very useful for study of pure mathematics (algebraic geometry over positive characteristic fields) and also for study of coding theory (design of algebraic geometric codes). To make primary decomposition efficient, practical method of multivariate polynomial factorization and its implementation are essential. (This is the authors' motivation for this study. )Since, multivariate factorization over finite fields can be reduced efficiently to bivariate factorization, we focus on bivariate factorization over small finite fields here, and we propose a practically efficient combination of two methods: one is the well-known method by trial division and the other is a new polynomial-time method.As to polynomial factorization, many of computer algebra systems employ trial-division type algorithms which are non polynomial-time but efficient in many cases. However, as polynomial-time algorithms work well in the worst cases, good combination with practical algorithms should be very useful to improve the performance of the computer algebra system, provided that we have their practical implementation and we know their good usages. Moreover, if we can incorporate those with certain knowledge on the input, (we may call these heuristics), their practicality shall be much improved. In this paper we propose a polynomial-time algorithm for bivariate factorization over finite fields, which can be implemented efficiently and in which some heuristics can be incorporated. The new algorithm is obtained by reviewing existing algorithms from the ideal theoretical point of view, and based on the change of ordering algorithm of zero-dimensional Gröbner basis [6, 17].As to practical implementation of bivariate factorization, finding evaluation points and Hensel lifting are very important. When we factorize a polynomial over a small finite field, we often have to extend the ground field because of shortage of evaluation points. However, if the extension field is small enough, a primitive root representation of the field can reduce the cost of field operations over the extension field. Under this situation we implement Hensel lifting and trial division, and we examine its performance by various benchmark problems. We also implement the new polynomial-time algorithm and we show its advantage for hard-to-factor polynomials.

We present an efficient algorithm for testing whether a given integral polynomial has two distinct roots a, B such that fflp is a root of unity.The test is based on results obtained by investigation of the structure of the splitting field of the polynomial.By this investigate ion, we found also an improved bound for the least common multiple of the orders of roots of unity appearing as quotients of distinct roots.

Article Free Access Share on On Hensel construction of eigenvalues and eigenvectors of matrices with polynomial entries Authors: Kazuhiro Yokoyama View Profile , Taku Takeshima View Profile Authors Info & Claims ISSAC '93: Proceedings of the 1993 international symposium on Symbolic and algebraic computationAugust 1993 Pages 218–224https://doi.org/10.1145/164081.164130Published:01 August 1993Publication History 2citation224DownloadsMetricsTotal Citations2Total Downloads224Last 12 Months10Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Landau and Miller presented a method for determining the solvability of a monic irreducible polynomial over integers in polynomial time. In their method, a series of polynomials is constructed so that the original problem is reduced to determining the solvability of new polynomials. Here, we present an improved method for finding such a series of polynomials efficiently. More precisely, we introduce a new notion on a series of blocks in the set of all roots of the original polynomial under the action of its Galois group, and then present an efficient method for finding such a series of blocks by modifying Landau and Miller's method for finding minimal imprimitive blocks.

For a problem how to find an extension field over which we can obtain an absolutely irreducible factor, Kaltofen gave an answer in 1983 and explicitly in 1985 by employing analytic argument for showing his answer, and Chistov and Grigor'ev also gave the same answer in 1983 by algebraic arguments. Here, we give an alternative proof for Kaltofen's answer in algebraic way, independently to Chistov and Grigor'ev, and by the benefit of new way, we also give several extensions of his answer and properties of absolutely irreducible factors. We also discuss usage of our results for actual computation of absolutely irreducible factors. Here we restrict ourselves to bi-variate polynomials with integer (or rational) coefficients. First we state Kaltofen's answer.