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

41–50 of 60 posts

Re: Thermodynamic Linear Algebra

#41

Post by aifer4 »

guyomes wrote: post #35

This is very interesting, especially considering the energy-time tradeoff. I wonder how it compares to optical computing [1], where FFT can be done efficiently [2], or to analog computing for linear algebra [3]. [1]: https://en.wikipedia.org/wiki/Optical_computing#Optical_Four... [2]: https://doi.org/10.1038/s41598-017-13733-1 [3]: https://doi.org/10.1109/MM.2017.55

The Optical Fourier Transform (OFT) in [2] is a way to compute the Discrete Fourier Transform (DFT), and is an alternative to the Fast Fourier Transform (FFT). The OFT basically does a matrix-vector multiplication, where the matrix has a special form, which is accomplished physically using the diffraction of light as it propagates from one plane to another. Although the paper claims constant time for this operation, it’s likely that when the optical array gets bigger, the light has to propagate further for the diffraction pattern to emerge, meaning the time gets longer too. But the coefficient of this scaling is extremely small, because light travels fast. This also accelerates linear algebra using physical dynamics, but can only be used to multiply one particular matrix (the DFT matrix) by an arbitrary vector.

Re: Thermodynamic Linear Algebra

#42

Post by rsp1984 »

This looks quite amazing at first glance but looking a bit deeper some elephant-in-the-room questions pop up:

1. Simple Gradient Descent is already linear in time w.r.t. # of parameters (but it is an iterative method). It seems to be missing from Table I too. This method requires waiting for equilibration, so could it be seen as another form of iterative method? If so, wouldn't the proper comparison be against known O(n) first-order iterative methods like GD as opposed to exact methods (O(n^3)) or pseudo-2nd-order iterative methods like CG (O(n^2))?

2. In 2.B.3 the paper says "Note that this includes a compilation step that scales as O(d2)". I think this needs some clarification. Is this saying that, in order to run this on actual hardware, there's a compilation step involved that is O(n^2)? Of course O notation says nothing about linear factors but wouldn't that contradict what's stated in Table I?

Re: Thermodynamic Linear Algebra

#43

Post by aifer4 »

canjobear wrote: post #39
aifer4 wrote: post #12

Earlier quoted context omitted.

Definitely. Landauer's principle gives a lower bound on the amount of energy a computation requires, which is k_B T ln(2) times the number of bits erased in the process, the decrease in Shannon entropy. Our energy cost analysis is not based on the Landauer limit, but simply on the energy difference between equilibrium states. But our algorithm for estimating the determinant is based on effectively measuring the entro…

I always have trouble thinking of computation in terms of “bits erased”. How many bits are erased when I sort an array? Or invert a matrix? Or compute a function like f(x)=1, which seems to maximally erase information, but doesn’t intuitively seem like it should cost a lot of energy.

To answer your question about sorting an array: For an array of length n, where each element takes one of m possible values, there are n^m possible arrays. But there are only O(n^m/n!) possible sorted arrays, which could be crudely approximated as O(n^(m-n)). The decrease in information is proportional to the log of the ratio of the number of possible states before and after the computation, which is in this case log(n^n) = n log n. See another explanation here https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall07/...

Re: Thermodynamic Linear Algebra

#44

Post by rsp1984 »

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…

> But the second interaction should matter, otherwise how can the system capture/model dependencies between variables (I guess)?

Keep in mind that the venerable (and enormously successful!) gradient descent method does not model dependencies between variables either and manages to find solutions too. It just has to iterate a bit on it -- actually not unlike the method presented here.

Re: Thermodynamic Linear Algebra

#45

Post by aifer4 »

rsp1984 wrote: post #42

This looks quite amazing at first glance but looking a bit deeper some elephant-in-the-room questions pop up: 1. Simple Gradient Descent is already linear in time w.r.t. # of parameters (but it is an iterative method). It seems to be missing from Table I too. This method requires waiting for equilibration, so could it be seen as another form of iterative method? If so, wouldn't the proper comparison be against known…

You're right, that iterative methods may be linear in time with respect to the number of parameters. In this paper, we provide a method which is linear in time with respect to the dimension (d) of the vector (x) we are solving for in the equation A x = b. The number of parameters is d^2 + d, as there are d^2 parameters for the matrix A and d for the vector b. Gradient descent would require a matrix-vector multiplication just to compute the gradient, which is already O(d^2).

You make an important point, regarding the compilation. In this case, we are talking about the time it takes to upload the matrix A and vector b to the hardware. This requires O(d^2) numbers to be updated, but assuming it is done in parallel it could be done in O(d) time, and the coefficient of this scaling is independent of the physical parameters of the analog hardware. For this reason, in the analysis of the algorithm, we are generally ignoring the time to update the parameters, as is clarified in the Methods section.

Re: Thermodynamic Linear Algebra

#46

Post by elcritch »

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).

Impressive work! You give me hope that we'll be able to continue scaling computing in domains which require it.

Also makes me wonder if Google's DWave could be more similar to this method rather than true quantum computing.

Re: Thermodynamic Linear Algebra

#47

Post by rsp1984 »

aifer4 wrote: post #45
rsp1984 wrote: post #42

This looks quite amazing at first glance but looking a bit deeper some elephant-in-the-room questions pop up: 1. Simple Gradient Descent is already linear in time w.r.t. # of parameters (but it is an iterative method). It seems to be missing from Table I too. This method requires waiting for equilibration, so could it be seen as another form of iterative method? If so, wouldn't the proper comparison be against known…

You're right, that iterative methods may be linear in time with respect to the number of parameters. In this paper, we provide a method which is linear in time with respect to the dimension (d) of the vector (x) we are solving for in the equation A x = b. The number of parameters is d^2 + d, as there are d^2 parameters for the matrix A and d for the vector b. Gradient descent would require a matrix-vector multiplicat…

OK, got it. I think what you're describing is Gradient Descent on the Normal Equations to solve an overdetermined linear system. Indeed in such a system dim(x) == dim(b) == d. Matrix A is fixed though and not part of the estimation but you're correct about the complexity of gradient computation which is indeed O(d^2).

Thanks for the clarification of the uploading / compilation step.

Re: Thermodynamic Linear Algebra

#49

Post by amelius »

cperciva wrote: post #7

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

You can come close to that time complexity on a single CPU by using multigrid methods.

https://en.wikipedia.org/wiki/Multigrid_method

Unless of course your matrix has a prohibitively complicated structure.

Post reply on HN