[Date Index] [Thread Index] [Author Index]

Suggestions for improving speed

• To: mathgroup at smc.vnet.net
• Subject: [mg113304] Suggestions for improving speed
• From: Joe Hays <hays.joe at gmail.com>
• Date: Sat, 23 Oct 2010 07:04:10 -0400 (EDT)

Hello all,

Today I've been studying B-Splines. I know that Mathematica has a built-in
function to build the basis of a B-Spline but I wanted to better understand
it so I coded up my own following the "Cox-de Boor recursion formula" found
at: http://en.wikipedia.org/wiki/B-spline#Cubic_B-Spline

I tested it against Mathematica's version to make sure things were working
OK. After I got the right answer I timed the two implementations.
Mathematica's took ~ 0.12 seconds. My version took ~15.53 seconds. I
expected my implementation to be slower but not 125X slower!

I realize that I still approach things from the procedural point of view.
So, I thought I'd ask the Mathematica gurus if they see obvious coding
choices that cause the drastic slow down...

My tests were:

Given,

m=15;
n=3;
knots=Range[0,m-1]
j=3;
time=3.5;

Mathematica's version:
<snip>
tmpT=AbsoluteTime[];
Plot[Table[BSplineBasis[{n,knots},j,time],{j,0,m-n-2}],{time,0,m-1},
PlotRange->All]
AbsoluteTime[] - tmpT
</snip>

this took ~0.12 seconds

my version,
<snip>
tmpT=AbsoluteTime[];
Plot[Table[NthBasisRecursive[{n,knots},j,time],{j,0,m-n-2}],{time,0,m-1},
PlotRange->All]
AbsoluteTime[] - tmpT
</snip>

this took ~15.53 seconds

Now, for my code defining "NthBasisRecursive"

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

NthBasisRecursive[{n_, knots_}, j_, time_] :=
 Module[{jj, nn, myBasis, jIdx},
  myBasis = ConstantArray[0, {n + 1, n + 1}];

  For[nn = 1, nn <= n + 1, nn++,
   For[jj = 1, jj <= n + 1, jj++,

    jIdx = j + jj; (* Need to offset the knot indexing by the jth basis I'm
solving for *)

    If[nn == 1,
     If[knots[[jIdx]] <= time < knots[[jIdx + 1]],
       myBasis[[jj, nn]] = 1;
       ];
     ,

     If[(jj - 1) <= n - (nn - 1),
        myBasis[[jj, nn]] = (time - knots[[jIdx]])/(knots[[jIdx + nn - 1]] -
knots[[jIdx]])*myBasis[[jj, (nn - 1)]]
     +  (knots[[jIdx + nn]] -  time)/(knots[[jIdx + nn]] - knots[[jIdx +
1]])*myBasis[[(jj + 1), (nn - 1)]];
      ,
      ];(* end of inner IF *)
    ];(* end of outer IF *)

    ];(* end of JJ loop *)
   ];(* end of nn loop *)
  myBasis[[1, n + 1]]
  ]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Any insight to help me learn how to make things faster would be greatly
appreciated!

Joe