Series editor's preface ......................................... v
INTRODUCTION ................................................. xiii
1 FAST METHODS FOR SOLVING THE POISSON EQUATION ................ 1
1.1 Introduction ............................................ 1
1.2 Direct methods .......................................... 5
1.2.1 Introduction ..................................... 5
1.2.2 Shintani's algorithm ............................. 7
1.2.3 Fundamental marching algorithms ................. 10
1.2.4 Mejran's modification of the matrix
decomposition algorithm ......................... 12
1.2.5 Lorenz's variant of the marching method ......... 14
1.3 Applications of direct methods to solving other
boundary value problems ................................ 17
1.3.1 Neumann's boundary value problem ................ 17
1.3.2 Problem with periodic boundary value
conditions ...................................... 23
1.4 Iterative methods ...................................... 26
1.4.1 Introduction .................................... 26
1.4.2 Fundamental iterative methods ................... 27
1.4.3 Two-step and optimalization methods ............. 29
1.4.4 Relaxation multigrid method ..................... 33
1.5 Solving the Poisson equation on non-rectangular
domains ................................................ 35
1.5.1 Introduction .................................... 35
1.5.2 Method of embedding into a rectangle ............ 37
1.5.3 Method of Active unknowns ....................... 39
1.5.4 Method of decomposition ......................... 41
1.5.5 An algorithm for an octagonal domain ............ 44
1.5.6 An algorithm for a disc ......................... 47
References .................................................. 50
2 FAST SERIAL ALGORITHMS FOR SOLVING BIHARMONIC EQUATION ....... 53
2.1 Introduction ........................................... 53
2.2 Direct, methods ........................................ 56
2.2.1 Golub's algorithm ............................... 58
2.2.2 The Buzbee-Dorr algorithm ....................... 60
2.2.3 Bjørstad's algorithm ............................ 61
2.3 Algorithms based on splitting .......................... 63
2.3.1 The splitting method ............................. 63
2.3.2 A fast iterative process for the splitting
method and its algorithmic and program
realization ..................................... 68
2.3.3 An algorithm for one iteration using an
elimination procedure ........................... 73
2.4 Solving the eigenvalue problem for a biharmonic
operator ............................................... 78
References .................................................. 84
3 PARALLEL ALGORITHMS FOR SOLVING CERTAIN ELLIPTIC BOUND
ARY VALUE PROBLEMS .......................................... 87
3.1 Introduction ........................................... 87
3.2 Parallel methods for solving the Poisson equation on
multiprocessors ........................................ 90
3.2.1 Introduction .................................... 90
3.2.2 Parallel block matrix decomposition ............. 91
3.2.3 Parallel marching algorithms .................... 95
3.2.4 A parallel domain decomposition method ......... 101
3.2.5 A parallel variant of the cyclic odd-even
reduction solver ............................... 105
3.2.6 An iterative parallel algorithm ................ 108
3.3 Parallel algorithms for solving biharmonic equations
on SIMD computers ..................................... 111
3.3.1 Introduction ................................... 1ll
3.3.2 Parallel algorithms using matrix
decomposition .................................. 114
3.3.3 Application of reduction algorithms ............ 118
3.3.4 Elimination parallel algorithm ................. 124
3.3.5 A block explicit iterative method .............. 128
References ................................................. 130
4 IMPLEMENTATION OF PARALLEL ALGORITHMS ON SPECIALIZED
COMPUTERS .................................................. 134
4.1 Introduction .......................................... 134
4.2 Implementation of parallel algorithms on matrix
processors ............................................ 139
4.2.1 Introduction ................................... 139
4.2.2 Algorithms for the matrix processor ICL DAP .... 141
4.2.3 Multicolour iteration schemes for the
specialized FEM processor ...................... 147
4.3 Parallel algorithms for pipeline computers ............ 149
4.3.1 Introduction ................................... 149
4.3.2 Conjugate gradient algorithm for CDC
STAR-100 ....................................... 152
4.3.3 Black-white iteration scheme on the CRAY-1
computer ....................................... 157
4.4 Implementation of fast parallel algorithms for
solving Poisson and biharmonic equations on
multiprocessor computers .............................. 161
4.4.1 Introduction ................................... 161
4.4.2 Principal characteristics of the EGPA system ... 164
4.4.3 Formulation of algorithms for EGPA ............. 166
4.4.4 The results of the implementation .............. 170
4.5 Algorithms for massively parallel computers ........... 173
4.5.1 Introduction ................................... 173
4.5.2 An example for the Connection Machine .......... 174
4.5.3 Matrix multiplication on the MasPar computer ... 179
References ................................................. 198
5 PARALLEL MULTIGRID ALGORITHMS .............................. 203
5.1 Introduction .......................................... 203
5.2 Parallelization principles for multigrid algorithms ... 207
5.2.1 Introduction ................................... 207
5.2.2 Parallel implementation of a multigrid cycle ... 207
5.2.3 SIMD implementation of the multigrid
algorithm ...................................... 211
5.2.4 Algorithm for a parallel computation over all
grids .......................................... 214
5.2.5 Complexity of multigrid algorithms for some
parallel computer topologies ................... 218
5.3 Multigrid algorithms for parallel systems with
hypercube structure ................................... 226
5.3.1 Introduction ................................... 226
5.3.2 Hypercube and Gray code ........................ 228
5.3.3 Parallelization of multigrid algorithms by
Gray codes ..................................... 231
5.4 Experiments with multigrid algorithms on parallel
computers ............................................. 237
5.4.1 Introduction ................................... 237
5.4.2 The multigrid parallel method for the CRAY
X-MP ........................................... 238
5.4.3 Algorithms for the DIRMU modular system ........ 243
5.4.4 Multigrid method amenable for
implementation on systems with massive
parallelism .................................... 246
References ................................................. 249
6 VLSI ELLIPTIC SOLVERS ...................................... 252
6.1 Introduction .......................................... 252
6.2 VLSI algorithms for special band systems .............. 253
6.2.1 Introduction ................................... 253
6.2.2 Recursive algorithm for band systems ........... 253
6.2.3 VLSI cyclic reduction .......................... 256
6.3 VLSI Poisson solvers .................................. 258
6.3.1 Introduction ................................... 258
6.3.2 Matrix decomposition VLSI algorithm ............ 259
6.3.3 VLSI implementation of an elimination Poisson
solver ......................................... 261
6.3.4 VLSI cyclic odd-even designs ................... 266
6.3.5 VLSI multigrid solver .......................... 270
6.4 VLSI Helmholtz and biharmonic solvers ................. 272
6.4.1 Introduction ................................... 272
6.4.2 A VLSI capacitance matrix solver for the
Helmholtz equation ............................. 273
6.4.3 A VLSI biharmonic semidirect solver with
multigrid Poisson blocks ....................... 277
6.4.4 An application of direct VLSI Poisson
solvers to the biharmonic problem .............. 283
References ............................................ 286
Subject index ................................................. 288
|
