The Multilevel Fast Multipole Algorithm (MLFMA) for Solving Large-Scale Computational Electromagnetics Problems

Preface xi

List of Abbreviations xiii

1 Basics 1

1.1 Introduction 1

1.2 Simulation Environments Based on MLFMA 2

1.3 From Maxwell's Equations to Integro-Differential Operators 3

1.4 Surface Integral Equations 7

1.5 Boundary Conditions 9

1.6 Surface Formulations 10

1.7 Method of Moments and Discretization 12

1.7.1 Linear Functions 15

1.8 Integrals on Triangular Domains 21

1.8.1 Analytical Integrals 22

1.8.2 Gaussian Quadratures 26

1.8.3 Adaptive Integration 26

1.9 Electromagnetic Excitation 29

1.9.1 Plane-Wave Excitation 29

1.9.2 Hertzian Dipole 31

1.9.3 Complex-Source-Point Excitation 31

1.9.4 Delta-Gap Excitation 32

1.9.5 Current-Source Excitation 34

1.10 Multilevel Fast Multipole Algorithm 35

1.11 Low-Frequency Breakdown of MLFMA 39

1.12 Iterative Algorithms 41

1.12.1 Symmetric Lanczos Process 42

1.12.2 Nonsymmetric Lanczos Process 44

1.12.3 Arnoldi Process 45

1.12.4 Golub-Kahan Process 45

1.13 Preconditioning 46

1.14 Parallelization of MLFMA 50

2 Solutions of Electromagnetics Problems with Surface Integral Equations 53

2.1 Homogeneous Dielectric Objects 53

2.1.1 Surface Integral Equations 54

2.1.2 Surface Formulations 55

2.1.3 Discretizations of Surface Formulations 58

2.1.4 Direct Calculations of Interactions 60

2.1.5 General Properties of Surface Formulations 67

2.1.6 Decoupling for Perfectly Conducting Surfaces 73

2.1.7 Accuracy with Respect to Contrast 74

2.2 Low-Contrast Breakdown and Its Solution 77

2.2.1 A Combined Tangential Formulation 77

2.2.2 Nonradiating Currents 80

2.2.3 Conventional Formulations in the Limit Case 81

2.2.4 Low-Contrast Breakdown 82

2.2.5 Stabilization by Extraction 82

2.2.6 Double-Stabilized Combined Tangential Formulation 87

2.2.7 Numerical Results for Low Contrasts 88

2.2.8 Breakdown for Extremely Low Contrasts 91

2.2.9 Field-Based-Stabilized Formulations 93

2.2.10 Numerical Results for Extremely Low Contrasts 95

2.3 Perfectly Conducting Objects 105

2.3.1 Comments on the Integral Equations 106

2.3.2 Internal-Resonance Problem 108

2.3.3 Formulations of Open Surfaces 108

2.3.4 Low-Frequency Breakdown 111

2.3.5 Accuracy with the RWG Functions 115

2.3.6 Compatibility of the Integral Equations 122

2.3.7 Convergence to Minimum Achievable Error 124

2.3.8 Alternative Implementations of MFIE 130

2.3.9 Curl-Conforming Basis Functions for MFIE 131

2.3.10 LN-LT Type Basis Functions for MFIE and CFIE 137

2.3.11 Excessive Discretization Error of the Identity Operator 160

2.4 Composite Objects with Multiple Dielectric and Metallic Regions 165

2.4.1 Special Case: Homogeneous Dielectric Object 168

2.4.2 Special Case: Coated Dielectric Object 169

2.4.3 Special Case: Coated Metallic Object 172

2.5 Concluding Remarks 175

3 Iterative Solutions of Electromagnetics Problems with MLFMA 177

3.1 Factorization and Diagonalization of the Green's Function 177

3.1.1 Addition Theorem 177

3.1.2 Factorization of the Translation Functions 180

3.1.3 Expansions 183

3.1.4 Diagonalization 184

3.2 Multilevel Fast Multipole Algorithm 186

3.2.1 Recursive Clustering 186

3.2.2 Far-Field Interactions 187

3.2.3 Radiation and Receiving Patterns 188

3.2.4 Near-Field Interactions 190

3.2.5 Sampling 190

3.2.6 Computational Requirements 192

3.2.7 Anterpolation 194

3.3 Lagrange Interpolation and Anterpolation 196

3.3.1 Two-Step Method 198

3.3.2 Virtual Extension of the ¿-f Space 199

3.3.3 Sampling at the Poles 201

3.3.4 Interpolation of Translation Operators 205

3.4 MLFMA for Hermitian Matrix-Vector Multiplications 211

