Metadata-Version: 2.4
Name: triton_submodular
Version: 0.1.0a1
Summary: A Triton implementation of greedy submodular algorithms using fused GPU kernels
Author: Vikram Rangarajan
Author-email: Vikram Rangarajan <rangarav@purdue.edu>
License-Expression: MIT
Requires-Dist: triton>=3.4
Requires-Dist: numpy>=2
Requires-Dist: torch>=2.8
Requires-Python: >=3.9
Project-URL: Homepage, https://github.com/VikramRangarajan/triton_submodular/
Project-URL: Repository, https://github.com/VikramRangarajan/triton_submodular.git
Project-URL: Issues, https://github.com/VikramRangarajan/triton_submodular/issues
Description-Content-Type: text/markdown

# Triton Implementation of Greedy Optimization of Submodular Functions

This is a python-only implementation of [submodlib](https://github.com/decile-team/submodlib/) and [apricot](https://github.com/jmschrei/apricot/).

This library provides fused kernels for every (function, optimizer) pair available by dynamically generating them.

## Installation

```bash
pip install triton_submodular
```

or with uv,

As a package dependency:
```bash
uv add triton_submodular
```
For a venv:
```bash
uv pip install triton_submodular
```
For older GPUs (like pascal), you need to specify the cu126 wheel for pytorch:
```bash
uv pip install triton_submodular --torch-backend=cu126
```

## Features
- Functions:
  - Facility Location
  - Graph Cut
  - Feature Based
  - Max Coverage
- Optimizers:
  - Naive Greedy
  - Stochastic Greedy
  - Lazy Greedy

## Example Usage
```python
import torch
from triton_submodular.functions import FacilityLocation

X = torch.randn(100, 10, device="cuda", dtype=torch.float32)

fn = FacilityLocation(X) # generates euclidean similarity matrix by default

indices, gains = fn.maximize(10, "LazyGreedyTriton")

X_subset = X[indices]
```
This will take the data (100 points, 10 dimensional) and greedy select 10 points using the lazy greedy optimizer
which tries to maximize the facility location function.

## Testing

Clone and run `uv run -p 3.9 pytest -n auto`. Requires a GPU with CUDA support.

Deterministic optimizers are tested to be 1:1 against both apricot and submodlib's implementations.
Random algorithms (currently only stochastic greedy) are only tested against apricot, as submodlib uses
C's `rand()` function, making reproduction difficult.


NOTE: The stochastic greedy optimizer with the graphcut function currently does not match 1:1 to apricot's implementation.

## Roadmap
- [ ] Benchmarks and optimizations
- [ ] Add more submodular functions
- [ ] Add more optimizers
- [ ] Add more similarity metrics to graph functions that require a similarity matrix
- [ ] Add knapsack constraints
- [ ] Add sparse matrix support (maybe)
- [ ] Add streaming optimization (maybe)
