6 ms·

A New Formula for the Determinant

95 points by scentoni 4y ago

abetusk 4y ago
I'm sorry, I'm having a hard time parsing this paper. It looks like even calculating "partial partitions" is exponential. Have they found a nice polynomial time algorithm to find determinants or is this just an exponential algorithm but with fewer components than what is "traditional"? FYI, The Bareiss algorithm can calculate the determinant in polynomial time, including bounding the bit complexity to polynomial space [0]. [0] https://en.wikipedia.org/wiki/Bareiss_algorithm https://en.wikipedia.org/wiki/Bareiss_algorithm
- steppi 4y ago
  From my read of the paper. This new formula also gives an exponential time algorithm. It’s not of interest as a practical method for computing determinants. It does however have interesting geometric and combinatorial properties and they used it to give new bounds for the tensor rank and Waring rank of a determinant respectively. You can think of these ranks loosely as measures of the “complexity” of a determinant (but not in the sense of computational complexity). These ranks are of interest in pure mathematics but I can’t really say more about them because it’s been too many years since I’ve studied related math.
robinhouston 4y ago
Oh wow! I wasn’t expecting to see this on HN. I’m one of the authors of the paper, and I’m happy to answer any questions. (I’m sorry I didn’t see it earlier, it was posted in the middle of my night.) First of all, to clear up a possible misunderstanding: this new formula will not help you to compute determinants more quickly. The number of terms still grows a lot faster than polynomial, and if you just want to compute the determinant, there are polynomial-time algorithms for that. The best theoretical results on the complexity of computing determinants, that I know of, are in [0]. In practice you'd probably use Gaussian elimination, or maybe Bareiss for integers. Someone complained that there’s no code in the paper. Since it isn’t really useful for practical computation, I didn’t think code would be useful, but in fact it did start as a Mathematica program when I first discovered it. Adam Goucher (one of my co-authors) wrote a blog post on it [1] within a few days of its discovery, which links to my original Mathematica notebook. (Edit: ur-whale points out that the link to the Mathematica notebook no longer works. I have now republished it at [2].) [0] https://users.cs.duke.edu/~elk27/bibliography/04/KaVi04_2697263.pdf https://users.cs.duke.edu/~elk27/bibliography/04/KaVi04_2697... [1] https://cp4space.hatsya.com/2022/07/02/a-combinatorial-proof-of-houstons-identity/ https://cp4space.hatsya.com/2022/07/02/a-combinatorial-proof... [2] https://www.wolframcloud.com/obj/robin.houston/Published/determinants.nb https://www.wolframcloud.com/obj/robin.houston/Published/det...
- ur-whale 4y ago
  > Someone complained that there’s no code in the paper. That was me, apparently much to the dislike of a number of HNers :) Thank you very much for the pointer to the notebook although it is not easy to access, you seem to need a Wolfram account to get to it. [EDIT]: "Sorry, you do not have permission to access this item." after I logged into Wolfram ... > Since it isn’t really useful for practical computation, I didn’t think code would be useful This is a very common misconception. There is a large category of people out there (software engineers among other) that find it much easier to read code than reading abstract math formulas full of weird greek letters and which typically pre-suppose what the reader does and doesn't know (things that are considered "trivial" by the author and not worth mentioning in the paper is often a huge obstacle for the reader to proceed with understanding what goes on). Code is explicit to the degree that a machine can execute it, and therefore often way easier as a path to understanding an idea. Publishing code also has the minor benefits of actually exposing things that are claimed to work but often don't - again because a machine can execute it whereas a math formula in a PDF does not have that nice property.
  - robinhouston 4y ago
    Oh, what a pain. Sorry. It looks as though Wolfram Cloud removes published notebooks after 60 days unless you pay extra. I’ve just republished it at https://www.wolframcloud.com/obj/robin.houston/Published/determinants.nb https://www.wolframcloud.com/obj/robin.houston/Published/det... I’d be interested to know whether the code _does_ make it easier for you to understand.
    - skyde 4y ago
      Thanks a lot for sharing the code. It does indeed make it order of magnitude easier for me to understand and validate my own theory and assumptions about it. For context when I was like 6 years old I was writing code in BASIC on a “TRS-80 Model III” to do linear algebra for fun (trying to make an arcade game). But never learned algebra until I was forced to at ~20 years old in university. So my understanding of mathematics was always mechanical (algorithm) and never very abstract. And it always was extremely hard to read research paper because the Greek letter don’t even mean the same thing in a (Statistic/ machine learning) paper and in a (physics/ calculus paper). And the author never properly define all the function and variables and assume you are already an expert.
