Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR07-052 | 21st April 2008 00:00

Linear and Sublinear Time Algorithms for the Basis of Abelian Groups Revision of: TR07-052 Abstract:=09It is well known that every finite abelian group G can be=20 represented as a direct product of cyclic groups: G\cong G_1\times=20 G_2\times \cdots \times G_t, where each G_i is a cyclic group of=20 order p^j for some prime p and integer j\ge 1.=20 If a_i generates the cyclic group of G_i, i=3D1,2,\cdots, t,=20 then the elements a_1,a_2,\cdots, a_t are called a basis of G. We show an= =20 a

RSS-Feed




Revision #2
Authors: Li, Chen, Fu, Ye Bin
Accepted on: 21st April 2008 00:00
Downloads: 1179
Keywords: 


Abstract:


Revision #1 to TR07-052 | 7th October 2007 00:00

Linear and Sublinear Time Algorithms for the Basis of Abelian Groups Revision of: TR07-052





Revision #1
Authors: Li Chen, Bin Fu
Accepted on: 7th October 2007 00:00
Downloads: 1203
Keywords: 


Abstract:

It is well known that every finite Abelian group $G$ can be
represented
as a direct product of cyclic groups: $G=G_1\circ G_2\circ\cdots \circ
G_t$, where
each $G_i$ is a cyclic group of size $p^j$ for some prime $p$ and integer
$j\ge 1$.
If $a_i$ is the generator of the cyclic group of $G_i$, $i=1,2,\cdots, t$,
then the
elements a_1,a_2,\cdots, a_t$ are called a basis of $G$. In this paper,
we first
obtain an $O(n)$-time deterministic algorithm for computing the basis of
an Abelian
group with $n$ elements. The existing algorithms need $O(n^2)$ time by
Chen and
$O(n^{1.5})$ time by Buchmann and Schmidt.
We then derive an $O((\sum_{i=1}^k _i^{n_i/2}n_i^2)(\log n)\log\log
n)$-time randomized
algorithm to compute the basis of Abelian group $G$ of size $n$ with
factorization
$n=p_1^{n_1}\cdots p_t^{n_t}$, which is also a part of the input. It
implies
an $O(n^{1/2}(\log n)^3\log\log n)$-time randomized algorithm to compute
the basis of
an Abelian group $G$ of size $n$. It also implies that if $n$ is an
integer
in $\{1,2, \cdots, m\}-G(m,c)$, then the basis of an Abelian group of size
$n$ can be
computed in $O((\log n)^{{c\over 2}+3}\log\log n)$-time, where $c$ is any
positive constant
and $G(m,c)$ is a subset of the small fraction of integers in $\{1,2,
\cdots, m\}$ with
${|G(m,c)|\over m}=O({1\over (\log m)^{c/2}})$ for every integer $m$.


Paper:

TR07-052 | 7th May 2007 00:00

Linear and Sublinear Time Algorithms for the Basis of Abelian Groups





TR07-052
Authors: Li Chen, Bin Fu
Publication: 16th June 2007 19:32
Downloads: 1173
Keywords: 


Abstract:

It is well known that every finite Abelian group $G$ can be
represented as a product of cyclic groups: $G=G_1\times
G_2\times\cdots G_t$, where each $G_i$ is a cyclic group of size
$p^j$ for some prime $p$ and integer $j\ge 1$. If $a_i$ is the
generator of the cyclic group of $G_i$, $i=1,2,\cdots, t$, then the
elements $a_1,a_2,\cdots, a_t$ are the basis of $G$. In this paper,
we first obtain an $O(n)$-time deterministic algorithm for
computing the basis of an Abelian group with $n$ elements. This
improves the previous $O(n^2)$ time algorithm found by
Chen. We then derive an $O((\sum_{i=1}^t p_i^{n_i-1}n_i^2\log p_i)(\log n)(\log\log n))$-time randomized
algorithm to compute the basis of Abelian group $G$ of size $n$ with
factorization $n=p_1^{n_1}\cdots p_k^{n_t}$, which is also a part of
the input. This shows that for a large number of cases, the basis of
a finite Abelian group can be computed in sublinear time. For
example, it implies an $O(n^{1-{1\over d}}(\log n)^3\log\log
n)$-time randomized algorithm to compute the basis of an Abelian
group $G$ of size $n=p_1^{n_1}\cdots p_t^{n_t}$, where $d=\max\{ n_i
| i=1,\cdots, t\}$. It is a sublinear time algorithm if $\max\{ n_i
| i=1,\cdots, t\}$ is bounded by a constant. It also implies that if
$n$ is an integer in $[1,m]-G(m,c)$, then the basis of an Abelian
group of size $n$ can be computed in $O((\log n)^{c+3}\log\log
n)$-time, where $c$ is any positive constant and $G(m,c)$ is a
subset of the small fraction of integers in $[1,m]$ with
${|G(m,c)|\over m}=O({1\over (\log m)^{c/2}})$ for every integer
$m$.



ISSN 1433-8092 | Imprint