Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

It takes a long time to compute the summation below, and I'd like to know if there are some better ways to compute things faster. I have used $3$ ways to calculate, but they are very unsatisfactory. I have a list named cu with around $8000$ different members with all rational numbers, and I expect that Mathematica can give me a result with a reasonable time.

Clear[b, k, mu];
b[0] := 1;
b[k_] := ( b[k] = Sum[Binomial[k - 1, m - 1] cu[[m]] b[k - m], {m, 1, k}] );
AbsoluteTiming[ mu = ParallelTable[b[k], {k, 20}]; ]
(* {0.0090005, { ... } } *) 

As this recursive definition is not good in computing, I also try to use Faa di Bruno formula and Bell polynomial to calculate.

Clear[b, k, mu];
AbsoluteTiming[ mu = ParallelTable[BellY[Table[{1, cu[[n]]}, {n, k}]], {k, 20}]; ]
(* {0.0220012, { ... } } *)

0.02s are needed for only $20$ terms, then it will be too slow for all $5000$ terms. Hence I also think whether procedural programming implementation is useful.

Clear[b, k, mu];
AbsoluteTiming[ For[k = 1; mu = {}; mu[[0]] = 1, k <= 20, k++, 
mu = Append[mu, Sum[Binomial[k - 1, n - 1] cu[[n]] mu[[k - n]], {n, 1, k}]]]; ]
mu = List@Delete[mu, 0];
(* {0.0020001, ... } *)

Unfortunately, it is not good for more terms. Can anyone provide me some methods in Mathematica to calculate as quick as possible?

Thanks in advance.

share|improve this question
    
Are you sure whether you'll always get the right result when combining parallel-operations with memoization? –  Coolwater Mar 29 at 15:31
    
I have checked the results from all 3 ways and they are all equivalent. –  Karho Mar 29 at 15:58
    
Do you really need arbitrary precision? Just fiddling and converting to machine precision gets result ~10X faster. –  rasher Mar 30 at 0:47
    
It might help to add where this sum is from: did it come out of thin air, or is there some concrete problem you're trying to solve that might (probably) admit a smarter solution? E.g., there are some combinatorial objects floating in there, like Bell numbers (if all your entries were 1, the result for k is the kth Bell number which can be computed very quickly, a hint there may be a better way to skin this cat). –  rasher Mar 30 at 4:01
    
Clearly, I have asked about the sum is from different members, rather than the same 1 to get a Bell number. If not, I would not use BellY instead. –  Karho Mar 31 at 10:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.