26 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. Representing short-term observations of moving objects by a simple visual language
- Author
-
Gottfried, Björn
- Subjects
- *
MATHEMATICS , *MATHEMATICAL analysis , *ALGEBRA , *ALGORITHMS - Abstract
Abstract: In a variety of dynamical systems, formations of motion patterns occur. Observing colonies of animals, for instance, for the scientist it is not only of interest which kinds of formations these animals show, but also how they altogether move around. In order to analyse motion patterns for the purpose of making predictions, to describe the behaviour of systems, or to index databases of moving objects, methods are required for dealing with them. This becomes increasingly important since a number of technologies have been devised which allow objects precisely to get traced. However, the indeterminacy of spatial information in real world environments also requires techniques to approximate reasoning, for example, in order to compensate for small and unimportant distinctions which are due to noisy measurements. As a consequence, precise as well as coarse motion patterns have to be dealt with. A set of 16 atomic motion patterns is proposed. On the one hand, a relation algebra is defined on them. On the other hand, these 16 relations form the basis of a visual language using which motion patterns can easily be dealt with in a diagrammatic way. The relations are coarse but crisp and they allow imprecise knowledge about motion patterns to be dealt with, while their diagrammatic realisation also allow precise patterns to get handled. While almost all approaches consider motion patterns along arbitrary time intervals, this paper in particular focuses on short-term motion patterns as we permanently observe them in our everyday life. The bottom line of the current work, however, is yet more general. While it has been widely argued that it makes sense to use both sentential and diagrammatic representations in order to represent different things in the same system adequately (and hence differently), we argue that it makes even sense to represent the same things differently in order to grasp different aspects of one and the same object of interest from different viewpoints. We demonstrate this by providing both a sentential and a diagrammatic representation for the purpose of grasping different aspects of motion patterns. It shows that both representations complement each other. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
17. Multigrid elliptic equation solver with adaptive mesh refinement
- Author
-
Brown, J. David and Lowe, Lisa L.
- Subjects
- *
EQUATIONS , *ALGORITHMS , *ALGEBRA , *MATHEMATICS - Abstract
Abstract: In this paper, we describe in detail the computational algorithm used by our parallel multigrid elliptic equation solver with adaptive mesh refinement. Our code uses truncation error estimates to adaptively refine the grid as part of the solution process. The presentation includes a discussion of the orders of accuracy that we use for prolongation and restriction operators to ensure second order accurate results and to minimize computational work. Code tests are presented that confirm the overall second order accuracy and demonstrate the savings in computational resources provided by adaptive mesh refinement. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
18. 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
19. 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
20. Seat reservation allowing seat changes
- Author
-
Boyar, Joan, Krarup, Susan, and Nielsen, Morten N.
- Subjects
- *
ALGORITHMS , *ALGEBRA , *MATHEMATICS , *TRAVELERS - Abstract
We consider a variant of the Seat Reservation Problem [J. Boyar, K.S. Larsen, Algorithmica 25 (1999) 403–417] in which seat changes are allowed. We analyze the model using the competitive ratio, the competitive ratio on accommodating sequences [J. Boyar, K.S. Larsen, Algorithmica 25 (1999) 403–417], and the accommodating function [J. Boyar et al., Acta Informatica 40 (2003) 3–35; J. Boyar et al., SIAM J. Comput. 31 (1) (2001) 233–258]. A very promising family of algorithms considered in this paper is Min-Change, which will ask passengers to change seats, only if they would otherwise have been rejected. Min-Change belongs to a large class of conservative algorithms, which all have very high performance guarantees. For instance, if the optimal off-line algorithm can seat all of the passengers,
2/3 of the passengers can be seated on-line using any conservative algorithm allowing only one seat change and3/4 will be seated if two seat changes are allowed. This should be compared to the asymptotic hardness result of1/2 for the best algorithm when no seat changes are allowed [E. Bach et al., J. Sched. 6 (2003) 131–147]. Another interesting algorithm, Modified-Kierstead–Trotter, is proposed and shown to seat all passengers if the optimal off-line algorithm could have accommodated them with only half as many seats. On this type of sequence, Modified-Kierstead–Trotter is strictly better than Min-Change-First-Fit which is strictly better than the Checkerboard algorithm. [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF
21. 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
22. 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
23. 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
24. 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
25. A fast numerical algorithm for the estimation of diffusion model parameters
- Author
-
Voss, Andreas and Voss, Jochen
- Subjects
- *
ALGORITHMS , *ALGEBRA , *MATHEMATICS , *DIFFUSION - Abstract
Abstract: In this paper, we describe a new algorithmic approach for parameter estimation in Ratcliff''s [(1978). A theory of memory retrieval. Psychological Review, 85 (2), 59–108] diffusion model. This problem, especially if inter-trial variabilities of parameters are included in the model, is computationally very expensive; the parameter estimation procedure often takes a long time even with today''s high-speed computers. The algorithm described here makes the calculation of the cumulative distribution functions for predicted process durations computationally much less expensive. This improvement is achieved by solving the Kolmogorov backward equation numerically instead of employing the previously used closed form solution. Additionally, the algorithm can determine the optimum fit for one of the model parameters (the starting point z) directly, thereby reducing the dimension of the parameter search space by one. The resulting method is shown to be notably faster than the standard (closed-form solution) method for parameter estimation. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
26. Forming all pairs in a minimal number of steps
- Author
-
Scheibe, Karl E. and Comfort, W.W.
- Subjects
- *
ALGORITHMS , *NATURAL numbers , *ALGEBRA , *MATHEMATICS - Abstract
Abstract: How can N individuals in a closed space meet and greet each other most efficiently? This paper presents a general solution to this problem—an algorithm or “dance” that will achieve universal pairing in the least possible number of moves or steps. A proof of the suggested algorithm is included, showing that it guarantees that every two participants will greet each other once and only once, and that no procedure with this property can be accomplished with fewer steps. Slightly different procedures are required for the odd and even cases. The algorithm has been applied in classroom settings, and could be applied in any social setting where the objective is to initiate efficiently a sense of group cohesion and common purpose. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.