
230 Designing Scientific Applications on GPUs
Algorithm 11: standard simplex algorithm
1 // Find entering variable x
e
;
2 γ
j
← k(A
N
)
j
k
2
;
3 e ← argmax
c/
√
γ
;
4 if e < 0 then
5 return optima found
6 end
7 // Find leaving variable x
`
;
8 `, t ← expand((A
N
)
e
);
9 if ` < 0 then
10 return unbounded
11 end
12 // Pivoting;
13 d ← (A
N
)
e
, d
e
← (A
N
)
`e
− 1;
14 r ← N
T
`
;
15 x
e
← x
e
+ t;
16 x
B
← x
B
− t(A
N
)
e
;
17 A
N
← A
N
− d
T
r/(A
N
)
`e
// cublasDger ;
18 c ← c − c
`
r/(A
N
)
`e
// cublasDaxpy;
19 swap(x
e
, x
`
);
is computed and, since we use a special structure instead of the basis matrix,
the entering and leaving variables are swapped.
Choice of the entering variable
Let us discuss two different approaches ...