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

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!

• Some services offer CPU cycles in the cloud. You and 200 of your closest friends can try breaking up the problem and running it in parallel on the free accounts. Gerhard "Flying High In The Sky" Paseman, 2011.07.30 Jul 30, 2011 at 18:10
• Dear Gerhard, that sounds like a great answer. Can you elaborate more on the how to find "200 closest friends" part? (-: Jul 30, 2011 at 18:34
• @Gerhard, Steve: Could one of you write down an answer please? I only know to email and Tex, so this is a bit hard for me to decipher. Jul 30, 2011 at 19:36
• Do a web search on cloud computing. Some companies offer an account with a free instance (something like 256mb ram and x number of GHz cpu) that you can use. Check the charges for bandwidth both in and out of the cloud though. As for friends, advertise on your MathOverflow user page. If you want ideas on parallelizing your problem, I take cash or Starbucks cards or reputation on MathOverflow. Gerhard "Will Also Barter For PDFs" Paseman, 2011.07.30 Jul 30, 2011 at 20:40
• Long: Here's a case where I've been unable to use Kevin's advice. Let f be the element x^3+y^3+xyz of A=Z/p[x,y,z]. I'd like to know how the colength of the ideal generated by f^k and the q'th powers of x,y and z depends on k and q when q is a power of p. As you know I've a conjecture when p=2 that would imply algebraicity of some H.K multiplicities and transcendence of some others. But I can't prove much. When p=3 I can't figure out what the pattern is--maybe if I could just push the computer a little harder...? Jul 31, 2011 at 10:22

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!

• Dear Kevin, this is a great advice, and I am nodding my head furiously reading it. But what if you do not know what the answer might be? For example, suppose I know in the example above (by pure thoughts) that the dimension is either $2(a+b+c+d) -2$ or $2(a+b+c+d)-3$, but no conjecture of when each one is right, isn't computing a couple of examples really helpful? Jul 30, 2011 at 19:55
• And of course +1 Jul 30, 2011 at 19:56
• May I also point out that Brian Conrad's and your thoughts are likely much purer than mine! Jul 30, 2011 at 20:11
• You've used pure thought to eliminate all but two numbers. Of course I don't understand the problem, but I am proposing that you don't rule out using more pure thought to eliminate one of the remaining possibilities. Of course this might not be possible. For all I know it might be super-hard. But if it's hard pure thought vs hard computation, then go for the hard pure thought because it's better for the soul. Why not do examples with a,b,c,d much much smaller, try and spot a pattern, and then pounce with the pure thought? Let me stress that I have no idea what the question is! I'm just... Jul 30, 2011 at 20:11
• Giving up is often (a component of) good strategy in general. Not only does it free you to trying other approaches to your present problem (whether it's a matter of computation vs. "pure thought" or otherwise), but taking a longer view it may free you from beating your head against one surprisingly hard problem to make progress on other problems of comparable importance that you may find more tractable.  The trick is not quitting either too early or too late... Jul 31, 2011 at 2:38

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.

• Sometimes picking the right CAS system to hit the problem with is a better bet. While having multiple threads of M2 running at the same time or parallelizing the problem is a good approach, I think computing resolutions of these ideals directly (most of my work has been in bounding invariants of resolutions of edge ideals) by splitting up the computation is harder than it sounds. Jul 30, 2011 at 22:59
• Dear Gwyn, thank you for the very elegant solution. $a+b+c+d-2$ is also what I got, although much less prettily. In general, my understanding is that to use Hochster's formula to compute the exact proj. dim. one needs to know all the subcomplexes of the independent complex. So the homology of the whole ind. complex can provide quick lower bound, and in this case it is enough. But for more general graphs, can you use this methods to compute the exact projective dimension? Your insight would be much appreciated. Jul 31, 2011 at 1:26
• True, normally the calculation requires more consideration of subcomplexes. That was the "of the appropriate size" comment. For a general edge ideal on n vertices, the projective dimension is at most n-1 (and is precisely = n-1 if the Stanley-Reisner complex is disconnected.) This follows from checking possible Betti numbers via Hochster's formula. To prove that pd(R/I)=k < n-1, you'd need to show two things: (continued) Jul 31, 2011 at 1:54
• (1) That every subcomplex on a vertex set of size k+2 through n is connected, every subcomplex on a vertex set of size k+3 through n has no first homology, every subcomplex on a vertex set of size k+4 through n has no second homology and so on. (2) That there exists some subcomplex on a vertex set of size k+1 which is disconnected, or that there exists some subcomplex on a vertex set of size k+2 which has nontrivial first homology or... Etc. This becomes difficult. (Replace "ith homology is zero on a vertex set of size j" throughout with $\dim(\widetilde{H}_i(\Delta|_{W})=0$ with $|W|=j$.) Jul 31, 2011 at 1:59
• It was easy in the case above since the projective dimension was "hit" by a subcomplex on vertex size k+2=n (where n=total # of vertices) and the complex was connected. Jul 31, 2011 at 2:00

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

• Dear Noah: Thanks a lot, I had no idea such a thing exist. Your warning is also very helpful. Jul 31, 2011 at 1:28