Mrthfx

Mapping a list into a phase plot

Is there an Impartial Brexit Deal comparison site?

Curses work by shouting - How to avoid collateral damage?

Best way to store options for panels

Modify casing of marked letters

How does residential electricity work?

Products and sum of cubes in Fibonacci

How can I replace every global instance of "x[2]" with "x_2"

Is a roofing delivery truck likely to crack my driveway slab?

Displaying the order of the columns of a table

Is there a good way to store credentials outside of a password manager?

Time travel short story where a man arrives in the late 19th century in a time machine and then sends the machine back into the past

The baby cries all morning

What is the intuitive meaning of having a linear relationship between the logs of two variables?

Is the destination of a commercial flight important for the pilot?

voltage of sounds of mp3files

How to be diplomatic in refusing to write code that breaches the privacy of our users

How do I keep an essay about "feeling flat" from feeling flat?

Where in the Bible does the greeting ("Dominus Vobiscum") used at Mass come from?

Implement the Thanos sorting algorithm

HashMap containsKey() returns false although hashCode() and equals() are true

The plural of 'stomach"

How does a character multiclassing into warlock get a focus?

Is it correct to write "is not focus on"?

Ways to speed up user implemented RK4

Speed up Numerical IntegrationSpeed of convergence for NIntegrateTough Calculation, novice mathematica userNumerical integration's speedNumerical integral speedImprove the speed of Gaussian quadrature integrationSolving an unstable BVP numerically, accurately and efficientlyHow to speed up integral of results of PDE modelSolve BVP involving user defined functionUser defined ArcTan function

3

1

$begingroup$

So, I've implemented RK4, and I'm wondering what I can do to make it more efficient? What I've got so far is below. I wish to still record all steps. I think AppendTo is doing the most damage to the time, is there a faster alternative?

rk4[f_, variables_, valtinit_, tinit_, tfinal_, nsteps_] := 

  Module[{table, xlist, ylist, step, k1, k2, k3, k4}, 

   xlist = tinit;

   step = N[(tfinal - tinit)/(nsteps)];

   ylist = valtinit;

   table = {{xlist, ylist}};

   Table[

    k1 = step* f /. MapThread[Rule, {variables, ylist}]; (* 

    Equivalent to step* f/.Thread[Rule[variables,ylist]]*)

    k2 = step*f /. MapThread[Rule, {variables, k1/2 + ylist}];

    k3 = step*f /. MapThread[Rule, {variables, k2/2 + ylist}];

    k4 = step*f /. MapThread[Rule, {variables, k3 + ylist}];

    ylist += 1/6 (k1 + 2 (k2 + k3) + k4);

    xlist += step;

    AppendTo[table, {xlist, ylist}];

    {xlist, ylist}, nsteps];

   table

   ];

Example Input:

funclist = {-x + y, x - y};

initials = {1, 2};

variables = {x, y};

init = 0;

final = 200;

nstep = 20000;

approx = rk4[funclist, variables, initials, init, final, nstep]//AbsoluteTiming;

{3.59932,{...}}

I'd love some suggestions!

differential-equations numerical-integration

share|improve this question

asked 3 hours ago

ShinaolordShinaolord

