---
title: "LordOfRings"
url: "https://edoardogabrielli.com/en/projects/lordofrings"
lang: "en"
updated: "2026-11-02"
---

# LordOfRings

> LordOfRings: a method to find rings in a sparse matrix, with a GPU version. A group project.

A Python module that finds rings in a sparse matrix and computes their radius and centre, optionally on the GPU. A university group project.

**Stack:** Python, CUDA (pycuda), NumPy, Matplotlib.

## The problem

In an almost empty matrix, where the value 1 draws rings, you need the radius and centre of each ring and which ring each point belongs to. With many points, doing it naively is slow.

![Rings found in a sparse matrix](https://edoardogabrielli.com/media/originals/2026/10/ff2193bc58004ab68e8c9ec148e58478/lordofrings.png)

## How it works

### 1. Circle fitting

A semi-parallel Taubin algorithm estimates the radius and centre of each ring.

### 2. Separating the rings

Ptolemy's theorem on quadrilaterals inscribed in a circle is used to tell points of different rings apart.

### 3. GPU and reference version

The computation uses CUDA through pycuda; without a GPU there is a sequential Python/NumPy implementation.

### What I did

The repository is on Sara-a-r's profile and the work is shared: of 83 contributions, 47 are mine and 36 are Sara's. I do not remember exactly how the tasks were split, so I do not describe it.

### Status

From August 2021 to January 2022. Documentation with tutorials on Read the Docs, tests on Travis CI.

[Code on GitHub](https://github.com/Sara-a-r/LordOfRings) · [Documentation](https://lordofrings.readthedocs.io/en/latest/)

[← All projects](https://edoardogabrielli.com/en/projects)