Efficient algorithms for the basis of finite Abelian groups

Details Efficient algorithms for the basis of finite Abelian groups Efficient algorithms for the basis of finite Abelian groups

2008-08-25

arxiv.org/abs/0808.3331v1

Computer Science

Data Structures and Algorithms

11 pages

Scientific paper

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^{\mu(p)})$, where $p$ runs over all the prime divisors of $N$, and $p^{e(p)}$, $\mu(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^{\epsilon})$ time algorithm for the computation of a basis of $G$ is obtained.

Affiliated with

Also associated with

No associations

Rating

Efficient algorithms for the basis of finite Abelian groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient algorithms for the basis of finite Abelian groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient algorithms for the basis of finite Abelian groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-380522