3
$\begingroup$

After using Expand on the result of a calculation I get a long expression which is a sum of 8654461 terms (nearly 8.7 million). When I Export'ed the expression into an ascii txt file (I use Debian 9) its size is 1.3 gb.

My goal is to integrate each term, say with respect to angle x from 0 to 2$\pi$. Each term is simple (the reason why I Expand'ed in the first place) and easily integrated. However if I feed the entire expanded expression to Integrate, after many hours the kernel automatically quits with no output. I believe this is because of memory issues.

My question: What's an efficient way to manipulate a long expression term-by-term?

I have an expression which is a sum of terms: expr=f1[x]+f2[x]+f3[x]+... I tried extracting each term using expr[[i]] and then integrating each term inside a Table, but even this doesn't work, meaning it takes forever to integrate even the first term. I observed that it takes long to access expr[[i]] when i is large (>500). Is there a way to break up the expression easily into a list of terms so that then each element of the list may be accessed quickly? Or is there another way?

$\endgroup$
  • $\begingroup$ You can break the expression into a list: lst=List@@expr You can then split your list into shorter sublists using lst2=Partition[lst,n] where n is the length of the sublists. Be careful, it may be necessary to manually create one sublist, and cut it away before the partition operation is applied, such that partition can divide the rest into n equal parts. This may serve to have short lists that you may integrate during the one-day session, while the rest you leave for tomorrow. You may now apply Integrate to the sublist, say Map[Integrate[#,{x,a,b},assumptions]&,lst2[[1]] ] $\endgroup$ – Alexei Boulbitch Sep 5 '18 at 11:09
  • $\begingroup$ Continuation: will integrate each element of the first sublist lst2 from a to b with the assumptions. After you have integrated everything and collected the results into the list listInt you might apply Plus@@listInt and get the results. Is it what you wanted? On the other hand, your words that even the first integral takes too long to be evaluated gives me a suspicion that the primary problem is not in the length of the expression but maybe, in integration. I propose that you first check this. $\endgroup$ – Alexei Boulbitch Sep 5 '18 at 11:13
  • $\begingroup$ If expr is not itself modified during the evaluation, then there should be no problems accessing its elements, since an expression is (roughly speaking) an array of pointers, which are accessed by their position. Could you provide a minimal example of the code which takes long time to evaluate? $\endgroup$ – Anton.Sakovich Sep 5 '18 at 11:42
  • $\begingroup$ @AlexeiBoulbitch That's what I want. Why not post it as an answer? Also each term when given separately is quickly integrated, but when the entire expanded expression is fed in it takes long to evaluate (I checked using Monitor). Perhaps Integrate tries to simplify before it begins integration and that may be the cause of the delay. $\endgroup$ – Deep Sep 6 '18 at 5:10
  • $\begingroup$ @Anton.Sakovich Thanks for your comment. My code is long and complicated. You may take the example sum in m_goldberg's answer for some very large n. $\endgroup$ – Deep Sep 6 '18 at 5:12
2
$\begingroup$

I would like to elaborate on my comment here, because modifying large Lists in place is a common source of slow-downs.

I would say that the main rule of manipulating long expressions in Mathematica is not to allow Mathematica to evaluate them more then it is completely necessary. Let us consider the example of @m_goldberg for a large n:

n = 10^4;
sum = x^Range[n];
Do[sum[[i]] = Integrate[sum[[i]], x], {i, n}] // Timing
(*3.23438, Null}*)

It might seem strange, but just changing the head from List to HoldComplete leads to 40-times less time taken:

hsum = HoldComplete @@ sum;
Do[hsum[[i]] = Integrate[hsum[[i]], x], {i, n}] // Timing
(*{0.09375, Null}*)

This happens because HoldComplete does not check for UpValues. Every time Mathematica sees a "new" expression whose head is not HoldAllComplete, it will check UpValues of each of its arguments, which is an $O(n)$ operation, where $n$ is the length of the expression. Of course, Mathematica is optimized to "remember" what expressions have already been checked and have not been modified since then (more precisely, Mathemtica somehow marks expressions as "not modified form the last evaluation" using hashes as far as I understand). For this reason, this will also run fast:

Do[Integrate[sum[[i]], x], {i, n}] // Timing
(*{0.078125, Null}*)

After the first evaluation of sum Mathematica "memories" that all SubValues of sum's arguments have been checked and will not check them on later steps. This is not true if you modify sum during the evaluation: since sum has been modified, SubValues of its arguments need to be checked again.

But in (I hope) rare cases Mathematica can fail determining whether there is a need for evaluation, evaluating an expression even if it was not necessary, so one shouldn't rely on this feature too much.

Finally, the method proposed by @AlexeiBoulbitch does not involve modifying in place, and hence is efficient either.

psum = Partition[sum, n/10];
Do[
 Map[
  Integrate[#, x] &,
  psum[[i]]
],
{i, 1, 10}
]; // Timing
(*{0.078125, Null}*)

Although it requires extra memory for the partitioned list.

P.S

I am not a specialist in Integrate, but @AlexeiBoulbitch made an interesting remark, which is not related to handling long expressions but can be of use in your particular problem:

I have one more comment. You did not show your expressions and I do not know, if they may depend on parameters. In the latter case, there can be a situation that in different domains of the parametric space the integral has different values, while in some has no value at all. Typically, in such a situation it takes a long time to evaluate such an integral. If, however, you fix the domain in the parametric space by using Assumptions, it is fast

P.P.S.

All this SubValues story is not applicable to PackedArrays as long as you perform only numerical operations which do not unpack it. But in your case you clearly use a symbolic expression.

$\endgroup$
1
$\begingroup$

Consider the following:

A contrived sum.

n = 5;

sum = Plus @@ Table[x^i, {i, n}]
(* x + x^2 + x^3 + x^4 + x^5 *)

Now we will convert sum to a list, integrate each of the terms separately and convert the list back into a sum.

sum[[0]] = List; sum
(* {x, x^2, x^3, x^4, x^5} *)

Do[sum[[i]] = Integrate[sum[[i]], x], {i, n}]

sum[[0]] = Plus; sum
(* x^2/2 + x^3/3 + x^4/4 + x^5/5 + x^6/6 *)

The above code does all its operations in-place without making copies and, thus, conserves memory. Perhaps you can apply this technique to your problem.

$\endgroup$
  • $\begingroup$ This code might be extremely inefficient unless you use HoldComplete head instead of List. Compare Do[sum[[i]] = Integrate[sum[[i]], x], {i, n}] // Timing with Do[Integrate[sum[[i]], x], {i, n}] // Timing for a very large n. So, it is NOT the same as the approach proposed by @AlexeiBoulbitch $\endgroup$ – Anton.Sakovich Sep 6 '18 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.