Try seeing what ulimit reports. The exact output and syntax varies, but for bash on a RH 7.1 box says:

$ ulimit -a
core file size (blocks)     1000000
data seg size (kbytes)      unlimited
file size (blocks)          unlimited
max locked memory (kbytes)  unlimited
max memory size (kbytes)    unlimited
open files                  1024
pipe size (512 bytes)       8
stack size (kbytes)         8192
cpu time (seconds)          unlimited
max user processes          10190
virtual memory (kbytes)     unlimited
[download]

It wouldn't be surprising if they've got CPU time throttled from what you're saying. If this is the case and the limits are applied to all Apache children, then you'll either have to talk them into upping your limit or have the CGI submit the request to something else that's not running under such limits (i.e. have a persistent process not started from Apache which does the calculations and stores the results for later retrieval).