Normal Computing's "Thermodynamic Linear Algebra" published in Nature Unconventional Computing

We're excited to announce the publication of Normal Computing 's "Thermodynamic Linear Algebra" by Maxwell Aifer , Kaelan Donatella , Max Hunter Gordon , Sam Duffield , Thomas Dybdahl Ahle , Dan Simpson , Gavin Crooks , and Patrick Coles in Nature Portfolio Unconventional Computing!

Today’s digital AI hardware is plateauing at about 1000x the fundamental energy efficiency limits[1]. This early?foundational?work from the Normal Computing team proposes a path to closing this gap, using thermodynamics as a unifying lens.?And this work is now published in Nature Partner Journal.

Our algorithms connect two seemingly distinct fields by showing how sampling from the equilibrium distribution of coupled harmonic oscillators can solve key linear algebra primitives like matrix inversion, linear systems, and determinant calculation.

Let's walk through the key mathematical insight:

Consider a system with potential energy function: U(x) = ?x^T Ax - b^T x

where A is symmetric positive definite matrix.

When this system reaches thermal equilibrium:

• The spatial coordinate x follows a Gaussian distribution
• The mean 〈x〉 solves the linear system Ax = b
• The covariance matrix gives A?1
• The partition function relates to det(A)

This connection works because, once the system equilibrates, x is distributed according to the Boltzmann distribution f(x) ∝ exp(-βU(x)), which becomes a multivariate Gaussian when you plug in the quadratic potential for U(x).

This particular Gaussian is maximized at Ax = b, and its covariance is proportional to A?1. In this sense, the physical dynamics associated with thermal equilibration have the effect of inverting the A matrix and solving the linear system Ax = b.

Similarly, by measuring free energy changes during the equilibration process, the determinant of A is calculated.

By leveraging these physical dynamics, we:

• Achieved O(dκ log(1/ε)) scaling for linear systems vs O(d2) for traditional methods, where d=matrix dimension, κ=condition number, ε=error tolerance
• Matrix inversion accomplished in O(d2κ log(1/ε)) time, showing linear speedup over classical O(d3)
• Demonstrated empirical speedups over Cholesky decomposition for d>1000, with increasing advantages at higher dimensions
• Predicted superior early-time performance vs conjugate gradient method (especially for large condition numbers), suggesting that our method will find application in providing fast, low-precision solutions

Additional details on how we implemented this algorithm experimentally, in the case of matrix inversion, can be found in this blog post.

Stay tuned for more insights into the groundbreaking work happening at Normal Computing as we continue to push the boundaries of AI hardware efficiency!

Read the full paper here: https://www.nature.com/articles/s44335-024-00014-0