3 ms·

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

aifer4 3y ago
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).
- elcritch 3y ago
  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.
- tnecniv 3y ago
  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.
deleted 3y ago
[deleted]
deleted 3y ago
[deleted]
thomasahle 3y ago
Here there are N cells with N^2 couplings. So as you say, a normal computer with this many processors could also solve a linear system in O(N sqrt(kappa)) time. (Using conjugate gradient, since matrix-vector-mult on the system would be O(N) time.) However, (1) these thermodynamic cells are much simpler than processors, and (2) it seems the overall energy required to simulate the SDE, once the couplings are initialized, only scales with O(N), not O(N^2) as in your digital case.
amelius 3y ago
You can come close to that time complexity on a single CPU by using multigrid methods. https://en.wikipedia.org/wiki/Multigrid_method https://en.wikipedia.org/wiki/Multigrid_method Unless of course your matrix has a prohibitively complicated structure.

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

elcritch 3y ago
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.
tnecniv 3y ago
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.

deleted 3y ago

[deleted]

deleted 3y ago

[deleted]

thomasahle 3y ago

Here there are N cells with N^2 couplings. So as you say, a normal computer with this many processors could also solve a linear system in O(N sqrt(kappa)) time. (Using conjugate gradient, since matrix-vector-mult on the system would be O(N) time.) However, (1) these thermodynamic cells are much simpler than processors, and (2) it seems the overall energy required to simulate the SDE, once the couplings are initialized, only scales with O(N), not O(N^2) as in your digital case.

amelius 3y ago

You can come close to that time complexity on a single CPU by using multigrid methods. https://en.wikipedia.org/wiki/Multigrid_method https://en.wikipedia.org/wiki/Multigrid_method Unless of course your matrix has a prohibitively complicated structure.