zuzatm 4y ago
Minor comment: the improvement over the state-of-the-art is in the second order term of the exponent. Their formula express det. with B_n = exp( n ln n - n lnln n - O(n)) terms. The old formula had exp(n ln n - O(n)) terms. It's a nice bound, but won't change much for non-theoretical results.
scentoni 4y ago
A new explicit formula for the determinant that contains superexponentially fewer terms than the usual Leibniz formula
- esperent 4y ago
  What does "superexponentially fewer" mean?
  - quchen 4y ago
    »More than exponential«. The standard formula for determinants of an n×n matrix (equation 1 in the paper) is the sum of n! terms, one term for each permutation of {1..n}. The paper details a method (equation 11) in which the sum is instead over all what they call »partial partitions of {1..n}«, denoted PP(n). I don’t know the size of PP(n), but if their claim is correct then PP(n) has exponentially less elements than S(n) (which has n! elements). I don’t see the value of |PP(n)| in the paper, but if it’s O(n^42), that would be an example of something that’s superexponentially smaller/faster. (n! is approximately n^n/e^n, the Stirling Formula.)
    - robinhouston 4y ago
      > I don’t know the size of PP(n) There’s a bit of a subtlety here, which is that the formula evaluates to zero whenever the partial partition contains a singleton. For example, the partial partitions of {1,2,3} are: {} {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3} {1, 2} | {3} {1, 3} | {2} {1} | {2, 3} {1} | {2} | {3} but most of these contain a part that only has one element. For example {1} | {2, 3} has the singleton part {1}. Only five of them have no singleton part: {} {1, 2} {1, 3} {2, 3} {1, 2, 3} (In fact all five of these consist of just a single part, but that’s just an artifact of using such a small example. If there are more than three elements then we can have things like {1, 2} | {3, 4}.) In general the number of partial partitions of n elements that have no singleton parts is the n’th Bell number[0]. The Bell numbers grow much more slowly than the factorials, but still much faster than any polynomial. [0] https://en.wikipedia.org/wiki/Bell_number https://en.wikipedia.org/wiki/Bell_number
deleted 4y ago
[deleted]
ur-whale 4y ago
Very interesting, but ... another paper without code.
- kzrdude 4y ago
  I'm a layman, but this seems to be a very approachable presentation of a paper. Section titles are approachable and it has figures and graphics with geometric ideas.
  - psychphysic 4y ago
    And equation 12 shows an expansion of the formula given in eq11.
- zython 4y ago
  The code is trivial and left as an exercise to the reader. /s
  - quchen 4y ago
    This, but unironically. Their formula (11) involves basics (sums and products), the only nontrivial part would be the partial partitions, and for that the first paragraph of chapter 2 explains how to get it from ordinary partitions, which is a standard function.
  - ur-whale 4y ago
    > The code is trivial and left as an exercise to the reader. /s Yeah, the margin was probably not wide enough.
- zuzatm 4y ago
  I'd argue that the results of this paper are not meant to be implemented, hence no code required.
- beyondCritics 4y ago
  It's about higher math dude.

95 points by scentoni 4y ago

I'm sorry, I'm having a hard time parsing this paper. It looks like even calculating "partial partitions" is exponential. Have they found a nice polynomial time algorithm to find determinants or is this just an exponential algorithm but with fewer components than what is "traditional"? FYI, The Bareiss algorithm can calculate the determinant in polynomial time, including bounding the bit complexity to polynomial space [0]. [0] https://en.wikipedia.org/wiki/Bareiss_algorithm https://en.wikipedia.org/wiki/Bareiss_algorithm

steppi 4y ago
From my read of the paper. This new formula also gives an exponential time algorithm. It’s not of interest as a practical method for computing determinants. It does however have interesting geometric and combinatorial properties and they used it to give new bounds for the tensor rank and Waring rank of a determinant respectively. You can think of these ranks loosely as measures of the “complexity” of a determinant (but not in the sense of computational complexity). These ranks are of interest in pure mathematics but I can’t really say more about them because it’s been too many years since I’ve studied related math.

robinhouston 4y ago

Oh wow! I wasn’t expecting to see this on HN. I’m one of the authors of the paper, and I’m happy to answer any questions. (I’m sorry I didn’t see it earlier, it was posted in the middle of my night.) First of all, to clear up a possible misunderstanding: this new formula will not help you to compute determinants more quickly. The number of terms still grows a lot faster than polynomial, and if you just want to compute the determinant, there are polynomial-time algorithms for that. The best theoretical results on the complexity of computing determinants, that I know of, are in [0]. In practice you'd probably use Gaussian elimination, or maybe Bareiss for integers. Someone complained that there’s no code in the paper. Since it isn’t really useful for practical computation, I didn’t think code would be useful, but in fact it did start as a Mathematica program when I first discovered it. Adam Goucher (one of my co-authors) wrote a blog post on it [1] within a few days of its discovery, which links to my original Mathematica notebook. (Edit: ur-whale points out that the link to the Mathematica notebook no longer works. I have now republished it at [2].) [0] https://users.cs.duke.edu/~elk27/bibliography/04/KaVi04_2697263.pdf https://users.cs.duke.edu/~elk27/bibliography/04/KaVi04_2697... [1] https://cp4space.hatsya.com/2022/07/02/a-combinatorial-proof-of-houstons-identity/ https://cp4space.hatsya.com/2022/07/02/a-combinatorial-proof... [2] https://www.wolframcloud.com/obj/robin.houston/Published/determinants.nb https://www.wolframcloud.com/obj/robin.houston/Published/det...

