SDOT
====
This package contains tools to handle
* semi-discrete transport plans (between discrete and generic densities),
* polyhedral convex functions (max of affine functions),
* and power diagrams (a generalization of Voronoi diagrams).
It works in any number of dimensions. It is highly optimized, in terms of execution speed and memory usage.
Historically, this package is a re-design of the `pysdot` package, which was written to handle a wide number of semi-discrete transport applications (partial transport, Moreau-Yosida regularization, etc...) but only worked in 2D or 3D. Additionaly, and more specifically, we wanted the APIs much more comprehensive and generic.
Currently, there are bindings for C++ and Python.
Installation
------------
### Pip
For python, `pip install sdot` should do the job, including some precompiled libraries for the most common cases (2D/3D, float64, ...). If your cases are not included in the distribution, the required dynamic libraries will be automatically compiled on first use. In this situation, you will need to have a C++ compiler installed on your machine. As scons is used to find and call the compiler, all you need to do is install one compiler that is compatible with this builder (for instance g++, clang, xcode, vscode, ...).
For a compiler : under Debian like, `sudo apt install g++`. Under Mac os, `xcode-select --install`. Under Windows, you can follow [this link](https://code.visualstudio.com/docs/cpp/config-mingw#_prerequisites).
### Sources
To get that latest version, `sdot` can also be installed from the git repository.
For the python modules:
```bash
git clone https://github.com/sdot-team/sdot.git
# maybe after a micromamba activate ...
cd sdot/src/python
pip install flit
flit install -s # -s makes symbolic links to the sources
```
Notebook examples
-----------------
Here are some notebooks you can download and test on your own machine or via google colab to understand the overall spirit.
* Power or voronoi diagrams in python: [file](tutorials/python/tutorial_power_diagram.ipynb), [colab](https://colab.research.google.com/drive/1yT62po-HFCxeXD4D_6XF8pHMgl3Fut34?usp=sharing).
* Optimal transport operations in python: [file](tutorials/python/tutorial_optimal_transport.ipynb), [colab](https://colab.research.google.com/drive/1P7l7_8QaEUFiVz49Ll1Avhwi8meaHojl?usp=sharing).
* Polyhedral convex function in python: [file](doc/polyhedral_convex_py.md), [colab](https://colab.research.google.com/drive/1EDk557WqxuIdlpqTV62rQWcRDklqZcai?usp=sharing).
If you're looking for more simple examples, there is an [example directory](examples/) with more concise notebooks, oriented on specific tasks.
Extensive documentation
-----------------------
[The generated pydoc files](...)
A word on performance
---------------------
The most common tools to handle voronoi and power diagrams start from delaunay (regular) triangulations. Building this triangulation is generaly the most time-consuming part of this approach, notably because one have to deal with the problems that come with digital precision...
Nevertheless, for most applications of the sdot package, we only need the *integrals* of the cells and the boundaries, meaning that most of the problems with digital precision naturally vanish at the end. We also realized that it was much more convenient for the user to work directly with the cells.
Bearing in mind that exact connectivity may of course be required for some applications (the 'dual' geometry becoming the triangulation in our case :) ), we therefore decided to give a try to algorithms with a focus on the cells, that are computed individually in a fully parallel fashion. We tried to stay on the user specified scalar types (e.g. `float64`) as long as possible. Finally, we designed adapted spatial acceleration structures to stay within O(n log(n)) execution speed with the smallest possible constant.
Internally, it is written in C++/Cuda with SIMD/SIMT instructions. It support large vectors, for out-of-core and multi-machine computations. More on [this page](doc/performance.md).
On going work
-------------
* pre-guess of the weight to avoid void cells at the beginning
* non-linear solvers to avoid bad newton directions
* pytorch compatible operations
Raw data
{
"_id": null,
"home_page": null,
"name": "sdot",
"maintainer": null,
"docs_url": null,
"requires_python": null,
"maintainer_email": null,
"keywords": "optimal transport, power diagram, Laguerre diagram",
"author": null,
"author_email": "Hugo Leclerc <hugo.leclerc@universite-paris-saclay.fr>",
"download_url": "https://files.pythonhosted.org/packages/24/29/6e2f49b0d88c274a67d2cfb41912ca1031acd5015a7c00dd4d9750fcdc7f/sdot-2024.12.7.1.tar.gz",
"platform": null,
"description": "SDOT\n====\n\nThis package contains tools to handle\n* semi-discrete transport plans (between discrete and generic densities),\n* polyhedral convex functions (max of affine functions),\n* and power diagrams (a generalization of Voronoi diagrams).\n\nIt works in any number of dimensions. It is highly optimized, in terms of execution speed and memory usage.\n\nHistorically, this package is a re-design of the `pysdot` package, which was written to handle a wide number of semi-discrete transport applications (partial transport, Moreau-Yosida regularization, etc...) but only worked in 2D or 3D. Additionaly, and more specifically, we wanted the APIs much more comprehensive and generic.\n\nCurrently, there are bindings for C++ and Python.\n\nInstallation\n------------\n\n### Pip\n\nFor python, `pip install sdot` should do the job, including some precompiled libraries for the most common cases (2D/3D, float64, ...). If your cases are not included in the distribution, the required dynamic libraries will be automatically compiled on first use. In this situation, you will need to have a C++ compiler installed on your machine. As scons is used to find and call the compiler, all you need to do is install one compiler that is compatible with this builder (for instance g++, clang, xcode, vscode, ...). \n\nFor a compiler : under Debian like, `sudo apt install g++`. Under Mac os, `xcode-select --install`. Under Windows, you can follow [this link](https://code.visualstudio.com/docs/cpp/config-mingw#_prerequisites).\n\n### Sources\n\nTo get that latest version, `sdot` can also be installed from the git repository.\n\nFor the python modules:\n\n```bash\ngit clone https://github.com/sdot-team/sdot.git\n# maybe after a micromamba activate ...\ncd sdot/src/python\npip install flit\nflit install -s # -s makes symbolic links to the sources\n```\n\nNotebook examples\n-----------------\n\nHere are some notebooks you can download and test on your own machine or via google colab to understand the overall spirit.\n\n* Power or voronoi diagrams in python: [file](tutorials/python/tutorial_power_diagram.ipynb), [colab](https://colab.research.google.com/drive/1yT62po-HFCxeXD4D_6XF8pHMgl3Fut34?usp=sharing).\n* Optimal transport operations in python: [file](tutorials/python/tutorial_optimal_transport.ipynb), [colab](https://colab.research.google.com/drive/1P7l7_8QaEUFiVz49Ll1Avhwi8meaHojl?usp=sharing).\n* Polyhedral convex function in python: [file](doc/polyhedral_convex_py.md), [colab](https://colab.research.google.com/drive/1EDk557WqxuIdlpqTV62rQWcRDklqZcai?usp=sharing).\n\nIf you're looking for more simple examples, there is an [example directory](examples/) with more concise notebooks, oriented on specific tasks.\n\nExtensive documentation\n-----------------------\n\n[The generated pydoc files](...)\n\nA word on performance\n---------------------\n\nThe most common tools to handle voronoi and power diagrams start from delaunay (regular) triangulations. Building this triangulation is generaly the most time-consuming part of this approach, notably because one have to deal with the problems that come with digital precision...\n\nNevertheless, for most applications of the sdot package, we only need the *integrals* of the cells and the boundaries, meaning that most of the problems with digital precision naturally vanish at the end. We also realized that it was much more convenient for the user to work directly with the cells.\n\nBearing in mind that exact connectivity may of course be required for some applications (the 'dual' geometry becoming the triangulation in our case :) ), we therefore decided to give a try to algorithms with a focus on the cells, that are computed individually in a fully parallel fashion. We tried to stay on the user specified scalar types (e.g. `float64`) as long as possible. Finally, we designed adapted spatial acceleration structures to stay within O(n log(n)) execution speed with the smallest possible constant.\n\nInternally, it is written in C++/Cuda with SIMD/SIMT instructions. It support large vectors, for out-of-core and multi-machine computations. More on [this page](doc/performance.md).\n\nOn going work\n-------------\n\n* pre-guess of the weight to avoid void cells at the beginning\n* non-linear solvers to avoid bad newton directions\n* pytorch compatible operations\n",
"bugtrack_url": null,
"license": null,
"summary": "Tools to construct/handle PowerDiagram, notably for semi-discrete optimal transport",
"version": "2024.12.7.1",
"project_urls": null,
"split_keywords": [
"optimal transport",
" power diagram",
" laguerre diagram"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "0febd41c8e7de73a679c6f16c1b9cefc62ce281de9454038081cc5a929c930f0",
"md5": "1d008c7878bae31133893e2b67af2250",
"sha256": "9655731c3eaf2e03c75e3f2c99a2de77e263a812ce91de505f19dd87c754e5f1"
},
"downloads": -1,
"filename": "sdot-2024.12.7.1-py2.py3-none-any.whl",
"has_sig": false,
"md5_digest": "1d008c7878bae31133893e2b67af2250",
"packagetype": "bdist_wheel",
"python_version": "py2.py3",
"requires_python": null,
"size": 103340,
"upload_time": "2024-12-07T08:00:51",
"upload_time_iso_8601": "2024-12-07T08:00:51.623648Z",
"url": "https://files.pythonhosted.org/packages/0f/eb/d41c8e7de73a679c6f16c1b9cefc62ce281de9454038081cc5a929c930f0/sdot-2024.12.7.1-py2.py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "24296e2f49b0d88c274a67d2cfb41912ca1031acd5015a7c00dd4d9750fcdc7f",
"md5": "a92f5fd3824df37fe21b352808045872",
"sha256": "68b034ba9a3eea91d53b30e632aa42668bf12d453fe700ffb5affae94c1d2803"
},
"downloads": -1,
"filename": "sdot-2024.12.7.1.tar.gz",
"has_sig": false,
"md5_digest": "a92f5fd3824df37fe21b352808045872",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 71038,
"upload_time": "2024-12-07T08:00:53",
"upload_time_iso_8601": "2024-12-07T08:00:53.808452Z",
"url": "https://files.pythonhosted.org/packages/24/29/6e2f49b0d88c274a67d2cfb41912ca1031acd5015a7c00dd4d9750fcdc7f/sdot-2024.12.7.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-12-07 08:00:53",
"github": false,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"lcname": "sdot"
}
JSON