3.5 Strategies for Building Less-Accurate MLFMA 213

3.6 Iterative Solutions of Surface Formulations 215

3.6.1 Hybrid Formulations of PEC Objects 216

3.6.2 Iterative Solutions of Normal Equations 226

3.6.3 Iterative Solutions of Dielectric Objects 238

3.6.4 Iterative Solutions of Composite Objects with Multiple Dielectric and Metallic Regions 247

3.7 MLFMA for Low-Frequency Problems 252

3.7.1 Factorization of the Matrix Elements 256

3.7.2 Low-Frequency MLFMA 259

3.7.3 Broadband MLFMA 261

3.7.4 Numerical Results 261

3.8 Concluding Remarks 268

4 Parallelization of MLFMA for the Solution of Large-Scale Electromagnetics Problems 269

4.1 On the Parallelization of MLFMA 269

4.2 Parallel Computing Platforms for Numerical Examples 270

4.3 Electromagnetics Problems for Numerical Examples 271

4.4 Simple Parallelizations of MLFMA 271

4.4.1 Near-Field Interactions 271

4.4.2 Far-Field Interactions 273

4.5 The Hybrid Parallelization Strategy 274

4.5.1 Aggregation Stage 275

4.5.2 Translation Stage 277

4.5.3 Disaggregation Stage 278

4.5.4 Communications in Hybrid Parallelizations 278

4.5.5 Numerical Results with the Hybrid Parallelization Strategy 279

4.6 The Hierarchical Parallelization Strategy 283

4.6.1 Hierarchical Partitioning of Tree Structures 283

4.6.2 Aggregation Stage 285

4.6.3 Translation Stage 286

4.6.4 Disaggregation Stage 286

4.6.5 Communications in Hierarchical Parallelizations 287

4.6.6 Irregular Partitioning of Tree Structures 288

4.6.7 Comparisons with Previous Parallelization Strategies 289

4.6.8 Numerical Results with the Hierarchical Parallelization Strategy 291

4.7 Efficiency Considerations for Parallel Implementations of MLFMA 295

4.7.1 Efficient Programming 295

4.7.2 System Software 297

4.7.3 Load Balancing 297

4.7.4 Memory Recycling and Optimizations 302

4.7.5 Parallel Environment 306

4.7.6 Parallel Computers 315

4.8 Accuracy Considerations for Parallel Implementations of MLFMA 317

4.8.1 Mesh Quality 324

4.9 Solutions of Large-Scale Electromagnetics Problems Involving PEC Objects 324

4.9.1 PEC Sphere 326

4.9.2 Other Canonical Problems 338

4.9.3 NASA Almond 342

4.9.4 Flamme 354

4.10 Solutions of Large-Scale Electromagnetics Problems Involving Dielectric Objects 358

4.11 Concluding Remarks 368

5 Applications 369

5.1 Case Study: External Resonances of the Flamme 369

5.2 Case Study: Realistic Metamaterials Involving Split-Ring Resonators and Thin Wires 373

5.3 Case Study: Photonic Crystals 377

5.4 Case Study: Scattering from Red Blood Cells 380

5.5 Case Study: Log-Periodic Antennas and Arrays 389

5.5.1 Nonplanar Trapezoidal-Tooth Log-Periodic Antennas 389

5.5.2 Circular Arrays of Log-Periodic Antennas 395

5.5.3 Circular-Sectoral Arrays of Log-Periodic Antennas 403

5.6 Concluding Remarks 410

Appendix 411

A.1 Limit Part of the ¿ Operator 411

A.2 Post Processing 412

A.2.1 Near-Zone Electromagnetic Fields 413

A.2.2 Far-Zone Fields 414

A.3 More Details of the Hierarchical Partitioning Strategy 423

A.3.1 Aggregation/Disaggregation Stages 423

A.3.2 Translation Stage 424

A.4 Mie-Series Solutions 425

A.4.1 Definitions 426

A.4.2 Debye Potentials 426

A.4.3 Electric and Magnetic Fields 427

A.4.4 Incident Fields 427

A.4.5 Perfectly Conducting Sphere 428

A.4.6 Dielectric Sphere 428

A.4.7 Coated Perfectly Conducting Sphere 429

A.4.8 Coated Dielectric Sphere 430

A.4.9 Far-Field Expressions 432

A.5 Electric-Field Volume Integral Equation 433

A.6 Calculation of Some Special Functions 437

A.6.1 Spherical Bessel Functions 437

A.6.2 Legendre Functions 437

A.6.3 Gradient of Multipole-to-Monopole Shift Functions 439

A.6.4 Gaunt Coefficients 439

References 441

Index 453