ur-whale 4y ago
> Someone complained that there’s no code in the paper. That was me, apparently much to the dislike of a number of HNers :) Thank you very much for the pointer to the notebook although it is not easy to access, you seem to need a Wolfram account to get to it. [EDIT]: "Sorry, you do not have permission to access this item." after I logged into Wolfram ... > Since it isn’t really useful for practical computation, I didn’t think code would be useful This is a very common misconception. There is a large category of people out there (software engineers among other) that find it much easier to read code than reading abstract math formulas full of weird greek letters and which typically pre-suppose what the reader does and doesn't know (things that are considered "trivial" by the author and not worth mentioning in the paper is often a huge obstacle for the reader to proceed with understanding what goes on). Code is explicit to the degree that a machine can execute it, and therefore often way easier as a path to understanding an idea. Publishing code also has the minor benefits of actually exposing things that are claimed to work but often don't - again because a machine can execute it whereas a math formula in a PDF does not have that nice property.
- robinhouston 4y ago
  Oh, what a pain. Sorry. It looks as though Wolfram Cloud removes published notebooks after 60 days unless you pay extra. I’ve just republished it at https://www.wolframcloud.com/obj/robin.houston/Published/determinants.nb https://www.wolframcloud.com/obj/robin.houston/Published/det... I’d be interested to know whether the code _does_ make it easier for you to understand.
  - skyde 4y ago
    Thanks a lot for sharing the code. It does indeed make it order of magnitude easier for me to understand and validate my own theory and assumptions about it. For context when I was like 6 years old I was writing code in BASIC on a “TRS-80 Model III” to do linear algebra for fun (trying to make an arcade game). But never learned algebra until I was forced to at ~20 years old in university. So my understanding of mathematics was always mechanical (algorithm) and never very abstract. And it always was extremely hard to read research paper because the Greek letter don’t even mean the same thing in a (Statistic/ machine learning) paper and in a (physics/ calculus paper). And the author never properly define all the function and variables and assume you are already an expert.

zuzatm 4y ago

Minor comment: the improvement over the state-of-the-art is in the second order term of the exponent. Their formula express det. with B_n = exp( n ln n - n lnln n - O(n)) terms. The old formula had exp(n ln n - O(n)) terms. It's a nice bound, but won't change much for non-theoretical results.

scentoni 4y ago

A new explicit formula for the determinant that contains superexponentially fewer terms than the usual Leibniz formula

esperent 4y ago
What does "superexponentially fewer" mean?
- quchen 4y ago
  »More than exponential«. The standard formula for determinants of an n×n matrix (equation 1 in the paper) is the sum of n! terms, one term for each permutation of {1..n}. The paper details a method (equation 11) in which the sum is instead over all what they call »partial partitions of {1..n}«, denoted PP(n). I don’t know the size of PP(n), but if their claim is correct then PP(n) has exponentially less elements than S(n) (which has n! elements). I don’t see the value of |PP(n)| in the paper, but if it’s O(n^42), that would be an example of something that’s superexponentially smaller/faster. (n! is approximately n^n/e^n, the Stirling Formula.)
  - robinhouston 4y ago
    > I don’t know the size of PP(n) There’s a bit of a subtlety here, which is that the formula evaluates to zero whenever the partial partition contains a singleton. For example, the partial partitions of {1,2,3} are: {} {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3} {1, 2} | {3} {1, 3} | {2} {1} | {2, 3} {1} | {2} | {3} but most of these contain a part that only has one element. For example {1} | {2, 3} has the singleton part {1}. Only five of them have no singleton part: {} {1, 2} {1, 3} {2, 3} {1, 2, 3} (In fact all five of these consist of just a single part, but that’s just an artifact of using such a small example. If there are more than three elements then we can have things like {1, 2} | {3, 4}.) In general the number of partial partitions of n elements that have no singleton parts is the n’th Bell number[0]. The Bell numbers grow much more slowly than the factorials, but still much faster than any polynomial. [0] https://en.wikipedia.org/wiki/Bell_number https://en.wikipedia.org/wiki/Bell_number

deleted 4y ago

[deleted]

ur-whale 4y ago

Very interesting, but ... another paper without code.

kzrdude 4y ago
I'm a layman, but this seems to be a very approachable presentation of a paper. Section titles are approachable and it has figures and graphics with geometric ideas.
- psychphysic 4y ago
  And equation 12 shows an expansion of the formula given in eq11.
zython 4y ago
The code is trivial and left as an exercise to the reader. /s
- quchen 4y ago
  This, but unironically. Their formula (11) involves basics (sums and products), the only nontrivial part would be the partial partitions, and for that the first paragraph of chapter 2 explains how to get it from ordinary partitions, which is a standard function.
- ur-whale 4y ago
  > The code is trivial and left as an exercise to the reader. /s Yeah, the margin was probably not wide enough.
zuzatm 4y ago
I'd argue that the results of this paper are not meant to be implemented, hence no code required.
beyondCritics 4y ago
It's about higher math dude.