Constant depth, near constant depth, and subcubic size threshold circuits for linear algebraic calculations
A method of increasing an efficiency at which a plurality of threshold gates arranged as neuromorphic hardware is able to perform a linear algebraic calculation having a dominant size of N. The computer-implemented method includes using the plurality of threshold gates to perform the linear algebraic calculation in a manner that is simultaneously efficient and at a near constant depth. “Efficient” is defined as a calculation algorithm that uses fewer of the plurality of threshold gates than a naïve algorithm. The naïve algorithm is a straightforward algorithm for solving the linear algebraic calculation. “Constant depth” is defined as an algorithm that has an execution time that is independent of a size of an input to the linear algebraic calculation. The near constant depth comprises a computing depth equal to or between O(log(log(N)) and the constant depth.
1. A method of increasing an efficiency at which a plurality of threshold gates arranged as neuromorphic hardware is able to perform a linear algebraic calculation having a dominant size of N, the method comprising:
using the plurality of threshold gates to perform the linear algebraic calculation in a manner that is simultaneously efficient and at a near constant depth, wherein “efficient” is defined as a calculation algorithm that uses fewer of the plurality of threshold gates than a naïve algorithm, wherein the naïve algorithm is a straightforward algorithm for solving the linear algebraic calculation, wherein “constant depth” is defined as an algorithm that has an execution time that is independent of a size of an input to the linear algebraic calculation, and wherein the near constant depth comprises a computing depth equal to or between O(log(log(N)) and the constant depth.
2. The method of claim 1 wherein the linear algebraic calculation comprises matrix multiplication of two square matrices of size N×N.
3. The method of claim 2 wherein the calculation algorithm has a first number of operations of O(N 2+δ ) compared to the straightforward algorithm having a second number of operations of O(N 3 ), wherein δ comprises a number that is greater than or equal to zero but less than one.
4. The method of claim 3 further comprising:
converting an initial depth of the linear algebraic calculation, wherein the initial depth is log 2 N, to the near constant depth.
5. The method of claim 4 wherein the near constant depth is the constant depth, and wherein converting comprises:
setting the constant depth to a value of at most 2d+5 that determines whether trace (A 3 )≥τ using Õ(dN ω+cγ d ) of the plurality of threshold gates, where c>0 and γ<1 are constants with respect to N and d that depend on parameters of the calculation algorithm, wherein d is a constant, and wherein ω is between exactly 2 and less than 3.
6. The method of claim 4 further comprising:
dedicating a sub-plurality of the plurality of threshold gates to communicate non-binary numbers that require increasing precision to define during subsequent stages of the calculation algorithm.
7. The method of claim 1 wherein the linear algebraic calculation comprises a matrix inversion.
8. The method of claim 1 wherein the linear algebraic calculation comprises multiplying at least two matrices in order to count triangles in a graph G.
9. A neuromorphic computer comprising:
a plurality of threshold gates or spiking neurons configured to compute a specific linear algebraic calculation having a dominant size of N in a manner that is simultaneously efficient and at a near constant depth, wherein “efficient” is defined as a calculation algorithm that uses fewer of the plurality of threshold gates than a naïve algorithm, wherein the naïve algorithm is a straightforward algorithm for solving the specific linear algebraic calculation, wherein “constant depth” is defined as an algorithm that has an execution time that is independent of a size of an input to the specific linear algebraic calculation, and wherein the near constant depth comprises a computing depth equal to or between O(log(log(N)) and the constant depth.
10. The neuromorphic computer of claim 9 wherein the specific linear algebraic calculation comprises matrix multiplication of two square matrices of size N×N.
11. The neuromorphic computer of claim 10 wherein the calculation algorithm has a first number of operations of O(N 2+δ ) compared to the straightforward algorithm having a second number of operations of O(N 3 ), wherein δ comprises a number that is greater than or equal to zero but less than one.
12. The neuromorphic computer of claim 11 wherein the plurality of threshold gates or spiking neurons are further configured to convert an initial depth of the specific linear algebraic calculation to the near constant depth, wherein the initial depth is log 2 N.
13. The neuromorphic computer of claim 12 wherein the near constant depth is the constant depth, and wherein in being configured to convert, the plurality of threshold gates or spiking neurons are further configured to set the constant depth to a value of at most 2d+5 that determines whether trace (A 3 )≥τ using Õ(dN ω+cγ d ) of the plurality of threshold gates or spiking neurons, where c>0 and γ≤1 are constants with respect to N and d that depend on parameters of the calculation algorithm, wherein d is a constant, and wherein ω is between exactly 2 and less than 3.
14. The neuromorphic computer of claim 12 wherein a sub-plurality of the plurality of threshold gates or spiking neurons are dedicated to communicate non-binary numbers that require increasing precision to define during subsequent stages of the calculation algorithm.
15. The neuromorphic computer of claim 9 wherein the specific linear algebraic calculation comprises a matrix inversion.
16. The neuromorphic computer of claim 9 wherein the specific linear algebraic calculation comprises multiplying at least two matrices in order to count triangles in a graph G.
17. A method of manufacturing a neuromorphic computer tailored to perform a specific linear algebraic calculation, the method comprising:
manufacturing a plurality of threshold gates or spiking neurons; and
arranging the plurality of threshold gates or spiking neurons to compute the linear algebraic calculation having a dominant size N in a manner that is simultaneously efficient and at a near constant depth, wherein “efficient” is defined as a calculation algorithm that uses fewer of the plurality of threshold gates than a naïve algorithm, wherein the naïve algorithm is a straightforward algorithm for solving the linear algebraic calculation, wherein “constant depth” is defined as an algorithm that has an execution time that is independent of a size of an input to the linear algebraic calculation, and wherein the near constant depth comprises a computing depth equal to or between O(log(log(N)) and the constant depth.
18. The method of claim 17 wherein the specific linear algebraic calculation comprises matrix multiplication of two square matrices of size N×N.
19. The method of claim 18 further comprising:
further arranging the plurality of threshold gates or spiking neurons to convert an initial depth of the specific linear algebraic calculation to the near constant depth, wherein the initial depth is log 2 N.
20. The method of claim 19 further comprising:
further arranging the plurality of threshold gates or spiking neurons to dedicate a sub-plurality of the plurality of threshold gates or spiking neurons to communicate non-binary numbers that require increasing precision to define during subsequent stages of the calculation algorithm.