---
title: "LordOfRings"
url: "https://edoardo.anteprime.edoardogabrielli.com/en/projects/lordofrings"
lang: "en"
updated: "2026-10-31"
---

# LordOfRings

> LordOfRings: a method to detect rings in a sparse matrix, with a semi-parallel Taubin algorithm and GPU.

## LordOfRings

Finding rings in a sparse matrix, using the GPU.

## The problem

In an almost empty matrix, where the value 1 draws rings, you need to work out 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://edoardo.anteprime.edoardogabrielli.com/media/originals/2026/10/ff2193bc58004ab68e8c9ec148e58478/lordofrings.png)

## What I built

### 1. Circle fitting

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

### 2. Telling rings apart

Ptolemy's theorem on quadrilaterals inscribed in a circle is used to separate points belonging to different rings.

### 3. GPU computation

The module evaluates the radius and centre of each ring with GPU acceleration; a non-GPU version exists too.

### 4. Documentation

The project has documentation with tutorials.

### My role

University project developed in collaboration: the repository is published on the GitHub profile of Sara-a-r.

### Technologies

Python · CUDA · GPU · online documentation

> Moving an algorithm to the GPU forces you to think about it differently, in parallel from the start. I learned to measure before optimising and to keep a simple reference version to compare results against.

— What I learned

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

## A slow numerical computation

Tell me the problem: it is often better to change the algorithm before the hardware.

[Get in touch](https://edoardo.anteprime.edoardogabrielli.com/en/contact)

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