
Parallel monotone spline interpolation and approximation on GPUs 305
i replaces the value y
k
, k ≥ i if P
ij
< y
i
. Now, if two threads i
1
and i
2
need
to replace y
k
, and i
1
< i
2
, we must have P
i
1
j
1
≥ P
i
2
j
2
, as formalized in the
following.
Proposition 1 If partial averages P
ij
are defined by (12.1) and i
1
< i
2
,
j
1
, j
2
≥ i
1
, i
2
, where j
1
, j
2
denote the minimizers of P
i
1
j
over j ≥ i
1
(respec-
tively P
i
2
j
over j ≥ i
2
), then P
i
1
j
1
≥ P
i
2
j
2
.
Proof 1 Because the average satisfies
1
k
k
X
i=1
y
i
≥
1
n − k
n
X
i=k+1
y
i
⇒
1
k
k
X
i=1
y
i
≥
1
n
n
X
i=1
y
i
≥
1
n − k
n
X
i=k+1
y
i
,
we must have P
i
1
i
2
−1
≥ P
i
1
j
1
≥ P
i
2
j
1
. At the same time we have P
i
2
j
1
≥ P
i
2
j
2
,
which implies P
i
1
j
1
≥ P
i
2
j
2
.
The order in which the steps are