Computing Irreducible Decomposition of Monomial Ideals

Details Computing Irreducible Decomposition of Monomial Ideals Computing Irreducible Decomposition of Monomial Ideals

2008-11-20

arxiv.org/abs/0811.3425v1

Mathematics

Commutative Algebra

18 pages, 5 figures

Scientific paper

The paper presents two algorithms for finding irreducible decomposition of monomial ideals. The first one is recursive, derived from staircase structures of monomial ideals. This algorithm has a good performance for highly non-generic monomial ideals. The second one is an incremental algorithm, which computes decompositions of ideals by adding one generator at a time. Our analysis shows that the second algorithm is more efficient than the first one for generic monomial ideals. Furthermore, the time complexity of the second algorithm is at most $O(n^2p\ell)$ where $n$ is the number of variables, $p$ is the number of minimal generators and $\ell$ is the number of irreducible components. Another novelty of the second algorithm is that, for generic monomial ideals, the intermediate storage is always bounded by the final output size which may be exponential in the input size.

Affiliated with

Also associated with

No associations

Rating

Computing Irreducible Decomposition of Monomial Ideals 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 Computing Irreducible Decomposition of Monomial Ideals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Irreducible Decomposition of Monomial Ideals will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-162483