Efficient algorithms for the basis of finite Abelian groups
| dc.creator | Karagiorgos, Gregory | |
| dc.creator | Poulakis, Dimitrios | |
| dc.date | 2008-08-25 | |
| dc.date.accessioned | 2026-07-07T09:58:15Z | |
| dc.date.available | 2026-07-07T09:58:15Z | |
| dc.description | Let $G$ be a finite abelian group $G$ with $N$ elements. In this paper we give a O(N) time algorithm for computing a basis of $G$. Furthermore, we obtain an algorithm for computing a basis from a generating system of $G$ with $M$ elements having time complexity $O(M\sum_{p|N} e(p)\lceil p^{1/2}\rceil^{μ(p)})$, where $p$ runs over all the prime divisors of $N$, and $p^{e(p)}$, $μ(p)$ are the exponent and the number of cyclic groups which are direct factors of the $p$-primary component of $G$, respectively. In case where $G$ is a cyclic group having a generating system with $M$ elements, a $O(MN^ε)$ time algorithm for the computation of a basis of $G$ is obtained. | |
| dc.description | 11 pages | |
| dc.identifier | https://arxiv.org/abs/0808.3331 | |
| dc.identifier | http://arxiv.org/abs/0808.3331 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/167648 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.title | Efficient algorithms for the basis of finite Abelian groups | |
| dc.type | text |