Brent's Method on CUDA

One independent root-finder per GPU thread. The first CUDA implementation of Brent's method.

35.31×kernel speedup vs single-thread CPU
8.79×end-to-end on an RTX 3080
<1e-10fp64 deviation across Python, C++, CUDA

THE PROBLEM

Root-finding refuses to parallelize.

Brent's method is the workhorse of numerical root-finding: robust, derivative-free, and stubbornly sequential. Each iteration depends on the one before it, so a single solve cannot be spread across GPU threads.

But scientific workloads rarely need one root. They need thousands of them: the same equation swept across parameters, ensembles, and batched simulations. That reframing is the whole trick.

THE APPROACH

Batch parallelism, one solver per thread.

Instead of parallelizing inside the algorithm, each CUDA thread runs a complete, independent Brent's solve. The project built the same solver three times, in reference Python, single-thread C++, and CUDA, and validated every implementation against a Python ground truth.

The hard part was bit-level discipline: keeping fp64 results identical across all three implementations, so the GPU version is a drop-in replacement rather than an approximation.

Two speedup curves against batch size, from 2^10 to 2^22 problems: kernel-only rising to 35.3 times the CPU baseline, and wall-time rising to 8.9 times, with the gap between them widening across the sweep. — **Two speedups, not one**Kernel-only against wall-time, swept across batch size. The gap between the curves is what it costs to get the data on and off the card. RTX 3080, median of ten trials.

A single horizontal bar of GPU wall time at four million problems, totalling 76.0 milliseconds, split into cudaMalloc 5.08, host-to-device copy 28.34, kernel 20.05, device-to-host copy 18.38 and cudaFree 4.20 milliseconds. — **Where the wall time goes**One batch of four million problems, broken into phases. The kernel is 20.05 ms of 76.0; everything else is allocation and copies. Phase durations from nsys.

THE IMPACT

35 times faster, provably identical.

On an NVIDIA RTX 3080 the CUDA kernel solves batches 35.31 times faster than the CPU baseline, and 8.79 times faster end-to-end including transfers, with results validated to below 1e-10 against the reference. The same technique generalizes to any batchable numerical method.

CUDA
C++
Python
CMake
GPU Computing
Numerical Computing