High-Performance Benchmarking: Randomized vs. Deterministic Matrix Algorithms

Overview

This repository contains the core benchmarking suite developed for my Bachelor's Thesis at the University of Tübingen. The project evaluates the trade-offs between randomized and deterministic algorithms in terms of numerical stability, memory footprint, and computational latency for large-scale datasets.

Tech Stack

• Language: Python 3.x
• Libraries: NumPy, Pandas, Matplotlib (for data visualization)
• Concepts: Linear Algebra, Algorithm Engineering, Performance Profiling

Key Features

• Automated Benchmarking: Custom-built suite to run extensive tests across varying matrix dimensions.
• Numerical Stability Analysis: Tools to measure error propagation in randomized vs. deterministic approaches.
• Visual Reporting: Automated generation of performance graphs (plots) to interpret high-dimensional data.

Benchmarking Results

Here are some visual insights generated by the benchmarking suite, comparing the runtime and error propagation of the implemented algorithms:

Figure 1: Comparison of execution time across error rate.

Figure 2: Comparison of execution error rate across different matrix dimensions.

This suite helps in selecting the most cost-efficient algorithm for large-scale data processing, balancing the need for speed (latency) with the required precision (error margins).

Running the Benchmarks

To reproduce the performance comparisons between Randomized and Deterministic SVD, you can run the benchmarking suite directly. The suite evaluates execution time and reconstruction error across various matrix dimensions and ranks.

Prerequisites

Ensure you have the required packages installed:

pip install -r requirements.txt

Which File?

• rand vs det new.py: Implementation of randomized and deterministic SVD algorithms.
• svd benchmark.py: Script for performing SVD benchmarks (runtime and error comparisons).
• mat mult alg.py: Implementation of deterministic and randomized matrix multiplication algorithms and associated benchmarks.
• svd compression.py: Implementation of image compression based on SVD, including tests.
• rand eigenfaces.py: Implementation of the Eigenfaces experiment with randomized SVD.
• rand eigenfaces.py: Implementation of the Eigenfaces experiment with randomized SVD.