What to do when your research runs into a computationally challenging problem? - MathOverflow

What to do when your research runs into a computationally challenging problem?

2011-07-30T17:30:42Z

Occasionally, but more frequently lately, I would like to perform some hard computations. As an example, yesterday the following question came up:

What is the projective dimension of the edge ideal of the graph $G$ which is two complete bipartite graphs $K_{a,b}, K_{c,d}$ joined by another edge?

(I believe I can get the answer by hand, but a confirmation would be nice. Also, I wish to compute other similar examples).

For the above question, my personal computer crashed when $a=b=c=d=6$. I used Macaulay 2 with a special package for such situations: EdgeIdeals.

I have a few vague ideas on how to solve this: email people who are better at computations, try to find access to more powerful computers (a small fee is OK), or carefullly use MO (but may be that only works for people like Kevin Buzzard). Still:

What can one do in such situations?

I am looking for more generic answers (that can apply not only for the examples above, but in other situations). For example, a pointer to what powerful computers one can get access to would be helpful. Thank you!

Answer by Kevin Buzzard for What to do when your research runs into a computationally challenging problem?

2011-07-30T19:44:57Z

When faced with a computationally intractable problem, here's one way of making progress: give up!

Here's why giving up might turn out to be a good idea. Sometimes I feel "if I could just compute a few more spaces of modular forms/rings of integers in number fields/examples of whatever I'm thinking about, then perhaps I'd be in good shape". I am usually thinking this because I have tried some small examples, and then written a computer program to try some bigger examples, but I feel like I want more data and my computer says that this isn't going to happen any time soon.

But several times now, I have given up. I have walked away from the problem and mulled it over, and tried to proceed instead using pure thought. I learnt this idea from Brian Conrad, who was actually talking about a related issue. He once basically said to me "if someone proves something using pure thought, and someone else proves something else which contradicts it, using lots of calculations, then I can guess where the error will be". One thing that I took away from this was that it might not be the right idea always to do lots of calculations. In fact only recently I was thinking "if I could only compute some examples of reductions of certain crystalline representations in certain cases, I would have a clearer view of what was going on". I left a loop on, on my computer, which was going to take about a week to produce an answer. And during this time I thought about the question and solved it with pure thought. After the week my computer ran out of memory anyway.

So, and it's just a suggestion -- try pure thought instead. It won't always work, but when it does work it works better than computations, and it might save you from banging your head against a brick wall. Some computations are simply too hard for computers. And if pure thought doesn't work -- come back to it in a decade when computers are 50 times faster! And if someone with l33t computer sk1llz solves it on a computer first, then just figure that they were the ones who had the necessary skills to solve the problem and that's life. In fact, why not collaborate with such a person! I once wanted to prove some cases of Artin's conjecture which entailed computing a bunch of weight 5 modular forms. I couldn't do this -- but Bill Stein told me could, and so he wrote some code for computing modular forms, and we wrote a joint paper, and now the whole world has access to the code. Big win for everyone!

Answer by Noah Snyder for What to do when your research runs into a computationally challenging problem?

2011-07-30T21:33:46Z

You can purchase servers for however long you need them from Amazon. You can buy more or less cpu cycles/memory as necessary. I've never done it myself, so I can't tell you how it works, but Scott Morrison does it sometimes.

(Warning: My recollection from when Ben Webster was using Macaulay 2 for something in grad school is that there's a built-in hard limit (it was either 2 gigs or 4 gigs) on the amount of RAM that you can use in Macaulay 2. So buying more memory might not help you, without rewriting your program in something else (like the original Macaulay).)

Answer by Gwyn Whieldon for What to do when your research runs into a computationally challenging problem?

2011-07-30T22:53:41Z

Isn't this particular case easier to prove using the topology of the independence complexes of your $K_{n,m}$ and $K_{s,t}$?

$Ind(K_{n,m})$ is the disjoint union of an (n-1)-simplex and an (m-1)-simplex, and $Ind(K_{s,t})$ is the disjoint union of a (s-1)-simplex and a (t-1)-simplex. So the Stanley-Reisner complex of the disjoint union of those two graphs would be $\Delta=Ind(K_{n,m})\coprod Ind(K_{s,t})$ is the join of those two complexes, which is connected ($\dim\widetilde{H}_0(\Delta)$=0) and has $\dim\widetilde{H}_1(\Delta)=1$.

From Hochster's formula, this gives you a nonzero Betti number at homological stage n+m+s+t-2, so $pd(R/I)\geq n+m+s+t-2$. As this is the entire Stanley Reisner complex, and as the complex is connected, that's as high as the projective dimension could be.

This isn't quite the complex you wanted - but you'd just need to examine what happens to the join of the independence complexes of $K_{n,m}$ and $K_{s,t}$ after deleting the face ${v,w}$ corresponding to the edge you added between the graphs and all of the faces containing it. This complex still is connected and has $\dim \widetilde{H}_1(\Delta)=1$, so the projective dimension of both complexes is the same.

I guess a more general answer to this particular question though is - instead of computing the resolutions using edge ideals, you might consider using GAP to compute the homology of subcomplexes of your total complex of the appropriate size. These homology calculations combined with Hochster's formula are often better tools at proving projective dimension or regularity bounds than trying to resolve the ideals themselves.