12 results
Search Results
2. Signature Gröbner bases, bases of syzygies and cofactor reconstruction in the free algebra.
- Author
-
Hofstadler, Clemens and Verron, Thibaut
- Subjects
- *
GROBNER bases , *ALGEBRA , *COMMUTATIVE rings , *NONCOMMUTATIVE algebras , *POLYNOMIALS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
3. Syzygies, constant rank, and beyond.
- Author
-
Härkönen, Marc, Nicklasson, Lisa, and Raiţă, Bogdan
- Subjects
- *
NONLINEAR analysis , *LINEAR systems , *FUNCTIONALS , *ALGEBRA - Abstract
We study linear PDE with constant coefficients. The constant rank condition on a system of linear PDEs with constant coefficients is often used in the theory of compensated compactness. While this is a purely linear algebraic condition, the nonlinear algebra concept of primary decomposition is another important tool for studying such system of PDEs. In this paper we investigate the connection between these two concepts. From the nonlinear analysis point of view, we make some progress in the study of weak lower semicontinuity of integral functionals defined on sequences of PDE constrained fields, when the PDEs do not have constant rank. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
4. Construction of free differential algebras by extending Gröbner-Shirshov bases.
- Author
-
Li, Yunnan and Guo, Li
- Subjects
- *
GROBNER bases , *ALGEBRA , *POLYNOMIALS , *DIFFERENTIAL algebra - Abstract
As a fundamental notion, the free differential algebra on a set is concretely constructed as the polynomial algebra on the differential variables. Such a construction is not known for the more general notion of the free differential algebra on an algebra, from the left adjoint functor of the forgetful functor from differential algebras to algebras, instead of sets. In this paper we show that a generator-relation presentation of a base algebra can be extended to the free differential algebra on this base algebra. More precisely, a Gröbner-Shirshov basis property of the base algebra can be extended to the free differential algebra on this base algebra, allowing a Poincaré-Birkhoff-Witt type basis for these more general free differential algebras. Examples are provided as illustrations. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
5. Geometric Algebra based 2D-DOA Estimation for Non-circular Signals with an Electromagnetic Vector Array.
- Author
-
Wang, Xiangyang, Feng, Yichen, Lv, Xiaolu, and Wang, Rui
- Subjects
- *
ALGEBRA , *STATISTICS , *COMPUTATIONAL complexity , *SIGNAL processing , *VECTOR algebra , *COVARIANCE matrices , *PARAMETER estimation - Abstract
This paper presents two novel methods based on geometric algebra (GA) to estimate two-dimensional (2D) direction-of-arrival (DOA) of non-circular (NC) signals for uniform rectangular array (URA). Traditional methods treat the received NC signals as a long vector which will inevitably lose orthogonality inside each electromagnetic vector sensor (EMVS) and thus miss some information of second-order statistical properties. Furthermore, the computational complexity will also increase. By contrast, the GA-based estimating signal parameter via rotational invariance techniques (ESPRIT) and propagation method (PM) algorithms are proposed to estimation DOA of NC signals. Taking advantage of GA, the relationship among multidimensional signals can be maintained. First, the six components of the EMVS are represented as a multivector in GA space. Then, we construct the GA-based extended covariance matrix to utilize the signal information more completely. The DOA parameters can be estimated through the ESPRIT and PM principle. The proposed GA-based estimation of signal parameter via rotational invariance techniques for NC signals processing (GANC-ESPRIT) can estimate DOA with high estimation accuracy. The proposed GA-based propagation method for NC signals estimation (GANC-PM) uses linear transformation to calculate angle parameters. Our model has much lower memory requirements and less computational burden compared with long vector models. Simulation results demonstrate the robustness and superiority of the proposed GANC-ESPRIT algorithm in terms of angular resolution. Complexity analysis shows that the proposed GANC-PM algorithm performances better with less computations. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
6. Generating functions and counting formulas for spanning trees and forests in hypergraphs.
- Author
-
Liu, Jiuqiang, Zhang, Shenggui, and Yu, Guihai
- Subjects
- *
GENERATING functions , *HYPERGRAPHS , *APPLIED mathematics , *ALGEBRA , *TREE graphs , *MATHEMATICS , *SPANNING trees - Abstract
In this paper, we provide generating functions and counting formulas for spanning trees and spanning forests in hypergraphs in two different ways: (1) We represent spanning trees and spanning forests in hypergraphs through Berezin-Grassmann integrals on Zeon algebra and hyper-Hafnians (orders and signs are not considered); (2) We establish a Hyper-Pfaffian-Cactus Spanning Forest Theorem through Berezin-Grassmann integrals on Grassmann algebra (orders and signs are considered), which generalizes the Hyper-Pfaffian-Cactus Theorem by Abdesselam (2004) [1] and Pfaffian matrix tree theorem by Masbaum and Vaintrob (2002) [15]. • We provide generating functions and counting formulas for spanning trees and spanning forests in hypergraphs through Berezin-Grassmann integrals on Zeon algebra and hyper- Hafnians when orders and signs are not considered. • We establish a Hyper-Pfaffian-Cactus Spanning Forest Theorem through Berezin-Grassmann integrals on Grassmann algebra (orders and signs are considered), which generalizes the Hyper-Pfaffian-Cactus Theorem by Abdesselam [Advances in Applied Mathematics (2004) Vol. 33: 51-70] and Pfaffian matrix tree theorem by Masbaum and Vaintrob [Internat. Math. Res. Notices (2002) Vol. 27: 1397-1426]. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
7. Universal equations for maximal isotropic Grassmannians.
- Author
-
Seynnaeve, Tim and Tairi, Nafie
- Subjects
- *
GRASSMANN manifolds , *EQUATIONS , *BILINEAR forms , *ALGEBRA - Abstract
The isotropic Grassmannian parametrizes isotropic subspaces of a vector space equipped with a quadratic form. In this paper, we show that any maximal isotropic Grassmannian in its Plücker embedding can be defined by pulling back the equations of G r iso (3 , 7) or G r iso (4 , 8). [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
8. Cambrian combinatorics on quiver representations (type [formula omitted]).
- Author
-
Barnard, Emily, Gunawan, Emily, Meehan, Emily, and Schiffler, Ralf
- Subjects
- *
INDECOMPOSABLE modules , *COMBINATORICS , *GEOMETRIC modeling , *ENDOMORPHISMS , *ALGEBRA - Abstract
This paper presents a geometric model of the Auslander–Reiten quiver of a type A quiver together with a stability function for which all indecomposable modules are stable. We also introduce a new Catalan object which we call a maximal almost rigid representation. We show that its endomorphism algebra is a tilted algebra of type A. We define a partial order on the set of maximal almost rigid representations and use our new geometric model to show that this partial order is a Cambrian lattice. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
9. Joint DOA, range and polarization estimation based on geometric algebra for near-field non-circular source with a symmetric MIMO array.
- Author
-
Wang, Xiangyang, Lv, Xiaolu, and Wang, Rui
- Subjects
- *
MIMO radar , *MULTIPLE Signal Classification , *ALGEBRA , *COVARIANCE matrices , *LOCALIZATION (Mathematics) , *COMPUTATIONAL complexity - Abstract
Multiple-input multiple-output (MIMO) radar is a new type of radar with excellent performance in target detection and parameter estimations. The MIMO radar equipped with electromagnetic vector sensors (EMVSs) can record multi-dimensional information of the electromagnetic (EM) signal. Traditional methods based on long vector model cannot preserve orthogonality between the outputs of each component of the EMVS and have high computational complexity. In this paper, a novel geometric algebra (GA)-based localization method is proposed for direction of arrival (DOA), range, and polarization estimation of near-field (NF) non-circular (NC) sources for a symmetric MIMO array. First, the proposed method converts the output of an EMVS into a multi-vector through a GA matrix transformation. Then, the DOA and range parameters can be estimated by searching the one-dimensional (1-D) spectrum based on the GA-based NC rank reduction (GANC-RARE) algorithm. Finally, the polarization can be estimated by employing estimated DOAs and ranges based on the modified GA-based NC multiple signal classification (MGANC-MUSIC) algorithm. The computational complexity analysis demonstrates that our solution improves memory spaces of the covariance matrix and reduces computation efforts of the eigenvalue decomposition (EVD). The simulation results show the superiority and reliability of our proposed method in model error and coherent noise environment. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
10. Branching interval algebra: An almost complete picture.
- Author
-
Bertagnon, A., Gavanelli, M., Passantino, A., Sciavicco, G., and Trevisani, S.
- Subjects
- *
ALGEBRA , *PROBLEM solving , *ARTIFICIAL intelligence , *ALGORITHMS , *BRANCHING processes - Abstract
Branching Algebra is the natural branching-time generalization of Allen's Interval Algebra. As in the linear case, the consistency problem for Branching Algebra is NP-hard. Branching Algebra has many potential applications in different areas of Artificial Intelligence; therefore, being able to efficiently solve classical problems expressed in Branching Algebra is very important. This can be achieved in two steps: first, by identifying expressive enough, yet tractable fragments of the whole algebra, and, second, by using such fragments to boost the performances of a backtracking algorithm for the whole language. In this paper we study the properties of several such fragments, both from the algebraic and the computational point of view, and we give an almost complete picture of tractable and non-tractable fragments of the Branching Algebra. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
11. Friezes, weak friezes, and T-paths.
- Author
-
Çanakçı, İlke and Jørgensen, Peter
- Subjects
- *
COMBINATORICS , *ALGEBRA , *POLYGONS , *GEOMETRY , *TRIANGULATION , *CLUSTER algebras - Abstract
Frieze patterns form a nexus between algebra, combinatorics, and geometry. T -paths with respect to triangulations of surfaces have been used to obtain expansion formulae for cluster variables. This paper will introduce the concepts of weak friezes and T -paths with respect to dissections of polygons. Our main result is that weak friezes are characterised by satisfying an expansion formula which we call the T -path formula. We also show that weak friezes can be glued together, and that the resulting weak frieze is a frieze if and only if so was each of the weak friezes being glued. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
12. On neighbourhood singleton-style consistencies for qualitative spatial and temporal reasoning.
- Author
-
Sioutis, Michael, Paparrizou, Anastasia, and Janhunen, Tomi
- Subjects
- *
PHASE transitions , *NEIGHBORHOODS , *ALGEBRA - Abstract
Given a qualitative constraint network (QCN), a singleton-style consistency focuses on each base relation (atom) of a constraint separately, rather than the entire constraint altogether. This local consistency is essential for tackling fundamental reasoning problems associated with QCN s, such as minimal labeling, but can suffer from redundant constraint checks, especially when checks occur far from where the pruning usually takes place. In this paper, we propose singleton-style consistencies that are applied just on the neighbourhood of a singleton-checked constraint instead of the whole network. We make a theoretical comparison with existing consistencies and consequently prove some properties of the new ones. Further, we propose algorithms to enforce our consistencies, as well as parsimonious variants thereof, that are more efficient in practice than the state of the art. An experimental evaluation with random and structured QCN s of Allen's Interval Algebra in the phase transition region demonstrates the potential of our approach. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.