De Boor's algorithm: Difference between revisions

Revision as of 10:04, 11 August 2017

Revision as of 13:03, 11 August 2017

Line 45:

== Optimizations ==

The algorithm above is not optimized for the implementation in a computer. It requires memory for <math> (p + 1) + p + \dots + 1 = (p + 1)(p + 2)/2 </math> temporary control points <math> \mathbf{d}_{i,r} </math>. Each temporary control points is written exactly once and read twice. By reversing the iteration over <math> i </math> (counting down instead of up), we can run the algorithm with memory for only <math> p + 1 </math> temporary control points, by letting <math> \mathbf{d}_{i,r} </math> reuse the memory cell for <math> \mathbf{d}_{i,r-1} </math>. Similarly, there is only one value of <math> \alpha </math> used in each step, so we can reuse the memory cell and drop theas indiceswell.

Furthermore, it is more convenient to use an index <math> j \in [0,p] </math> for the temporary control points. The relation to the previous index is <math> i = j + k - p </math>. Thus we obtain the improved algorithm:

Line 51:

Let <math> \mathbf{d}_{j} := \mathbf{c}_{j+k - p} </math> for <math> j = 0, \dots, p</math>. Iterate for <math> r = 1, \dots, p </math>:

:<math> \alphamathbf{d}_{j} := (1-\alpha_j) \fracmathbf{x-t_d}_{j-1} + k\alpha_j - p}}\mathbf{t_d}_{j+1+k-r}-t_{; \quad j+k-=p}}, \dots, r \quad </math> (<math> j </math> must be counted down)

:<math> \mathbf{d}_{j}alpha_j := (1-\alpha) \mathbffrac{d}_x-t_{j-1} + \alphak - \mathbf{dp}_}{t_{j+1+k-r}; \quad -t_{j=+k-p, \dots, r \quad}}. </math> (<math> j </math> must be counted down)

After the iterations are complete, the result is <math>\mathbf{S}(x) = \mathbf{d}_{p} </math>.