Iterative Calculations Query - How long do they usually take?

Hi,

Slightly random query and I'm posting it here and not on one of the specific forums as it's not a problem that I can't solve (it's a case of how long does something typically take?).

In short, I have two essentially recursive loops set up in a spreadsheet (with two worksheets - the loops effectively tie the sheets together) and I am using a find and replace to trip one of the loops and force it run some iterations to solve a problem. I know the maths is good as I've spent long enough doing this and had plenty of problems on the way (with things not converging - but the numbers when I have tried it appear to be converging and moving in both directions etc. - and not one direction as they had done previously and hence not converging).

Basically I have ratings against 739 teams, and just under 8000 games to work the iterations through (to derive new ratings for the 739 teams) and I was wondering typically how long does a calculation process like this take? I have iterations set to 10000, and max change to 0.001, and I've stopped it running after about 3 hours and only 400-450 iterations. I'm wondering if my laptop is too old and somewhat cranky (a 7 year old last of the Power PC's Mac) to be doing this (e.g. should it normally take over 3 hours for this level of calculation or long should something like this take)?

Any advice or suggestions (or this will take more than 8 hours type experiences of past exploits) would be greatly appreciated,

I know very little about computer benchmarking and such, but maybe this will help.

First, I don't know that there is a "typical" iterative problem, so I don't think this can really be answered as if there is a single answer. For comparison, the iterative calculations that I set up (completely different kind of problem) tend to require 5-20 iterations to converge over 5-20 data points. In these cases, a full recalculate probably takes about 1 second (my machine is running 4 3.2 GHz processors). If I scale it up to ~1000 data points, it takes 5 to 10 s.

The description of your problem indicates that your problem needs 1000's of iterations (~100x mine) over 1000's of data points (~10x my scaled up version). Maybe a reasonable first guess for your problem (all else being equal, which it almost certainly isn't) is 1000x as long (5000-10000 seconds or 1.5 to 3 hours).

Suggestions: certainly a faster machine won't hurt. The only other suggestion is to find or come up with a much more efficient algorithm (though developing a new algorithm can take longer than just letting the old algorithm run).

Thanks for the suggestions - it is very helpful. I have access to another newer machine (which hopefully should be faster - I'm not convinced that it actually is though) and will give it a go on that. I have also made a shorter version of the sheet where I have taken out the last 6-7 weeks of the season to halve the number of games. With that number of games and only working off of 199 teams (I didn't have access to all of the relevant games at the time and the other 540 teams so it would have been less "game" lines) it took standard solver about 45 minutes to "solve" a similar problem.

Re: changing the algorithm - I totally get the point but don't think it is a viable option (I had trouble enough with this one - basically I struggle with the maths but get processes, I have been looking at this on and off for a couple of months and only worked out this week I had two columns the wrong way round which is why it hadn't converged up and until now). Usually I use Solver to do this kind of thing, but with 739 teams (and hence variables) I am above the variable limit, and the other way that I have for doing this by matrix's (it would work in a similar way and get a similar result) would be awkward (I struggled to build a 32x32 matrix - 739x739 would be very time consuming).

Thanks for the suggestions though and it's good to get a feeling of how quickly other people's iterations go. I suspect my laptop may be a touch cranky and old.

Re: just a follow up on this - in short I need to get a faster computer. The maths behind this (I don't do the maths but I get the processes), essentially worked the solver process iteratively with a few tweaks (I hadn't allowed for homefield advantage in the iterative process - yet, and as a result it was fractionally off my solver process - on average it was accurate to 7dp, with a worst case out by 0.15). The matrix ways of solving this (not allowing for homefield advantage) was out by on average 0.09 (with a worst case of about 2.92).

In the example above I tried it on a different sport with smaller criteria just to see how long it took (32 teams, 320-ish game lines), solver solved it in about a minute, the iterative process solved it in about a minute (matrix methods once you had copied the numbers into the matrix's - it solved them within a minute), therefore given my computers speed with 739 teams, and approx.8000 games lines we will genuinely be talking hours (as a 739x739 matrix isn't feasible - easily, and I'm not getting industrial solver just to rate sports for fun).

Incidentally I attached the end values for anyone interested - power ratings essentially going into week 12 of this year's NFL season. The area highlighted yellow was solving iteratively and the process I was interested in (breaking out average margin of victory values, and strength of schedule - not allowing for homefield advantage capping or weighting), green was least squares (allowing for homefield advantage but no weighting or capping), red was two matrix based method (not allowing for homefield advantage or capping or weighting).

Values Test into Week 12.xls

Just a quick rounding this one off (I think) I now have a confirmed solution on the problem, as I've got a timescale for someone running a similar sized problem on a newer machine;

My 7 year old last of the Power PC's Mac Powerbook with Excel 2004; 3-4 hours.

A less than 2 year old (don't know the specific date) Lenovo laptop running Excel 2010; 2 minutes.

I'm figuring my friend had the benefits of a newer machine and the benefits of improved calculation methods within the newer version of Excel? I'm not sure if we had the same max change settings but either way if he went to 3 dp and I went to 5 it wouldn't make 3 hours+ difference. I'd be grateful for any second opinions on this but it looks conclusive (I think)?