Cambridge University Press
Matrix Preconditioning Techniques and Applications
Department of Mathematical Sciences,
The University of Liverpool
Contents ( Chapters first
/ Full Details second)
Appendix D - LIVE (......click to download ......) soon
(c) K Chen -- Provided for free but full Acknowledgement of this book and its Mfiles is expected.
List of supplied M-files and programs (A zipped file at end)
Most supplied Mfiles for MATLAB experiments and illustrations
have been explained in the text and at the end of the concerned
chapters. The summary given here as a single and brief list
is for reference purpose and easy downloading.
Access to the following supplied Mfiles through the addresses:
http://www.cambridge.org/0521838282
http://www.liv.ac.uk/~cmchenke/mpta
________________________________________________________________
| Chapter 1 ..................| index2.m |
| | intera.m |
| hess_as.m | iter3.m |
| exafft16.m | |
| mygrid.m | Chapter 4 ..................|
| mat_prt.m | |
| mat_prt4.m | banda.m |
| fwt.m | bandb.m |
| ifwt.m | bandg.m |
| fft_fwt.m | circ_pre.m |
| | detect.m |
| Chapter 2 ..................| ilu_0.m |
| | ilu_t.m |
| circ_toep.m | matrix0.mat |
| ge_all.m | matrix1.mat |
| gh_all.m | matrix2.mat |
| givens.m | matrix3.mat |
| houses.m | multic.m |
| mgs.m | schts.m |
| gj_ek.m | t_band.m |
| g_e.m | t_dete.m |
| g_h.m | |
| g_j.m | Chapter 5 ..................|
| mk_ek.m | |
| nsh.m | chebg.m |
| waz_fox.m | cheb_fun.m |
| waz_zol.m | def_no.m |
| waz_all.m | run_ai.m |
| | spai2.m |
| Chapter 3 ..................| waz_t.m |
| | |
| ch3_fmm.m | Chapter 6 ..................|
| gmrest_k.m | |
| gmres_c.m | cf_split.m |
| gmres_k.m | ch6_gs.m |
|_______________________________|______________________________|
| Chapter 6 (continue) .......| |
| | Chapter 10 .................|
| ch6_mg2.m | |
| lap_lab.m | ch0_w2.m |
| mgm_2d.m | |
| mgm_2f.m | Chapter 13 .................|
| mgm_2s.m | |
| | bccb.m, bttb.m |
| Chapter 7 ..................| ch13.m |
| | |
| hb1.m | Chapter 14 .................|
| | |
| Chapter 8 ..................| bprod.m |
| | hopf.m |
| ch8.m | |
| cz.m | Chapter 15 .................|
| fwts.m | |
| iperm0.m | cup1.f |
| iperm2.m | cup2.f |
| perm0.m | cup3.f |
| perm2.m | cup23.in |
| run8.m | cup4.f |
| spyc.m | cup5.f |
| | |
| Chapter 9 ...................| Appendices A - E............|
| | |
| gmres_nr.m | ap2f.m |
| iwts.m | ap2m.m |
| richa_nr.m | my_jordan.m |
| run9.m | mat_pr0.m |
| | size6.m, size6.rua |
|_______________________________|______________________________|
Finally, (1) Alphabetical list of Mfiles/programs
(2) A zipped file of all Mfiles/programs
1 Introduction......................................1
2 Direct methods 57
3 Iterative Methods 97
4 Matrix Splitting Preconditioners [T1] 145
5 Approximate Inverse Preconditioners [T2] 167
6 Multilevel Methods and Preconditioners [T3] 210
7 Multilevel Recursive Schur Complements
Preconditioners [T4] 254
8 Wavelet Preconditioners [T5] for "A and A^{-1}" 273
9 Wavelet Schur Preconditioners [T6] 300
10 Implicit Wavelet Preconditioners [T7] 322
11 Application I - Acoustic Scattering Modelling 339
12 Application II - Coupled Matrix Problems 355
13 Application III - Image Restoration and
Inverse Problems 368
14 Application IV - Voltage Stability in
Electrical Power Systems 398
15 Parallel Computing by Examples 421
Appendices A-E ............................... 466
Abstract page ii
Preface vii
Nomenclature xiii
1 Introduction ..................................... 1
1.1 Direct and iterative solvers, types of preconditioning2
1.2 Norms and condition number 3
1.3 Perturbation theories for systems and eigenvalues 8
1.4 The Arnoldi iterations and decomposition 10
1.5 Clustering characterization, field of values and
- -pseudospectrum 14
1.6 Fast Fourier transforms and fast wavelet transforms16
1.6.1 The fast Fourier transform 17
1.6.2 The fast wavelet transform 29
1.7 Numerical solution techniques for practical equations34
1.7.1 The Finite Element Method (FEM) 35
1.7.2 The Boundary Element Method (BEM) 39
1.7.3 The Finite Difference Method (FDM) 45
1.7.4 The Finite Volume Method (FVM) 48
1.7.5 The Global Element Methods (GEM's) 51
1.7.6 Linearization Methods 52
1.8 Common theories on preconditioned systems 53
1.9 On software development and the supplied Mfiles 54
2 Direct methods ................................. 57
2.1 The LU decomposition and variants 59
2.1.1 The standard LDM factorization 59
2.1.2 Schur complements and the partitioned LU
factorization 61
2.1.3 The substitution free W'AZ factorization 63
2.2 The Newton-Schulz-Hostelling method 65
2.3 The Gauss-Jordan decomposition and variants 66
2.3.1 The standard GJ factorization 66
2.3.2 A block variant of the GJ 68
2.3.3 Huard and Purcell methods 69
2.4 The QR decomposition 71
2.4.1 Method 1 - Givens plane rotations 71
2.4.2 Method 2 - Householder transformations 72
2.4.3 Method 3 - Gram-Schmidt 72
2.5 Special matrices and their direct inversion 74
2.5.1 Banded arrow matrices 75
2.5.2 Circulant and Toeplitz matrices 76
2.5.3 Special matrices with known inverse 85
(1) Special lower triangular matrices 85
(2) Special dense matrices 86
(3) Kroneker tensor products 87
(4) Sherman-Morrison types 87
2.6 Ordering algorithms for better sparsity 88
2.6.1 Reverse Cuthill-McKee Algorithm 91
2.6.2 Duff's spiral ordering Algorithm for surfaces91
2.6.3 Domain decomposition re-ordered matrices 93
2.7 Discussion of software and the supplied Mfiles 95
3 Iterative Methods .............................. 97
3.1 Solution complexity and expectations 98
3.2 Introduction to residual correction 99
3.3 Classical iterative methods 99
3.3.1 Richardson A = M - N 100
3.3.2 Jacobi, GS and SOR 101
3.4 The conjugate gradient method - the SPD case 105
3.5 The conjugate gradient normal method - the
unsymmetric case 115
3.6 The generalised minimal residual method - GMRES 117
3.7 The GMRES algorithm in complex arithmetic 124
3.8 Matrix free solvers: the fast multipole methods 126
3.9 Discussion of software and the supplied Mfiles 141
4 Matrix Splitting Preconditioners [T1] ......... 145
4.1 Banded preconditioner 146
4.2 Banded arrow preconditioner 147
4.3 Block arrow preconditioner from DDM ordering 148
4.4 Triangular preconditioners 150
4.5 ILU preconditioners 151
4.6 Fast circulant preconditioners 154
4.7 Singular operator splitting preconditioners 160
4.8 Preconditioning the fast multipole method 163
4.9 Numerical experiments 163
4.10 Discussion of software and the supplied Mfiles 164
5 Approximate Inverse Preconditioners [T2] ...... 167
5.1 How to characterize A1 in terms of A 168
5.2 Banded preconditioner 170
5.3 Polynomial preconditioner pk(A) 171
5.4 General and adaptive sparse approximate inverses 174
5.4.1 Review of solution techniques for a least
square problem 174
5.4.2 SPAI construction for a given pattern S 175
5.4.3 Adaptive SPAI methods 176
5.4.4 Acceleration using a priori patterns 183
5.5 AINV type preconditioner 185
5.6 Multi-level preconditioner 186
5.6.1 Deflating a single eigenvalue 187
5.6.2 Deflation method 1 188
5.6.3 Deflation method 2 189
5.6.4 Using approximate eigenvectors for deflation189
5.6.5 Factorization based Level-2 preconditioner 192
5.7 The dual tolerance self-preconditioning method 196
5.8 Near neighbour splitting for singular integral equations198
5.8.1 Solution of the least squares problem 199
5.8.2 The DBAI preconditioner 201
5.8.3 Analysis of the 3D case 206
5.9 Numerical experiments 207
5.10 Discussion of software and the supplied Mfiles 208
6 Multilevel Methods and Preconditioners
[T3] ................................... 210
6.1 Multigrid method for linear PDEs 211
6.1.1 Relaxation and smoothing analysis 211
6.1.2 Restriction and interpolation 218
6.1.3 Multigrid algorithms 221
6.1.4 Convergence results 224
6.2 Multigrid method for nonlinear PDEs 228
6.2.1 Full approximation schemes 229
6.2.2 Nonlinear multigrid algorithms 229
6.3 Multigrid method for linear integral equations 232
6.3.1 The case of a second kind equation with a
compact operator 233
6.3.2 Operator splitting for a non-compact operator237
6.4 Algebraic multigrid methods 238
6.4.1 Algebraic smoothness 239
6.4.2 Choice of coarser levels 241
6.4.3 Matrix-dependent transfer operators 243
6.4.4 AMG algorithms and AMG preconditioners 244
6.5 Multilevel domain decomposition preconditioners 245
6.5.1 The additive multilevel preconditioner 247
6.5.2 The additive multilevel diagonal preconditioner249
6.5.3 The additive multilevel BPX preconditioner 250
6.5.4 The multiplicative multilevel preconditioner250
6.6 Discussion of software and the supplied Mfiles 251
7 Multilevel Recursive Schur Complements
Preconditioners [T4] ................... 254
7.1 Multilevel functional partition: AMLI approximated2Schur55
7.2 Multilevel geometrical partition: exact Schur 259
7.3 Multilevel algebraic partition: permutation based2Schur64
7.4 Appendix - the FEM hierachical basis 268
7.5 Discussion of software and the supplied Mfiles 271
8 Wavelet Preconditioners [T5] for
"A and A^{-1}" .................... 273
8.1 Multilresolution and wavelets 274
8.1.1 Multilresolution analysis 275
8.1.2 Two-scale equations, orthogonalityFandourier
analysis 276
8.1.3 Pyramidal algorithms 279
8.1.4 Discrete wavelets as matrix computation tools281
8.2 Operator compression by wavelets and sparsity patterns282
8.3 Band WSPAI preconditioner 285
8.4 New centering WSPAI preconditioner 287
8.4.1 A new non-standard DWT 287
8.4.2 Band matrices under the new DWT 291
8.4.3 Applications to preconditioning a linear system294
8.5 Optimal implementations and wavelet quadratures 296
8.6 Numerical Results 297
8.7 Discussion of software and the supplied Mfiles 297
9 Wavelet Schur Preconditioners [T6] ............ 300
9.1 Introduction 301
9.2 Wavelets telescopic splitting of an operator 301
9.3 An exact Schur preconditioner with level-by-level3wavelets06
9.4 An approximate preconditioner with level-by-level3wavelets11
9.5 Some analysis and experiments 316
9.5.1 Complexity analysis 316
9.5.2 An analysis of preconditioner I 317
9.5.3 Numerical experiments 320
9.6 Discussion of the supplied Mfiles 320
10 Implicit Wavelet Preconditioners [T7] ........ 322
10.1 Introduction 323
10.2 Wavelet based sparse approximate inverse 326
10.3 An implicit wavelet SPAI preconditioner 327
10.4 Implementation details 328
10.5 Dense problems 332
10.6 Some theoretical results 333
10.7 Combination with a level-1 preconditioner 336
10.8 Numerical results 337
10.9 Discussion of the supplied Mfile 337
11 Application I - Acoustic Scattering Modelling 339
11.1 The boundary integral equations for the Helmholtz
equation in R3 339
11.1.1 The time-harmonic wave equation 340
11.1.2 A unique BIE formulation in R3 340
11.1.3 The piecewise constant approximation 342
11.1.4 The high order Galerkin approximation 343
11.1.5 The high order collocation approximation using
finite part integration 344
11.1.6 A new high order collocation approximation 346
11.2 The low wavenumber case of a Helmholtz equation 351
11.3 The high wavenumber case of a Helmholtz equation 352
11.4 Discussion of software 353
12 Application II - Coupled Matrix Problems ..... 355
12.1 Generalized saddle point problems 356
12.2 The Oseen and Stokes saddle point problems 358
12.3 The mixed finite element method 360
12.4 Coupled systems from fluid structure interaction 361
12.5 Elastohydrodynamic lubrication modelling 364
12.5.1 Coupled isothermal equations 364
12.5.2 Coupled thermal equations 366
12.6 Discussion of software and a supplied Mfile 367
13 Application III - Image Restoration and
Inverse Problems ............................. 368
13.1 Image restoration models and discretizations 369
13.1.1 Solution of a first kind equation 370
13.1.2 Regularity condition: total and bounded variation371
13.1.3 Tikhonov regularization 371
13.1.4 Discretizations 373
13.1.5 Computation of w = Kv by FFT 377
13.2 Fixed point iteration method 380
13.2.1 A differential operator based preconditioner381
13.2.2 An integral operator based preconditioner 381
13.2.3 The use of DWT for a mixed preconditioner 383
13.3 Explicit time marching schemes 387
13.4 The Primal-dual method 387
13.5 Nonlinear multigrids for optimization 390
13.6 The level set method and other image problems 392
13.7 Numerical experiments 396
13.8 Guide to software and the supplied Mfiles 396
14 Application IV - Voltage Stability in Electrical
Power Systems ................................ 398
14.1 The model equations 398
14.2 Fold bifurcation and arc-length continuation 402
14.3 Hopf bifurcation and solutions 406
14.3.1 The tensor product of matrices 411
14.3.2 The biproduct of matrices 414
14.3.3 Hopf test functions 417
14.4 Preconditioning issues 419
14.5 Discussion of software and the supplied Mfiles 420
15 Parallel Computing by Examples ............... 421
15.1 A brief introduction to parallel computing and MPI422
15.2 Some commonly used MPI routines 423
15.3 Example 1 of a parallel series summation 427
15.4 Example 2 of a parallel power method 431
15.5 Example 3 of a parallel direct method 433
15.5.1 The Purcell method 434
15.5.2 Comparison of the Purcell method with others436
15.5.3 Parallellisation of the Purcell method 437
15.5.4 Numerical examples 441
15.6 Discussion of software and the supplied MPI programs444
Appendix A - A Brief Guide to Linear Algebra .......... 446
A.1 Linear independence 446
A.2 Range and null spaces 446
A.3 Orthogonal vectors and matrices 447
A.4 Eigenvalues, symmetric matrices and diagonalization447
A.5 Determinants and Cramer's rule 448
A.6 The Jordan decomposition 448
A.7 The Schur and related decompositions 450
Appendix B - The Harwell-Boeing (HB) data format ...... 452
Appendix C - A Brief Guide to MATLAB .................. 454
C.1 Vectors and matrices 454
C.2 Visualisation of functions 455
C.3 Visualisation of sparse matrices 456
C.4 The functional Mfile and string evaluations 457
C.5 Interfacing MATLAB with Fortran or C 458
C.6 Debugging a Mfile 460
C.7 Symbolic computing 461
Appendix D - List of supplied M-files and programs .... 463
Appendix E - List of selected scientific resources on Internet465
E.1 Freely available software and data 465
E.2 Other software sources 466
E.3 Useful software associated with books 467
E.4 Specialized subjects, sites and interest groups 468
Bibliography .......................................... 469
Author Index 500
Subject Index .......................................... 505
< Back to
to Ke's home page