808

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  AppendTo is quadratic time complexity. Might be better to preallocate and set by index. Also it'll be much faster to not use Rule and instead code stuff up a little bit more explicitly. As a general rule, too, use vectorized operators. Those can be very fast. And if everything can be totally functional over "packed arrays" (look them up here) it'll be very quick too.
  $endgroup$
  – b3m2a1
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'll work on implementing it more explicity, this is what came to find first though. It'll require some changes to the inputs, I'll have to ponder this. And preallocating the list is a quick change that won't be an issue to do, I can't believe I forgot that's faster :(. Thanks though!
  $endgroup$
  – Shinaolord
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Shinaoloard, using Join[ {{xlist, ylist}}, Table[ k1 = step*f /. MapThread[Rule, {variables, ylist}]; k2 = step*f /. MapThread[Rule, {variables, k1/2 + ylist}]; k3 = step*f /. MapThread[Rule, {variables, k2/2 + ylist}]; k4 = step*f /. MapThread[Rule, {variables, k3 + ylist}]; ylist += 1/6 (k1 + 2 (k2 + k3) + k4); xlist += step; {xlist, ylist}, nsteps ] ] as return value is already a first step. There is no point in appending if you use a Table anyways.
  $endgroup$
  – Henrik Schumacher
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @HenrikSchumacher do you think it would be faster to Pre-allocate a list of length nsteps, and append the values, or to join the values using table? I can obviously change Table to Do to remove the time it takes to make the table list, going by b3m2a1's method, or I could use Join as you have suggested. I'm thinking your method may be faster, though. I've already removed the MapThread part, I am testing the speed increase granted by that at the moment. Just curious which path you think will be faster.
  $endgroup$
  – Shinaolord
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am currently testing the speed difference between the one in the post and rk4t2[f_, valtinit_, tinit_, tfinal_, nsteps_] := Module[{test, table, xlist, ylist, step, k1, k2, k3, k4}, xlist = tinit; step = N[(tfinal - tinit)/(nsteps)]; ylist = valtinit; table = {{xlist, ylist}}; test = Table[ k1 = step* f[ylist] ; k2 = step*f[k1/2 + ylist]; k3 = step*f[k2/2 + ylist]; k4 = step*f[k3 + ylist]; ylist += 1/6 (k1 + 2 (k2 + k3) + k4); xlist += step; {xlist, ylist}, nsteps]; Join[table, test] ];
  $endgroup$
  – Shinaolord
  2 hours ago
  

  
  
  
  

 | 
show 1 more comment

3

1

$begingroup$

So, I've implemented RK4, and I'm wondering what I can do to make it more efficient? What I've got so far is below. I wish to still record all steps. I think AppendTo is doing the most damage to the time, is there a faster alternative?

rk4[f_, variables_, valtinit_, tinit_, tfinal_, nsteps_] := 

  Module[{table, xlist, ylist, step, k1, k2, k3, k4}, 

   xlist = tinit;

   step = N[(tfinal - tinit)/(nsteps)];

   ylist = valtinit;

   table = {{xlist, ylist}};

   Table[

    k1 = step* f /. MapThread[Rule, {variables, ylist}]; (* 

    Equivalent to step* f/.Thread[Rule[variables,ylist]]*)

    k2 = step*f /. MapThread[Rule, {variables, k1/2 + ylist}];

    k3 = step*f /. MapThread[Rule, {variables, k2/2 + ylist}];

    k4 = step*f /. MapThread[Rule, {variables, k3 + ylist}];

    ylist += 1/6 (k1 + 2 (k2 + k3) + k4);

    xlist += step;

    AppendTo[table, {xlist, ylist}];

    {xlist, ylist}, nsteps];

   table

   ];

Example Input:

funclist = {-x + y, x - y};

initials = {1, 2};

variables = {x, y};

init = 0;

final = 200;

nstep = 20000;

approx = rk4[funclist, variables, initials, init, final, nstep]//AbsoluteTiming;

{3.59932,{...}}

I'd love some suggestions!

differential-equations numerical-integration

share|improve this question

asked 3 hours ago

ShinaolordShinaolord

808

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  AppendTo is quadratic time complexity. Might be better to preallocate and set by index. Also it'll be much faster to not use Rule and instead code stuff up a little bit more explicitly. As a general rule, too, use vectorized operators. Those can be very fast. And if everything can be totally functional over "packed arrays" (look them up here) it'll be very quick too.
  $endgroup$
  – b3m2a1
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'll work on implementing it more explicity, this is what came to find first though. It'll require some changes to the inputs, I'll have to ponder this. And preallocating the list is a quick change that won't be an issue to do, I can't believe I forgot that's faster :(. Thanks though!
  $endgroup$
  – Shinaolord
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Shinaoloard, using Join[ {{xlist, ylist}}, Table[ k1 = step*f /. MapThread[Rule, {variables, ylist}]; k2 = step*f /. MapThread[Rule, {variables, k1/2 + ylist}]; k3 = step*f /. MapThread[Rule, {variables, k2/2 + ylist}]; k4 = step*f /. MapThread[Rule, {variables, k3 + ylist}]; ylist += 1/6 (k1 + 2 (k2 + k3) + k4); xlist += step; {xlist, ylist}, nsteps ] ] as return value is already a first step. There is no point in appending if you use a Table anyways.
  $endgroup$
  – Henrik Schumacher
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @HenrikSchumacher do you think it would be faster to Pre-allocate a list of length nsteps, and append the values, or to join the values using table? I can obviously change Table to Do to remove the time it takes to make the table list, going by b3m2a1's method, or I could use Join as you have suggested. I'm thinking your method may be faster, though. I've already removed the MapThread part, I am testing the speed increase granted by that at the moment. Just curious which path you think will be faster.
  $endgroup$
  – Shinaolord
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am currently testing the speed difference between the one in the post and rk4t2[f_, valtinit_, tinit_, tfinal_, nsteps_] := Module[{test, table, xlist, ylist, step, k1, k2, k3, k4}, xlist = tinit; step = N[(tfinal - tinit)/(nsteps)]; ylist = valtinit; table = {{xlist, ylist}}; test = Table[ k1 = step* f[ylist] ; k2 = step*f[k1/2 + ylist]; k3 = step*f[k2/2 + ylist]; k4 = step*f[k3 + ylist]; ylist += 1/6 (k1 + 2 (k2 + k3) + k4); xlist += step; {xlist, ylist}, nsteps]; Join[table, test] ];
  $endgroup$
  – Shinaolord
  2 hours ago
  

  
  
  
  

 | 
show 1 more comment

$begingroup$

So, I've implemented RK4, and I'm wondering what I can do to make it more efficient? What I've got so far is below. I wish to still record all steps. I think AppendTo is doing the most damage to the time, is there a faster alternative?

rk4[f_, variables_, valtinit_, tinit_, tfinal_, nsteps_] := 

  Module[{table, xlist, ylist, step, k1, k2, k3, k4}, 

   xlist = tinit;

   step = N[(tfinal - tinit)/(nsteps)];

   ylist = valtinit;

   table = {{xlist, ylist}};

   Table[

    k1 = step* f /. MapThread[Rule, {variables, ylist}]; (* 

    Equivalent to step* f/.Thread[Rule[variables,ylist]]*)

    k2 = step*f /. MapThread[Rule, {variables, k1/2 + ylist}];

    k3 = step*f /. MapThread[Rule, {variables, k2/2 + ylist}];

    k4 = step*f /. MapThread[Rule, {variables, k3 + ylist}];

    ylist += 1/6 (k1 + 2 (k2 + k3) + k4);

    xlist += step;

    AppendTo[table, {xlist, ylist}];

    {xlist, ylist}, nsteps];

   table

   ];

Example Input:

funclist = {-x + y, x - y};

initials = {1, 2};

variables = {x, y};

init = 0;

final = 200;

nstep = 20000;

approx = rk4[funclist, variables, initials, init, final, nstep]//AbsoluteTiming;

{3.59932,{...}}

I'd love some suggestions!

differential-equations numerical-integration

share|improve this question

asked 3 hours ago

ShinaolordShinaolord

808

$endgroup$

rk4[f_, variables_, valtinit_, tinit_, tfinal_, nsteps_] := 

  Module[{table, xlist, ylist, step, k1, k2, k3, k4}, 

   xlist = tinit;

   step = N[(tfinal - tinit)/(nsteps)];

   ylist = valtinit;

   table = {{xlist, ylist}};

   Table[

    k1 = step* f /. MapThread[Rule, {variables, ylist}]; (* 

    Equivalent to step* f/.Thread[Rule[variables,ylist]]*)

    k2 = step*f /. MapThread[Rule, {variables, k1/2 + ylist}];

    k3 = step*f /. MapThread[Rule, {variables, k2/2 + ylist}];

    k4 = step*f /. MapThread[Rule, {variables, k3 + ylist}];

    ylist += 1/6 (k1 + 2 (k2 + k3) + k4);

    xlist += step;

    AppendTo[table, {xlist, ylist}];

    {xlist, ylist}, nsteps];

   table

   ];

funclist = {-x + y, x - y};

initials = {1, 2};

variables = {x, y};

init = 0;

final = 200;

nstep = 20000;

approx = rk4[funclist, variables, initials, init, final, nstep]//AbsoluteTiming;

share|improve this question

asked 3 hours ago

ShinaolordShinaolord

808

share|improve this question

asked 3 hours ago

ShinaolordShinaolord

808

asked 3 hours ago

ShinaolordShinaolord

808

asked 3 hours ago

ShinaolordShinaolord

808

1 Answer
1

active

oldest

votes

4

$begingroup$

Just to give you an impression how fast things may get when you use the right tools.

For given stepsize τ and given vectorfield F, this creates a CompiledFunction cStep that computes a single Runge-Kutta step

F = X [Function] {-Indexed[X, 2], Indexed[X, 1]};



τ = 0.01;

Block[{YY, Y, k1, k2, k3, k4},



  YY = Table[Compile`GetElement[Y, i], {i, 1, 2}];

  k1 = τ F[YY];

  k2 = τ F[0.5 k1 + YY];

  k3 = τ F[0.5 k2 + YY];

  k4 = τ F[k3 + YY];



  cStep = With[{code = YY + (k1 + 2. (k2 + k3) + k4)/6. },

    Compile[{{Y, _Real, 1}},

     code,

     CompilationTarget -> "C",

     RuntimeOptions -> "Speed"

     ]

    ]

  ];

Now we can apply it 2 million times with NestList and still need only 2 seconds.

nsteps = 20000000;

xlist = Range[0., step nsteps, step];

Ylist = NestList[cStep, initials, nsteps]; // AbsoluteTiming // First

2.08678

share|improve this answer

answered 2 hours ago

Henrik SchumacherHenrik Schumacher

57.9k579159

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Damn, you definitely know how to use Mathematica A LOT more efficiently than I do. Thanks!
  $endgroup$
  – Shinaolord
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You're welcome.
  $endgroup$
  – Henrik Schumacher
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'll have to play around with Compile, it definitely seems like a massive speed up if used correctly.
  $endgroup$
  – Shinaolord
  2 hours ago
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "387"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f194002%2fways-to-speed-up-user-implemented-rk4%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

Just to give you an impression how fast things may get when you use the right tools.

For given stepsize τ and given vectorfield F, this creates a CompiledFunction cStep that computes a single Runge-Kutta step

F = X [Function] {-Indexed[X, 2], Indexed[X, 1]};



τ = 0.01;

Block[{YY, Y, k1, k2, k3, k4},



  YY = Table[Compile`GetElement[Y, i], {i, 1, 2}];

  k1 = τ F[YY];

  k2 = τ F[0.5 k1 + YY];

  k3 = τ F[0.5 k2 + YY];

  k4 = τ F[k3 + YY];



  cStep = With[{code = YY + (k1 + 2. (k2 + k3) + k4)/6. },

    Compile[{{Y, _Real, 1}},

     code,

     CompilationTarget -> "C",

     RuntimeOptions -> "Speed"

     ]

    ]

  ];

Now we can apply it 2 million times with NestList and still need only 2 seconds.

nsteps = 20000000;

xlist = Range[0., step nsteps, step];

Ylist = NestList[cStep, initials, nsteps]; // AbsoluteTiming // First

2.08678

share|improve this answer

answered 2 hours ago

Henrik SchumacherHenrik Schumacher

57.9k579159

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Damn, you definitely know how to use Mathematica A LOT more efficiently than I do. Thanks!
  $endgroup$
  – Shinaolord
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You're welcome.
  $endgroup$
  – Henrik Schumacher
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'll have to play around with Compile, it definitely seems like a massive speed up if used correctly.
  $endgroup$
  – Shinaolord
  2 hours ago
  

  
  
  
  

add a comment | 

4

$begingroup$

Just to give you an impression how fast things may get when you use the right tools.

For given stepsize τ and given vectorfield F, this creates a CompiledFunction cStep that computes a single Runge-Kutta step

F = X [Function] {-Indexed[X, 2], Indexed[X, 1]};



τ = 0.01;

Block[{YY, Y, k1, k2, k3, k4},



  YY = Table[Compile`GetElement[Y, i], {i, 1, 2}];

  k1 = τ F[YY];

  k2 = τ F[0.5 k1 + YY];

  k3 = τ F[0.5 k2 + YY];

  k4 = τ F[k3 + YY];



  cStep = With[{code = YY + (k1 + 2. (k2 + k3) + k4)/6. },

    Compile[{{Y, _Real, 1}},

     code,

     CompilationTarget -> "C",

     RuntimeOptions -> "Speed"

     ]

    ]

  ];

Now we can apply it 2 million times with NestList and still need only 2 seconds.

nsteps = 20000000;

xlist = Range[0., step nsteps, step];

Ylist = NestList[cStep, initials, nsteps]; // AbsoluteTiming // First

2.08678

share|improve this answer

answered 2 hours ago

Henrik SchumacherHenrik Schumacher

57.9k579159

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Damn, you definitely know how to use Mathematica A LOT more efficiently than I do. Thanks!
  $endgroup$
  – Shinaolord
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You're welcome.
  $endgroup$
  – Henrik Schumacher
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'll have to play around with Compile, it definitely seems like a massive speed up if used correctly.
  $endgroup$
  – Shinaolord
  2 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

Just to give you an impression how fast things may get when you use the right tools.

For given stepsize τ and given vectorfield F, this creates a CompiledFunction cStep that computes a single Runge-Kutta step

F = X [Function] {-Indexed[X, 2], Indexed[X, 1]};



τ = 0.01;

Block[{YY, Y, k1, k2, k3, k4},



  YY = Table[Compile`GetElement[Y, i], {i, 1, 2}];

  k1 = τ F[YY];

  k2 = τ F[0.5 k1 + YY];

  k3 = τ F[0.5 k2 + YY];

  k4 = τ F[k3 + YY];



  cStep = With[{code = YY + (k1 + 2. (k2 + k3) + k4)/6. },

    Compile[{{Y, _Real, 1}},

     code,

     CompilationTarget -> "C",

     RuntimeOptions -> "Speed"

     ]

    ]

  ];

Now we can apply it 2 million times with NestList and still need only 2 seconds.

nsteps = 20000000;

xlist = Range[0., step nsteps, step];

Ylist = NestList[cStep, initials, nsteps]; // AbsoluteTiming // First

2.08678

share|improve this answer

answered 2 hours ago

Henrik SchumacherHenrik Schumacher

57.9k579159

$endgroup$

F = X [Function] {-Indexed[X, 2], Indexed[X, 1]};



τ = 0.01;

Block[{YY, Y, k1, k2, k3, k4},



  YY = Table[Compile`GetElement[Y, i], {i, 1, 2}];

  k1 = τ F[YY];

  k2 = τ F[0.5 k1 + YY];

  k3 = τ F[0.5 k2 + YY];

  k4 = τ F[k3 + YY];



  cStep = With[{code = YY + (k1 + 2. (k2 + k3) + k4)/6. },

    Compile[{{Y, _Real, 1}},

     code,

     CompilationTarget -> "C",

     RuntimeOptions -> "Speed"

     ]

    ]

  ];

nsteps = 20000000;

xlist = Range[0., step nsteps, step];

Ylist = NestList[cStep, initials, nsteps]; // AbsoluteTiming // First

share|improve this answer

answered 2 hours ago

Henrik SchumacherHenrik Schumacher

57.9k579159

answered 2 hours ago

Henrik SchumacherHenrik Schumacher

57.9k579159

answered 2 hours ago

Henrik SchumacherHenrik Schumacher

57.9k579159