A Note on the Space Complexity of Fast D-Finite Function Evaluation
Supplementary material to the article by Marc Mezzarobba. CASC 2012.

Code

Experimental branch of NumGfun featuring a pure Maple implementation of the algorithm described the paper

• Work in progress, updated periodically
• Mostly works, but far from ready for general use
• Users are strongly advised to install the regular releases of NumGfun instead

Download

Experiments

We compare the performance of the above code (in blue) with those of the NumGfun mainline (in black), which uses regular binary splitting without truncations. The graphs shown below correspond to the following test case, with 1 ≤ k ≤ 100:

            diffeq := {
                (13/30+8/15*z+7/30*z^2)*y(z)
                +(-9/20+29/30*z-1/12*z^2)*diff(y(z),z)
                +(-43/60+49/60*z+11/30*z^2)*diff(y(z),z,z)
                +(-7/12+17/30*z-3/5*z^2)*diff(y(z),z,z,z),
                y(0)=0, D(y)(0)=7/30, D(D(y))(0)=-43/60};
            evaldiffeq(diffeq, y(z), 1/5, k*1000);
        

The measurements were done using CodeTools[Usage] under Maple 15.

The provisional conclusion is that a lower-level implementation (with explicit memory management in the critical steps) seems to be necessary to see the benefits of the algorithm.

Total memory usage

Values (bytes):

Ratios:

Memory allocations

Values (bytes):

Ratios:

CPU time

Values (seconds):

Ratios: