21 results
Search Results
2. Symmetric polynomials in tropical algebra semirings.
- Author
-
Kališnik, Sara and Lešnik, Davorin
- Subjects
- *
SEMIRINGS (Mathematics) , *POLYNOMIALS , *ALGEBRA , *MATHEMATICS , *ABSTRACT algebra , *ALGORITHMS - Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF
3. Ordered spanning sets for quasimodules for Möbius vertex algebras
- Author
-
Buhl, Geoffrey
- Subjects
- *
ALGEBRA , *MATHEMATICAL analysis , *MATHEMATICS , *ALGORITHMS - Abstract
Abstract: Quasimodules for vertex algebras are generalizations of modules for vertex algebras. These new objects arise from a generalization of locality for fields. Quasimodules tie together module theory and twisted module theory, and both twisted and untwisted modules feature Poincaré–Birkhoff–Witt-like spanning sets. This paper generalizes these spanning set results to quasimodules for certain Möbius vertex algebras. In particular this paper presents two spanning sets, one featuring a difference-zero ordering restriction on modes and another featuring a difference-one ordering restriction. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
4. On factorizing codes: Structural properties and related decision problems
- Author
-
De Felice, Clelia
- Subjects
- *
ALGORITHMS , *MACHINE theory , *MATHEMATICS , *ALGEBRA - Abstract
Abstract: The algebraic theory of variable-length codes was initiated by Schützenberger in the 1950s. Almost all the subsequently stated results in this theory are constructive and therefore lead to algorithms. However, there are some basic problems that are still open. For instance, we still do not know how to decide whether a finite code can be embedded in a finite maximal one. We answer this question under additional hypotheses. Precisely, let A be a finite alphabet with , let . Let , let be the number of factors in the prime factorization of n. We give an algorithm to decide whether there exists n, with , and a finite maximal code C which is also factorizing such that . We recall that a factorizing code is a finite maximal code which satisfies the factorization conjecture, proposed by Schützenberger. The above-mentioned statement is a consequence of another result proved in this paper. Namely, given a factorizing code C, it is known that the words in satisfy a property defined by using factorizations of cyclic groups. In this paper we give an algorithm to decide whether a set can be embedded in a set satisfying . Furthermore, we prove that, conversely, for each set satisfying , under additional hypotheses, there exists a factorizing code C such that and, as a consequence, is a code. In this case, C can be constructed starting with prefix/suffix codes and by using two types of operations on codes (composition and substitution). The additional required hypotheses concern the structure of the factorizations involved and are always satisfied when, for each , we have , with . In addition, we prove that there exist sets which satisfy and which are not codes. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
5. Factoring polynomials over global fields II
- Author
-
Méndez Omaña, José and Pohst, Michael E.
- Subjects
- *
POLYNOMIALS , *ALGORITHMS , *MATHEMATICS , *ALGEBRA - Abstract
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]
- Published
- 2005
- Full Text
- View/download PDF
6. A parallel multi-modular algorithm for computing Lagrange resolvents
- Author
-
Rennert, Nicolas
- Subjects
- *
ALGORITHMS , *FOUNDATIONS of arithmetic , *ALGEBRA , *MATHEMATICS - Abstract
The aim of this paper is to exploit the algorithms of paper Experimental Math. 8 (1999) in order to produce a new algebraic method for computing efficiently absolute Lagrange resolvent, a fundamental tool in constructive algebraic Galois theory. This article is composed of two parts.The main idea of the first part is to break up the calculation of absolute resolvent into smaller computations. Since a multi-resolvent is a factor of a resolvent, the whole resolvent may be computed by means of several multi-resolvents.The idea of the second part is that an irreducible polynomial over
Z might be reducible overZ /pZ for certain integerp . So the first part can be applied and then, the Chinese remainder theorem allows to lift up the resolvent overZ . [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF
7. A characterization of finite EI categories with hereditary category algebras
- Author
-
Li, Liping
- Subjects
- *
ALGEBRA , *CATEGORIES (Mathematics) , *ALGORITHMS , *ENDOMORPHISMS , *REPRESENTATIONS of algebras , *MORPHISMS (Mathematics) , *ALGEBRAIC fields , *MATHEMATICS - Abstract
Abstract: In this paper we give an explicit algorithm to construct the ordinary quiver of a finite EI category for which the endomorphism groups of all objects have orders invertible in the field k. We classify all finite EI categories with hereditary category algebras, characterizing them as free EI categories (in a sense which we define) for which all endomorphism groups of objects have invertible orders. Some applications on the representation types of finite EI categories are derived. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
8. Certifying properties of an efficient functional program for computing Gröbner bases
- Author
-
Jorge, J. Santiago, Gulias, Victor M., and Freire, Jose L.
- Subjects
- *
POLYNOMIALS , *ALGEBRA , *ALGORITHMS , *MATHEMATICS - Abstract
Abstract: This paper explores the certification of properties of an efficient functional program in the area of symbolic computation: the calculation of Gröbner basis of a set of multivariate polynomials. Our experience in the development of industrial systems and the certification of some of its relevant properties has led us to use a methodology consisting of functional programs to write the code and the formal verification of fundamental properties. The functional language objective caml has been chosen to implement the program. To verify the properties two approaches are explored: manual proofs that reason directly over the source code of the algorithms, applying techniques like equational reasoning, and theorem provers that are used as a tool to help us certify a model of the real system. The chosen proof assistant is coq. Not only will the certification of the software be taken into consideration but also its efficiency. In addition, we present a graphical interface which eases the use of the program. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
9. Partial actions and partial skew group rings
- Author
-
Ferrero, Miguel and Lazzarin, João
- Subjects
- *
MATHEMATICS , *ALGEBRA , *MATHEMATICAL analysis , *ALGORITHMS - Abstract
Abstract: In this paper we consider partial actions of groups on algebras and partial skew group rings. After some general results we prove two versions of Maschke''s theorem and then we study von Neumann regularity, the prime radical and the Jacobson radical of partial skew group rings. In this way we extend many results which are known for skew group rings. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
10. Almost laura algebras
- Author
-
Smith, David
- Subjects
- *
MATHEMATICAL analysis , *ALGEBRA , *MATHEMATICS , *ALGORITHMS - Abstract
Abstract: In this paper, we propose a generalization for the class of laura algebras, called almost laura. We show that this new class of algebras retains most of the essential features of laura algebras, especially concerning the important role played by the non-semiregular components in their Auslander–Reiten quivers. Also, we study more intensively the left supported almost laura algebras, showing that these are characterized by the presence of a generalized standard, convex and faithful component. Finally, we prove that almost laura algebras behave well with respect to full subcategories, split-by-nilpotent extensions and skew group algebras. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
11. The subword complexity of a class of infinite binary words
- Author
-
Gheorghiciuc, Irina
- Subjects
- *
ALGORITHMS , *ALGEBRA , *MATHEMATICAL analysis , *MATHEMATICS - Abstract
Abstract: The gap function of an infinite word over the binary alphabet gives the distances between consecutive 1''s in this word. In this paper we study infinite binary words whose gap function is injective or “almost injective.” A method for computing the subword complexity of such words is given. A necessary and sufficient condition for a function to be the subword complexity function of a binary word whose gap function is increasing is obtained. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
12. A characterization of the SDPS-hyperplanes of dual polar spaces
- Author
-
De Bruyn, Bart
- Subjects
- *
ALGORITHMS , *ALGEBRA , *MATHEMATICAL analysis , *MATHEMATICS - Abstract
Abstract: In [B. De Bruyn, P. Vandecasteele, Valuations and hyperplanes of dual polar spaces, J. Combin. Theory Ser. A 112 (2005) 194–211], we introduced the class of the SDPS-valuations of dual polar spaces. We showed that these valuations and all their extensions give rise to hyperplanes of dual polar spaces. We call these hyperplanes SDPS-hyperplanes. In the present paper, we show that a hyperplane of a thick dual polar space is an SDPS-hyperplane if and only if every hex not contained in intersects in either a singular hyperplane or the extension of an ovoid. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
13. On a computation of plurigenera of a canonical threefold
- Author
-
Shin, Dong-Kwan
- Subjects
- *
ALGORITHMS , *ALGEBRA , *MATHEMATICS , *FOUNDATIONS of arithmetic - Abstract
Abstract: For a canonical threefold X, we know for a sufficiently large n. When , there are few known results about the integer n. This paper introduces an algorithm for computing plurigenera. Furthermore, when is small, especially 1 and 2, plurigenera are computed. This produces for and for when . Also, for and for with 8 possible exceptional cases when . [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
14. Computation of unirational fields
- Author
-
Gutierrez, Jaime and Sevilla, David
- Subjects
- *
ALGORITHMS , *MATHEMATICS , *MATHEMATICAL programming , *ALGEBRA - Abstract
Abstract: One of the main contributions which Volker Weispfenning made to mathematics is related to Gröbner bases theory. In this paper we present an algorithm for computing all algebraic intermediate subfields in a separably generated unirational field extension (which in particular includes the zero characteristic case). One of the main tools is Gröbner bases theory. Our algorithm also requires computing primitive elements and factoring over algebraic extensions. Moreover, the method can be extended to finitely generated -algebras. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
15. Counterexamples to witness conjectures
- Author
-
van der Hoeven, Joris
- Subjects
- *
ALGEBRA , *MATHEMATICS , *MATHEMATICAL analysis , *ALGORITHMS - Abstract
Abstract: Consider the class of exp–log constants, which is constructed from the integers using the field operations, exponentiation and logarithm. Let be such an exp–log constant and let be its size as an expression. Witness conjectures attempt to give bounds for the number of decimal digits which need to be evaluated in order to test whether equals zero. For this purpose, it is convenient to assume that exponentials are only applied to arguments with absolute values bounded by 1. In that context, several witness conjectures have appeared in the literature and the strongest one states that it is possible to choose . In this paper we give a counterexample to this conjecture. We also extend it so as to cover similar, polynomial witness conjectures. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
16. Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic
- Author
-
Steel, Allan
- Subjects
- *
ALGORITHMS , *ALGEBRA , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
Abstract: Algebraic function fields of positive characteristic are non-perfect fields, and many standard algorithms for solving some fundamental problems in commutative algebra simply do not work over these fields. This paper presents practical algorithms for the first time for (1) computing the primary decomposition of ideals of polynomial rings defined over such fields and (2) factoring arbitrary multivariate polynomials over such fields. Difficulties involving inseparability and the situation where the transcendence degree is greater than one are completely overcome, while the algorithms avoid explicit construction of any extension of the input base field. As a corollary, the problem of computing the primary decomposition of a positive-dimensional ideal over a finite field is also solved. The algorithms perform very effectively in an implementation within the Magma Computer Algebra System, and an analysis of their practical performance is given. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
17. An approximate proximal-extragradient type method for monotone variational inequalities
- Author
-
He, Bing-sheng, Yang, Zhen-hua, and Yuan, Xiao-ming
- Subjects
- *
ALGORITHMS , *MATHEMATICS , *NUMERICAL analysis , *ALGEBRA - Abstract
Abstract: Proximal point algorithms (PPA) are attractive methods for monotone variational inequalities. The approximate versions of PPA are more applicable in practice. A modified approximate proximal point algorithm (APPA) presented by Solodov and Svaiter [Math. Programming, Ser. B 88 (2000) 371–389] relaxes the inexactness criterion significantly. This paper presents an extended version of Solodov–Svaiter''s APPA. Building the direction from current iterate to the new iterate obtained by Solodov–Svaiter''s APPA, the proposed method improves the profit at each iteration by choosing the optimal step length along this direction. In addition, the inexactness restriction is relaxed further. Numerical example indicates the improvement of the proposed method. [Copyright &y& Elsevier]
- Published
- 2004
- Full Text
- View/download PDF
18. Semi-numerical absolute factorization of polynomials with integer coefficients
- Author
-
Rupprecht, David
- Subjects
- *
POLYNOMIALS , *ALGORITHMS , *ALGEBRA , *MATHEMATICS - Abstract
In this paper, we propose a semi-numerical algorithm for computing absolute factorization of multivariate polynomials. It is based on some properties appearing after a generic change of coordinate. Using numerical computation, Galois group action and rational approximation, this method provides an efficient probabilistic algorithm for medium degrees. Two implementations are presented and compared to other algorithms. [Copyright &y& Elsevier]
- Published
- 2004
- Full Text
- View/download PDF
19. A long note on Mulders’ short product
- Author
-
Hanrot, G. and Zimmermann, P.
- Subjects
- *
ALGORITHMS , *POWER series , *ALGEBRA , *MATHEMATICS - Abstract
The short product of two power series is the meaningful part of the product of these objects, i.e.,
∑i+j . Mulders (AAECC 11 (2000) 69) gives an algorithm to compute a short product faster than the full product in the case of Karatsuba’s multiplication (Karatsuba and Ofman, Dokl. Akad. Nauk SSSR 145 (1962) 293). This algorithm works by selecting a cutoff point k and performing a fullk×k product and two(n−k)×(n−k) short products recursively. Mulders also gives a heuristically optimal cutoff pointβn . In this paper, we determine the optimal cutoff point in Mulders’ algorithm. We also give a slightly more general description of Mulders’ method. [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF
20. Effective methods for vanishing cycles of <f>p</f>-cyclic covers of the <f>p</f>-adic line
- Author
-
Lehr, Claus
- Subjects
- *
ALGORITHMS , *GROUP theory , *ALGEBRA , *MATHEMATICS - Abstract
This paper studies the stable reduction of
p -cyclic coversX→PK1 of the projective line overp -adic fields. So far, an algorithm to effectively determine the stable reduction of such covers is only known under additional hypothesis on the branch locus of the cover. Here, rather than restricting the type of cover, we consider the general case and obtain results on the structure of the special fiberXk of the stable reduction ofX . Special attention is payed to making all constructions effective. The central result is a formula computing the number of vanishing cycles onXk . In particular, we give criteria for the special fiber of the stable reduction to be tree-like and for whenX is a Mumford curve. Refining the analysis of vanishing cycles, we describe an algorithm that computes all the components of positivep -rank in the stable model. [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF
21. Bases for projective modules in <f>An(k)</f>
- Author
-
Gago-Vargas, Jesús
- Subjects
- *
ALGEBRA , *ALGORITHMS , *MATHEMATICS - Abstract
Let
An(k) be the Weyl algebra, withk a field of characteristic zero. It is known that every projective finitely generated left module is free or isomorphic to a left ideal. LetM be a left submodule of a free module. In this paper we give an algorithm to compute the projective dimension ofM . IfM is projective andrank(M)≥2 we give a procedure to find a basis. [Copyright &y& Elsevier]- Published
- 2003
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.