generating the ideals of a poset in logarithmic time complexity

[saatvikraoIITGN]

Problem Description

Currently, SageMath lacks efficient algorithms for enumerating the ideals of a partially ordered set (poset) in logarithmic time complexity. An enumeration of the ideals of a poset can be used to solve various scheduling and reliability problems. Current algorithms for generating ideals require an amortized time of O(n) per ideal in the worst case, where n is the number of elements in the poset. Through this issue, we can generate ideals in an amortized time of O(log n) per ideal.

Proposed Solution

The proposed solution involves implementing an efficient algorithm for enumerating the ideals of a partially ordered set (poset) in logarithmic time complexity within SageMath. One approach to achieve this is by adapting the algorithm described in the research paper "Enumerating the Ideals of a Poset" by Matthew B. Squire. This algorithm presents a divide-and-conquer strategy that efficiently enumerates the ideals of a post.

Specifically, the implementation would involve creating a recursive procedure to generate ideals based on subsets of elements in the poset. By strategically partitioning the poset and exploiting its structure, the algorithm can achieve logarithmic time complexity for ideal enumeration.

Alternatives Considered

1. Naive Enumeration: One alternative is to continue using the current methods for enumerating ideals, which typically have polynomial time complexity. However, these methods may become impractical for large posets or when performing intensive computations.
2. External Libraries: Another option is to rely on external libraries or tools that provide efficient algorithms for enumerating ideals. However, this approach may introduce dependencies and compatibility issues, and it may not integrate seamlessly with SageMath's existing functionality.
3. Custom Implementations: Users could develop custom implementations of ideal enumeration algorithms outside of SageMath. While feasible, this approach may require significant effort and expertise, and it may not benefit from the full integration and support offered by SageMath.

Additional Information

No response

Is there an existing issue for this?

• [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.

[DaveWitteMorris]

I think alternative (2) is the one that is appropriate for sagemath, because our philosophy is to avoid re-inventing the wheel. The overarching design of sagemath is the integration of many mathematical packages into one interface, and the developers would rather deal with incompatibilities that arise than take responsibility for maintaining yet more code.

[saatvikraoIITGN]

I have implemented an acyclic orientations iterator in graphs/orientations.py, where we generate the upsets/ideals of the poset. But it is a trivial method involving exponential time. To improve this, it would be great if we can do this in better time. Implementing this better method can have other applications too as generating ideals/upsets of a poset is common.