Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Thermodynamic Linear Algebra

arxiv.org

Post reply on HN
Print view View original

51–60 of 60 posts

Re: Thermodynamic Linear Algebra

#51

Post by tnecniv »

Talinx wrote: post #19

Does this hold up when taking quantum mechanics into account? Let's assume you need at least m = n ^2 particles for a physical system modelling a n by n matrix and model the change of the system from setting the state of the particles (to the matrix elements) to measurement by a finite number of interactions between particles (by exchanging a photon): - a particle can interact with a particle of the heat bath - a par…

The coupling between variables is given by the (quadratic) potential of the system.

I think there is some confusion because they have two tiers of “particles” going on. The first is the masses coupled in the spring-mass system. In that system, each component of x is a particle. However, any specific vector x, in the parlance of thermodynamics, is a single microstate of the system. You can then form a macrostate, I.e., a distribution, of microstate particles, by considering an infinite (or near infinite) number of particles. The dynamics of the macrostate are given by the Fokker-Planck equation, where interactions where both interactions you mention come from the diffusion term only present due to connection with a heat bath.

So the n coupled masses are viewed as a single particle in an abstract system with (stochastic) gradient dynamics.

Re: Thermodynamic Linear Algebra

#52

Post by tnecniv »

aifer4 wrote: post #10
cperciva wrote: post #7

A classical computer can solve a linear system in O(N) time on O(N^2) processors, too.

This is an important observation, and is one of the reasons we included an energy-time tradeoff analysis in the paper. To our knowledge, this is the first result where the product energy * time has been shown to scale with dimension for solving linear systems of equations (in any computational paradigm).

The time-energy trade off is of particular interest to me. I’m a roboticist, but I’ve been looking at adapting similar thermodynamic results to research problems in my field (Crooks’ work has been quite inspirational). I’m looking forward to reading this paper in greater detail in a few days when I have time (I’m in the middle of a move) and might want to get in touch about research ideas if that’s of interest.

Re: Thermodynamic Linear Algebra

#53

Post by itissid »

At its core, How closely related is this to Hamiltonian Chain Monte Carlo(HCMC) methods?

Reading about waiting to reach equilibrium state, extracting paths and integrating it(IIRC this is analogus to estimating the expected value) in a space made me think of that :). Sorry if the comparison seems naive.

Re: Thermodynamic Linear Algebra

#54

Post by m_dupont »

I'm a little late to the party but hopefully someone can still answer this question.

In order to solve the linear system of equations in this framework, you need to integrate a measurement of the system over some time greater than t_0 and tau. However in equation 12 you can see that t_0 and tau are functions of the eigenvalues and the norm of the matrix.

AFAIK the best runtime algorithms we have for computing matrix eigenvalues is still O(d²), so even if the thermodynamic part of algorithm is linear in d, computing how long you would need to run the algorithm for is still quadratic in d, so there's no real gain.

Or am I missing something here?

Re: Thermodynamic Linear Algebra

#55

Post by pama »

m_dupont wrote: post #54

I'm a little late to the party but hopefully someone can still answer this question. In order to solve the linear system of equations in this framework, you need to integrate a measurement of the system over some time greater than t_0 and tau. However in equation 12 you can see that t_0 and tau are functions of the eigenvalues and the norm of the matrix. AFAIK the best runtime algorithms we have for computing matrix…

I’m not one of the authors and have only skimmed the paper thus far and found it interesting enough to warrant further study. I guess one could run the simulation in the hardware and monitor convergence as a function of time. I can also imagine cases where one could work on a class of problems that have a priori known worst case condition, or cases where the exact solution every time is not a hard requirement.

Re: Thermodynamic Linear Algebra

#58

Post by kaelan123 »

m_dupont wrote: post #54

I'm a little late to the party but hopefully someone can still answer this question. In order to solve the linear system of equations in this framework, you need to integrate a measurement of the system over some time greater than t_0 and tau. However in equation 12 you can see that t_0 and tau are functions of the eigenvalues and the norm of the matrix. AFAIK the best runtime algorithms we have for computing matrix…

Indeed the bounds on convergence times t_0 and tau depend on quantities that are expensive to compute. For example, if we consider the norm of A, this quantity can itself be bound by the values the elements A can take itself, which is a requirement on the type of hardware we would be using (as the elements of A are mapped to component values in the hardware that is considered in the appendix). There are other heuristic tricks one could use.

To give a comparison with conjugate gradients, there the condition number is in the convergence bound, however computing it requires the maximum and minimum eigenvalues, hence people never compute it, and rely on heuristics for convergence.

Re: Thermodynamic Linear Algebra

#59

Post by lachlan_gray »

aifer4 wrote: post #27
chenghuzi wrote: post #26

The RC circuit looks familiar. Is it related to neuromorphic computing hardware? Can it be implemented with existing hardware?

An interesting feature of this approach is that the proposed hardware doesn't rely on non-linear elements, memristors, or even active elements (besides an optional noise source). It is simply a passive network of oscillators with a DC bias on each cell. That said, the hardware to implement this at scale does not currently seem to exist. To my knowledge, the state of the art is https://app.normalcomputing.ai/composer

I haven't read the paper, so maybe completely irrelevant, but isn't there an analytical solution for a system of N coupled oscillators?

Re: Thermodynamic Linear Algebra

#60

Post by m_dupont »

kaelan123 wrote: post #58
m_dupont wrote: post #54

I'm a little late to the party but hopefully someone can still answer this question. In order to solve the linear system of equations in this framework, you need to integrate a measurement of the system over some time greater than t_0 and tau. However in equation 12 you can see that t_0 and tau are functions of the eigenvalues and the norm of the matrix. AFAIK the best runtime algorithms we have for computing matrix…

Indeed the bounds on convergence times t_0 and tau depend on quantities that are expensive to compute. For example, if we consider the norm of A, this quantity can itself be bound by the values the elements A can take itself, which is a requirement on the type of hardware we would be using (as the elements of A are mapped to component values in the hardware that is considered in the appendix). There are other heurist…

thankyou, that actually cleared things up for me
Post reply on HN