Sparse Linear Solvers

Background

Dr. John Appleyard, one of the directors of Polyhedron Solutions, was one of the original authors of Eclipse, the oil reservoir simulator now developed and marketed by Schlumberger, which has been a dominant force in the industry for 30 years.  He made numerous technical innovations, including the well-known Nested Factorization algorithm, which is used to solve the linear equations in Eclipse.  In recent years, he has renewed his interest in linear solvers, and developed new solvers, including MPNF, which is designed to work best on massively parallel processors.  Dr Appleyard holds two patents covering various aspects of this work.

MPNF (Massively Parallel Nested Factorization)

MPNF is an iterative solver for sparse linear equations arising from space and time discretization of fluid flow problems – such as those arising in oil reservoir simulation. The underlying grid may be structured or unstructured. It is designed to exploit the parallel processing capabilities of GPU-style processors, as supplied by companies such as NVIDIA, AMD and Intel.  MPNF is a natural complement to the Multigrid methods often used in modern simulators – in many cases one excels where the other struggles.

Currently, MPNF is available as a DLL (Windows) or shared object (Linux) for NVIDIA GPUs. Some customization is likely to be required to integrate MPNF with client software.  Please contact us to discuss possible applications of MPNF.

Anonymized MPNF Benchmarks

The table shows anonymized results of benchmark runs using a client oil reservoir simulator. It compares an existing arithmetic multi-grid (AMG) implementation of a CPR based solver with a block Jacobi smoother, to a hybrid method using AMG with an MPNF smoother, and finally, a full MPNF solver.

Multigrid + Block Jacobi smoother Multigrid + MPNF smoother MPNF throughout
Test cells Total CPU Newtons Linears Solver CPU Total CPU Newtons Linears Solver CPU Total CPU Newtons Linears Solver CPU
A 1010 2.64 54 293 1.47 2.80 53 240 1.53 2.24 53 161 1.11
B 3036 48.03 573 4792 33.84 45.33 561 3275 30.99 26.40 518 1595 13.28
C 104 5.35 160 945 3.19 5.21 160 656 3.10 4.03 160 598 2.13
D 304 15.02 337 2743 10.37 12.57 337 1315 8.00 8.26 339 1220 3.84
E 1208 15.66 211 2420 11.67 14.89 255 1490 10.65 16.27 249 1488 12.30
F 1631 9.19 108 1193 6.49 7.58 110 568 4.77 5.84 110 398 3.26
G 23 2.33 52 394 0.67 2.13 53 162 0.42 1.92 52 165 0.34
H 4804 21.12 314 2144 15.96 19.37 316 1245 14.59 12.89 314 1156 8.58
I 109307 119.81 354 2655 75.13 126.44 356 1424 78.57 85.20 355 1330 45.69
J 5000 3.31 29 308 2.20 3.13 29 189 1.95 1.98 30 95 0.90
K 5016 10.21 94 1126 7.74 11.45 93 1106 8.74 4.22 86 172 1.89
L 1261 4.86 38 440 3.19 4.56 38 260 2.75 2.41 38 76 0.72
M 147087 218.46 383 4349 149.38 159.05 226 2159 108.05 75.79 221 580 33.44
N 587768 1373.30 671 7800 938.07 1521.40 613 6042 1055.00 750.21 594 1834 370.26
O 898704 972.50 253 2583 692.59 967.89 253 1744 667.67 804.21 254 2014 559.56
P 400084 28.92 16 146 14.80 34.55 16 121 17.49 24.23 16 86 10.43
Q 100084 7.53 15 97 3.68 9.33 15 94 4.68 10.76 15 167 6.07
R 25064 2.87 14 85 1.54 3.45 14 86 1.89 3.06 14 115 1.88
S 6294 1.41 13 62 0.70 1.54 13 51 0.81 2.72 13 200 2.07
T 1734 1.05 14 65 0.57 1.15 14 56 0.60 2.01 14 168 1.49
U 534 0.81 13 57 0.39 0.92 13 50 0.40 0.93 13 55 0.50
V 204 0.72 12 54 0.34 0.80 12 43 0.34 0.70 12 35 0.24
Odeh-IMPES 300 12.45 307 1360 6.71 11.71 307 839 6.26 7.10 306 796 1.95
Odeh-FI 300 5.29 132 889 3.82 4.53 132 472 3.01 2.78 132 433 1.56
SPE9 simple 9052 43.67 332 3395 26.70 39.37 247 1864 20.90 41.31 266 2329 25.58
SPE9 vanilla 9106 532.14 4045 47546 354.74 84.41 394 3914 38.42 94.78 491 4673 52.99
SPE10 (1/4) 273905 1078.50 1170 13845 733.83 956.85 774 7911 691.15 1658.61 863 10332 1412.39
Geomean 16.08 108.5 850.7 9.68 14.88 95.4 525.1 8.46 11.98 96.0 444.5 6.07
Best Value
More than twice best value